Home » Posts tagged 'number theory'

Tag Archives: number theory

Proofs of Irrationality

Tuesday, February 14th, 2012 19:18 / 3 Comments

“Irrational numbers are those real numbers which are not rational numbers!”

A rational number is a real number which can be expressed in the form of $\frac{a}{b}$ where $a$ and $b$ are both integers relatively prime to each other and $b$ being non-zero.
Following two statements are equivalent to the definition 1.
1. $x=\frac{a}{b}$ is rational if and only if $a$ and $b$ are integers relatively prime to each other and $b$ does not equal to zero.
2. $x=\frac{a}{b} \in \mathbb{Q} \iff \mathrm{g.c.d.} (a,b) =1, \ a \in \mathbb{Z}, \ b \in \mathbb{Z} \setminus \{0\}$ .

(more…)

On Ramanujan’s Nested Radicals

Friday, December 30th, 2011 08:50 / 8 Comments

Ramanujan (1887-1920) discovered some formulas on algebraic nested radicals. This article is based on one of those formulas. The main aim of this article is to discuss and derive them intuitively. Nested radicals have many applications in Number Theory as well as in Numerical Methods.

(more…)

Claim for a Prime Number Formula

Sunday, December 11th, 2011 14:42 / 4 Comments

Dr. SMRH Moosavi has claimed that he had derived a general formula for finding the $n$ -th prime number. More details can be found here at PrimeNumbersFormula.com and a brief discussion here at Math.SE titled “Formula for the nth prime number: discovered?”

SOME MORE EXCERPTS ARE HERE:

General Formula

Prime Numbers Formula For $k$ -th prime numberGeneral Formula

Calendar: Finding the Weekdays

Friday, December 9th, 2011 10:07 / 2 Comments

Pope Gregory

This is the last month of the glorious prime year 2011. We are all set to welcome upcoming 2012, which is not a prime but a leap year. Calendars have very decent stories and since this blog is based on mathematical approach, let we talk about the mathematical aspects of calendars.

The international calendar we use is called Gregorian Calendar, said to be created by Pope Gregory XIII. Gregorian calendar was introduced in 80s of 16th century, to be accurate in $1582$ ,—as a correction to earlier Julian Calendar. Julian Calendar was introduced by Julius Caesar and was based on the fact that there were $365 \frac{1}{4}$ days in a year, with leap year every fourth year. Astronomical calculations told us that one year on earth (the time required for the earth to complete an orbit around the sun) was equal to $365.2422$ days —thus we can say that Julian Calendar hadn’t enough precise measure of dates. A difference of $365 \frac{1}{4}-365.2422 =0.0078$ days per year meant that the Julian Calendar receded a day from its astronomical data every $\frac{1}{0.0078}$ years (viz. Approx. $128.2$ years). More information on Julian Calendar can be found at http://en.wikipedia.org/wiki/Julian_Calendar .

The centuries old calendar came to an end as the accumulating inaccuracy caused the vernal equinox (the first day of Spring) to fall on March 11 instead of its proper day, March 21. The inaccuracy naturally persisted throughout the year, but at this season it meant that the Easter festival was celebrated at the wrong astronomical time. Pope Gregory XIII rectified the discrepancy in a new calendar, imposed on the predominantly Catholic Countries of Europe. He decreed that 10 years (11 March to 21 March) were to be omitted from the year $1582$ , by having October 15 of that year immediately follow October 4. At the same time, C. Clavius proposed the scheme for leap years —which must be divisible by 4, except for those marking centuries. Century years would be leap years only if they were disible by 400. This implies that the century years $1600, 2000, 2400$ are leap years, but $1700, 1800, 1900, 2100, 2200, 2300$ are not.
A more detailed info about Gregorian Calendar is here: http://en.wikipedia.org/wiki/Gregorian_Calendar

There are many tricks to determine the day of a week for a given day after the year 1600 in the Gregorian Calendar. But we shall use a number-theoretic method to determine it, as described in the book ‘ELEMENTARY NUMBER THEORY’ by David M. Burton.
We all know that the extra day of a leap year is added to February month of the year, so let us adopt the convenient fiction that each year ends at the end of February. The months for any year Y are:

[LIST A]
1. March
2. April
3. May
4. June
5. July
6. August
7. September
8. October
9. November
10. December
11. January
12. February.

It is clear that if we count for any year $Y$ , January and February must be in next year, $Y+1$ of Gregorian Calendar.

We need another convenient notation as we denote days by numbers $0,1,2,3...6$ as:

[LIST B]
0. Sunday
1. Monday
2. Tuesday
3. Wednesday
4. Thursday
5. Friday
6. Saturday.

The number of days in a common year is $365$ , and the number weeks thus are $\frac{365}{7}$ =52 weeks and 1 day while that in a leap year is $366$ claiming the number of weeks being 52 with two extra days. We could write last sentence as this way too:

Number of days in a common year is $365 \equiv 1 \pmod {7}$ and that in a leap year is $366 \equiv 2 \pmod {7}$ . [See FootNotes]

One extra day remaining after 52 weeks in a common year implies that the day proceeds for ‘one’ week-day for every year. February 28 is last (365th) day of a common year — it always falls on the same weekday as the previous year’s March 1 . But if it follows a leap year day, the last day February 29, its weekday is increased by two.

We can have a mathematical theorem to find which weekday a fixed date will fall.

THEOREM: The day with month $m$ , day $d$ , year $Y=100c+y$ , where $c$ (century) is equal to or greater than 16 and $y$ is any number between 0 and 99 inclusive, has a weekday number $w=d+[2.6 \times m -0.2] -2c+y+[c/4]+[y/4] \pmod{7}$ ,
where $m$ is the number chosen for corresponding month from the [LIST A], $d$ is the number which represent the date in common sense and the square bracket function $[x]$ represent the greatest integer less than or equal to $x$ .
After finding the numerical value of $w$ , we match it with [LIST B] .

Let me illustrate this with an example.

What day of week will be on December 9, 2011?
(That (today?) will be Friday off-course, but we are going to find it mathematically.)

For December 9, 2011:
$m=10$ (see list A)
$d=9$
$Y=2011=2000+ 11=100 \times 20 + 11$
$c=20$
$y=11$

We have
$w=d+[2.6 \times m -0.2] -2c+y+[c/4]+[y/4] \pmod{7}$ as
$w \equiv 9+ [2.6 \times 10 -0.2] -2\times 20 +11+ [20/4]+[11/4] \pmod{7} \\ \equiv 9+[25.8] -40+11+[5]+[2.75] \pmod{7} \\ \equiv 9+25-40+11+5+2 \pmod{7} \\ \equiv 10+ 2 \pmod{7} \\ \equiv 5+\pmod{7}$
This implies that the value of w to be $5, 12, 19, 26, \ldots$ but for $w$ being less than 7, we have $w=5$ . Comparing with table we get that December 9, 2011 occur on Friday (5).

FootNotes:
1.Don’t get confused with [2.75] =2 or [n.xyz]=n. For any positive number, the Square Bracket Function (say it Floor Function or Greatest Integer Function) allows you to leave fractional part of the number. Read more at http://en.wikipedia.org/wiki/Floor_and_Ceiling_Functions .

2.Let n be a fixed positive integer. Two integers a and b are said to be congruent modulo n, symbolised by $a \equiv b \pmod{n}$ , if n divides the difference a-b. For simple understanding $a \equiv b \pmod{n}$ is same to $a-b=kn$ for any $k$ being an integer. We can simplify it for $a$ as $a=kn+b$ . In particular conditions, $a=n+b$ ; $a=2n+b$ , $a=3n+b, \ldots$ . More details at http://mathworld.wolfram.com/Congruence.html . //////////

Well, it’s your turn now:

Find on which weekdays these dates fall:
1. July 4, 1776
2. October 19, 1992
3. August 15, 1947
4. March 21, 1688
5. June 8, 2333.

A Trip to Mathematics: Part IV Numbers

Monday, November 21st, 2011 16:07 / Leave a Comment

If logic is the language of mathematics, Numbers are the alphabet. There are many kinds of number we use in mathematics, but at a broader aspect we may categorize them in two categories:
1. Countable Numbers
2. Uncountable Numbers
The names are enough to explain the properties of above numbers. The numbers which can be counted in nature are called Countable Numbers and the numbers which can not be counted are called Uncountable Numbers.

Well, this is not the correct way to classify the bunch of types of numbers. We have some formal names for special types of numbers, like Real numbers, Complex Numbers, Rational Numbers, Irrational Numbers etc.. We shall discuss these non-interesting numbers (let me say them non-interesting) at first and then some interesting numbers(those numbers are really interesting to learn). Although in this post I have concisely described the classification, I will rigorously discuss them later.
Let me start this discussion with the memorable quote by Leopold Kronecker:

“God created the natural numbers, and all the rest is the work of man.”

What does it mean? What did Kronecker think when he made this quote? Why is this quote true? —First part of this article is based on this discussion.
Actually, he meant to say that all numbers, like Real Numbers, Complex Numbers, Fractions, Integers, Non-integers etc. are made up of the numbers given by God to the human. These God Gifted numbers are actually called Natural Numbers. Natural Numbers are the numbers which are used to count things in nature.

Eight pens, Eighteen trees, Three Thousands people etc. are measure of natural things and thus ‘Eight’, ‘Eighteen’, ‘Three Thousands’ etc. are called natural numbers and we represent them numerically as ’8′, ’18′, ’3000′ respectively. So, if 8, 18, 3000 are used in counting natural things, are natural numbers. Similarly, 1, 2, 3, 4, and other numbers are also used in counting things —thus these are also Natural Numbers.

Let we try to form a set of Natural Numbers. What will we include in this set?

1?    (yes!).
2?    (yes).
3? (yes).
….
1785?    (yes)
…and so on.

This way, after including all elements we get a set of natural numbers {1, 2, 3, 4, 5, …1785, …, 2011,….}. This set includes infinite number of elements. We represent this set by Borbouki’s capital letter N, which looks like $\mathbb{N}$ or bold capital letter N ( $\mathbf{N}$ where N stands for NATURAL. We will define the set of all natural numbers as:

$\mathbb{N} := \{ 1, 2, 3, 4, \ldots, n \ldots \}$ .

It is clear from above set-theoretic notation that $n$ -th element of the set of natural numbers is $n$ .
In general, if a number $n$ is a natural number, we right that $n \in \mathbb{N}$ .
Please note that some mathematicians (and Wolfram Research) treat ’0′ as a natural number and state the set as $\mathbb{N} :=\{0, 1, 2, \ldots, n-1, \ldots \}$ , where $n-1$ is the nth element of the set of natural numbers; but we will use first notion since it is broadly accepted.

Now we shall try to define Integers in form of natural numbers, as Kronecker’s quote demands. Integers (or Whole numbers) are the numbers which may be either positives or negatives of natural numbers including 0.
Few examples are 1, -1, 8, 0, -37, 5943 etc.
The set of integers is denoted by $\mathbb{Z}$ or $\mathbf{Z}$ (here Z stands for ‘Zahlen‘, the German alternative of integers). It is defined by
$\mathbb{Z} := \{ \pm n: n \in \mathbb{N} \} \cup \{0\}$
i.e., $\mathbb{Z} := \{\ldots -3, -2, -1, 0, 1, 2, 3 \ldots \}$ .

Now, if we again consider the statement of Kronecker, we might ask that how could we prepare the integer set $\mathbb{Z}$ by the set $\mathbb{N}$ of natural numbers? The construction of $\mathbb{Z}$ from $\mathbb{N}$ is motivated from the requirement that every integer can be expressed as difference of two positive integers (i.e., Natural Numbers). Let $a,b,c,d \in \mathbb{N}$ and a relation ρ is defined on $\mathbb{N} \times \mathbb{N}$ by $(a,b) \rho (c,d)$ if and only if $a+d = b+c$ . The relation ρ is an equivalence relation and the equivalence classes under ρ are called integers and defined as $\mathbb{Z} := \mathbb{N} \times \mathbb{N} /\rho$ . Now we can define set of integers by an easier way, as $\mathbb{Z}:= \{a-b; \ a,b \in \mathbb{N}\}$ . Thus an integer is a number which can be produced by difference of two or more natural numbers. And similarly as converse defintion, positive integers are called Natural Numbers.
After Integers, we head to rational numbers. Say it again– ‘ratio-nal numbers‘ –numbers of ratio.

Image via Wikipedia

A rational number $\frac{p}{q}$ is defined as a ratio of an integer p and a non-zero integer q. (Well that is not a perfect definition, but as an introduction it is great for understanding.) The set of rational numbers is defined by $\mathbb{Q}$ .
Once integers are formed, we can form Rational (and Irrational numbers: numbers which are not rational ) using integers.
We consider an ordered pair $(p,q):=\mathbb{Z} \times (\mathbb{Z} \setminus \{0 \})$ and another ordered pair $(r,s):=\mathbb{Z} \times (\mathbb{Z} \setminus \{0\})$ and define a relation ρ by $(p,q) \rho (r,s) \iff ps=qr$ for $p,q,r,s \in \mathbb{Z}, \ q, r \ne 0$ . Then ρ is an equivalence relation of rationality, class (p,q). The set $\mathbb{Z} \times (\mathbb{Z} \setminus \{0\})/\rho$ is denoted by $\mathbb{Q}$ (and the elements of this set are called rational numbers).
In practical understandings, the ratio of integers is a phrase which will always help you to define the rational numbers. Examples are $\frac{6}{19}, \ \frac{-1}{2}=\frac{-7}{14}, \ 3\frac{2}{3}, \ 5=\frac{5}{1} \ldots$ . Set of rational numbers includes Natural Numbers and Integers as subsets.
Consequently, irrational numbers are those numbers which can not be represented as the ratio of two integers. For example $\pi, \sqrt{3}, e, \sqrt{11}$ are irrationals.
The set of Real Numbers is a relatively larger set, including the sets of Rational and Irrational Numbers as subsets. Numbers which exist in real and thus can be represented on a number line are called real numbers. As we formed Integers from Natural Numbers; Rational Numbers from Integers, we’ll form the Real numbers by Rational numbers.
The construction of set $\mathbb{R}$ of real numbers from $\mathbb{Q}$ is motivated by the requirement that every real number is uniquely determined by the set of rational numbers less than it. A subset $L$ of $\mathbb{Q}$ is a real number if L is non-empty, bounded above, has no maximum element and has the property that for all $x, y \in \mathbb{Q}, x < y$ and $y \in L$ implies that $x \in L$ . Real numbers are the base of Real Analysis and detail study about them is case of study of Real Anlaysis.
Examples of real numbers include both Rational (which also contains integers) and Irrational Numbers.

The square root of a negative number is undefined in one dimensional number line (which includes real numbers only) and is treated to be imaginary. The numbers containing or not containing an imaginary number are called complex numbers.
Some very familiar examples are $3+\sqrt{-1}, \sqrt{-1} =i, \ i^i$ etc. We should assume that every number (in lay approach) is an element of a complex number. The set of complex numbers is denoted by $\mathbb{C}$ . In constructive approach, a complex number is defined as an ordered pair of real numbers, i.e., an element of $\mathbb{R} \times \mathbb{R}$ [i.e., $\mathbb{R}^2$ ] and the set as $\mathbb{C} :=\{a+ib; \ a,b \in \mathbb{R}$ . Complex numbers will be discussed in Complex Analysis more debately.
We verified Kronecker’s quote and shew that every number is sub-product of postive integers (natural numbers) as we formed Complex Numbers from Real Numbers; Real Numbers from Rational Numbers; Rational Numbers from Integers and Integers from Natural Numbers. //
Now we reach to explore some interesting kind of numbers. There are millions in name but few are the follow:
Even Numbers: Even numbers are those integers which are integral multiple of 2. $0, \pm 2, \pm 4, \pm 6 \ldots \pm 2n \ldots$ are even numbers.

Odd Numbers: Odd numbers are those integers which are not integrally divisible by 2. $\pm 1, \pm 3, \pm 5 \ldots \pm (2n+1) \ldots$ are all odd numbers.

Prime Numbers: Any number $p$ greater than 1 is called a prime number if and only if its positive factors are 1 and the number $p$ itself.
In other words, numbers which are completely divisible by either 1 or themselves only are called prime numbers. $2, 3, 5, 7, 11, 13, 17, 19, 23, 29 \ldots$ etc. are prime numbers or Primes. The numbers greater than 1, which are not prime are called Composite numbers.
Twin Primes: Consecutive prime numbers differing by 2 are called twin primes. For example 5,7; 11,13; 17,19; 29,31; … are twin primes.

Pseudoprimes: Chinese mathematicians claimed thousands years ago that a number $n$ is prime if and only if it divides $2^n -2$ . In fact this conjecture is true for $n \le 340$ and false for upper numbers because first successor to 340, 341 is not a prime ( $31 \times 11$ ) but it divides $2^{341}-2$ . This kind of numbers are now called Pseudoprimes. Thus, if n is not a prime (composite) then it is pseudoprime $\iff n | 2^n-2$ (read as ‘n divides 2 powered n minus 2‘). There are infinitely many pseudoprimes including 341, 561, 645, 1105.

Carmichael Numbers or Absolute Pseudoprimes: There exists some pseudoprimes that are pseudoprime to every base $a$ , i.e., $n | a^n -a$ for all integers $a$ . The first Carmichael number is 561. Others are 1105, 2821, 15841, 16046641 etc.

e-Primes: An even positive integer is called an e-prime if it is not the product of two other even integers. Thus 2, 6, 10, 14 …etc. are e-primes.

Germain Primes: An odd prime p such that 2p+1 is also a prime is called a Germain Prime. For example, 3 is a Germain Prime since $2\times 3 +1=7$ is also a prime.
Relatively Prime: Two numbers are called relatively prime if and only their greatest common divisor is 1. In other words, if two numbers are such that no integer, except 1, is common between them when factorizing. For example: 7 and 9 are relatively primes and same are 15, 49.

Perfect Numbers: A positive integer n is said to be perfect if n equals to the sum of all its positive divisors, excluding n itself. For example 6 is a perfect number because its divisors are 1, 2, 3 and 6 and it is obvious that 1+2+3=6. Similarly 28 is a perfect number having 1, 2, 4, 7, 14 (and 28) as its divisors such that 1+2+4+7+14=28. Consecutive perfect numbers are 6, 28, 496, 8128, 33550336, 8589869056 etc.

Mersenne Numbers and Mersenne Primes: Numbers of type $M_n=2^n-1; \ n \ge 1$ are called Mersenne Numbers and those Mersenne Numbers which happen to be Prime are called Mersenne Primes. Consecutive Mersenne numbers are 1, 3 (prime), 7(prime), 15, 31(prime), 63, 127.. etc.

Catalan Numbers: The Catalan mumbers, defined by $C_n = \dfrac{1}{n+1} \binom{2n}{n} = \dfrac{(2n)!}{n! (n+1)!} \ n =0, 1, 2, 3 \ldots$ form the sequence of numbers 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …

Triangular Number: A number of form $\dfrac{n(n+1)}{2} \ n \in \mathbb{N}$ represents a number which is the sum of n consecutive integers, beginning with 1. This kind of number is called a Triangular number. Examples of triangular numbers are 1 (1), 3 (1+2), 6 (1+2+3), 10(1+2+3+4), 15(1+2+3+4+5) …etc.

Square Number: A number of form $n^2 \ n \in \mathbb{N}$ is called a sqaure number.
For example 1 ( $1^2$ ), 4 ( $2^2$ ), 9( $3^2$ ), 16 ( $4^2$ )..etc are Square Numbers.

Palindrome: A palindrome or palindromic number is a number that reads the same backwards as forwards. For example, 121 is read same when read from left to right or right to left. Thus 121 is a palindrome. Other examples of palindromes are 343, 521125, 999999 etc.

A Trip To Mathematics: Part II Set(Basics) (wpgaurav.wordpress.com)
Do complex numbers really exist? (math.stackexchange.com)
Definitions (gowers.wordpress.com)

How Many Fishes in One Year? [A Puzzle in Making]

Sunday, November 13th, 2011 08:49 / 12 Comments

This is a puzzle which I told to my classmates during a talk, a few days before. I did not represent it as a puzzle, instead of a talk suggesting the importance of Math in general life. This is partially solved for me and I hope you will run your brain-horse to help me solve it completely. If you didn’t notice, this puzzle is not a part of A Trip To Mathematics series. Puzzle which I discussed in the talk was something like this:

“Let I have seven fishes in a huge tank of water —four male and three females. Those were allowed to sex independently but under some conditions. One male is allowed to have intercourse with female, unless other has done so. A male can have intercourse with any number of female fishes possible. If we assume that first female fish could give 100 eggs, second female fish could give 110, third 90. We are also known that a female fish might lay eggs in 21 days since the date of sex with male. The children fish are reproductive only after those are 30 days old. In each bunch of children fish of individual female fish, 60% die. In remaining 40% child fishes, the ratio of male and female is 3:2. If two fishes (male and female) can not do intercourse with each other if those are born to same mother fish, one male is allowed to have intercourse with female, unless other has done so, a male can have intercourse with any number of fishes possible, every three female fishes lay eggs in order of 100,110 and 90 eggs out of which only 40% remain alive having a ratio of male and females of 1:1 and the same rule applies to third, fourth and consecutive generations of fishes; then find the number of total fishes in my tank after one year (365 days).”

I have done many proofreads of this puzzle and found it valid. Your comments, your ideas and suggestions might help me working more rigorously on this puzzle. This puzzle is neither too hard nor too easy. I will be updating this post frequently as my work on this puzzle is directed towards a correct way.

The problem of the Hundred Fowls

Saturday, October 1st, 2011 17:37 / Leave a Comment

This is a popular Chinese problem, on Linear Diophantine equations, which in wording seems as a puzzle or riddle. However, when used algebraic notations, it looks obvious. The problems states :

If a cock is worth 5 coins, a hen 3 coins, and three chickens together 1 coin, how many cocks, hens and chickens, totaling 100 in number, can be bought for 100 coins?

This puzzle in terms of algebraic equations can be written as $5x+3y+\frac{1}{3}z=100$ and $x+y+z=100$
where $x, y, z$ being the number of cocks, hens and chicks respectively.
We find that there are two equations with three unknown quantities. So eliminating one of the unknowns, by putting $z=100-x-y$ from second equation into first one such that $5x+3y+\frac{1}{3} (100-x-y)=100$
or, $15x+9y+100-x-y=300$
or, $14x+8y=200$
or, $7x+4y=100$ .
Which is a linear Diophantine equation (with only two unknown quantities).
The equation $7x+4y=100$ has the general solution [links to WolframAlpha] $x=4 t$ and $y=25-7t$ , so that $z=75+3t$ where $t$ is an arbitrary integer.
Now, since $x, y, z$ are the number of creatures, hence $x, y, z >0$ and thus $4t >0$ , $25-7t >0$ and $75+3t >0$ which imply that $0 < t < 3\frac{4}{7}$ . And because t must have integer values, we have $t=1,2,3$ . Which gives the following three solutions: