Number Theory: Historical Introduction: Tom Apostol

Reference: Introduction to Analytic Number Theory by Tom Apostol.

The theory of numbers is that branch of mathematics which deals with properties of the whole numbers: 1, 2, 3, 4, 5, …

also called the counting numbers, or positive integers.

The positive integers are undoubtedly man’s first mathematical creation. It is hardly possible to imagine human beings without the ability to count, at least within a limited range. Historical record shows that as early as 5700 BC the ancient Sumerians kept a calendar, so they must have developed some form of arithmetic.

By 2500 BC, the Sumerians had developed a number system using 60 as a base. This was passed on to the Babylonians, who became highly skilled calculators. Babylonian clay tablets containing elaborate mathematical tables have been found, dating back to 2000BC.

When ancient civilizations reached a level which provided some leisure time to ponder about things, some people began to speculate about the nature and properties of numbers. This curiosity developed into a sort of number-mysticism or numerology, and even today numbers such as 3,7, 11 and 13 are considered omens of good or bad luck.

Numbers were used for keeping records and for commercial transactions for over 5000 years before any one thought of studying numbers themselves in a systematic way. The first scientific approach to the study of integers, that is, the true origin of the theory of numbers, is generally attributed to the Greeks. Around 600 BC, Pythagoras and his disciples made rather thorough studies of the integers. They were the first to classify integers in various ways: Even numbers, odd numbers, prime numbers, composite numbers.

A prime number is a number greater than 1 whose only divisors are 1 and the number itself. Numbers that are not prime are called composite numbers, except that the number 1 is neither prime nor composite.

The Pythagoreans also linked numbers with geometry. They introduced the idea of polygonal numbers: triangular numbers, square numbers, pentagonal numbers, etc. The reason for this geometrical nomenclature is clear: when the numbers are represented by dots arranged in the form of triangles, squares, pentagons, etc. …E.g.: Triangular numbers: 1, 3, 6, 10, 15, 21, 28, ….; square numbers: 1, 4, 9, 16, 25, 36, ….; pentagonal numbers: 1, 5, 12, 22, 35, 51, 70, ….

Another link with geometry came from the famous Theorem of Pythagoras which states that in any right triangle the square of the length of the hypotenuse is the sum of the squares of the lengths of the two legs. The Pythagoreans were interested in right triangles whose sides are integers. Such triangles are called Pythagorean triangles. The corresponding triple of numbers (x,y,z) representing the lengths of the sides is called a Pythagorean triple. Example (3,4,5)

A Babylonian tablet had been found dating from about 1700 BC, which contains an extensive list of Pythagorean triples, some of the numbers being quite large. The Pythagoreans were the first to give a method for determining infinitely many triples. In modern notation, it can be described as follows:

x=n, y=\frac{1}{2}(n^{2}-1), \frac{1}{2}(n^{2}+1);

the resulting triple (x,y,z) will always be a Pythagorean triple with z=y+1.

Here are some examples:

(3,4,5), (5,12,13), (7,24,25), (9,40,41), (11,60,61), (13,84,85), (15,112, 113), (17,144, 145), (19,180, 181)

There are other Pythagorean triples besides these, for example:

(8,15,17), (12,35,37), (16,63, 65), (20,99,101)

In these examples, we have z=y+2. Plato had found a method for determining all these triples : in modern notation, they are given by the formulas:

x=4n, y=4n^{2}-1, z=4n^{2}+1

Around 300 BC, an important event occurred in the history of mathematics. The appearance of Euclid’s Elements,a collection of 13 books, transformed mathematics from numerology into a deductive science. Euclid was the first person to present mathematical facts along with rigorous proofs of these facts. Three of the thirteen books were devoted to theory of numbers (books VII, IX and X). In book IX Euclid proved that there are infinitely many primes. His proof is still taught in the classroom today. In Book X, he gave a method for obtaining all Pythagorean triples although he gave no proof that his method did, indeed, give them all. The method can be summarized by the formulas:

x=t(a^{2}-b^{2}), y=2tab, z=t(a^{2}+b^{2}),

where t, a, b are arbitrary positive integers such that a>b, a and b have no prime factors in common, and one of a or b is odd, the other even.

Euclid also made an important contribution to another problem posed by the Pythagoreans —- that of finding all perfect numbers. The number 6 was called a perfect number because 6=1+2+3, the sum of all its proper divisors (that is, the sum of divisors less than 6). Another example of a perfect number is 28 because 28=1+2+4+7+14, and 1, 2, 4, 7 and 14 are the divisors of 28 less than 28. The Greeks referred to the proper divisors of a number as its “parts.” They called 6 and 28 perfect numbers because in each case the number is equal to to the sum of all its parts.

In Book IX, Euclid found all even perfect numbers. He proved that an even number is perfect if it has the form:


where both p and 2^{p}-1 are primes.

Two thousand years later, Euler proved the converse of Euclid’s theorem. That is, every even perfect number must be of Euclid’s type. For example, for 6 and 28, we have:

6=2^{2-1}(2^{2}-1) = 2 \times 3 and 28=2^{3-1}(2^{3}-1)= 4 \times 7/

The first five even perfect numbers are

6,28,496,8128 and 33,550,336.

Perfect numbers are very rare indeed. At the present time (1975) only 24 perfect numbers are known. They correspond to the following values of p in Euclid’s formula:

2,3,5,7,13,17,19,31,61, 89,107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937.

Numbers of the form 2^{p}-1, where p is a prime, are now called Mersenne numbers and are denoted by M_{p} in honour of Mersenne, who studied them in 1644. It is known that M_{p} is prime for the 24 primes listed above and composite for all other values of p \leq 257, except for possibly

p=157,167, 193, 199, 227, 229

for these it it not yet (1975) known whether M_{p} (PS: you can google and find out the status now) is prime or composite.

No odd perfect numbers are known, it is not even known if any exist. But, if any do exist they must be very large; in fact, greater than 10^{50}.

We turn now to a brief description of the history of theory of numbers since Euclid’s time.

After Euclid in 300 BC, no significant advances were made in number theory until about 250 AD when another Greek mathematician, Diophantus of Alexandria, published 13 books, six of which have been preserved. This was the first Greek work to make systematic use of algebraic symbols. Although his algebraic notation seems awkward by present-day standards, Diophantus was able to solve certain algebraic equations involving two or three unknowns. Many of his problems originated from number theory and it was natural for him to seek integer solutions of equations. Equations to be solved with integer values are now called Diophantine equations, and the study of such equations is known as Diophantine analysis. The equation x^{2}+y^{2}=z^{2} for Pythagorean triples is an example of a Diophantine equation.

After Diophantus, not much progress was made in the theory of numbers until the seventeenth century, although there is some evidence that the subject began to flourish in the Far East — especially in India — in the period between AD 500 and AD 1200.

In the seventeenth century the subject was revived in Western Europe, largely through the efforts of a remarkable French mathematician, Pierre de Fermat (1601-1665), who is generally acknowledged to be the father of modern number theory. Fermat derived much of his inspiration from the works of Diophantus. He was the first to discover really deep properties of the integers. For example, Fermat proved the following surprising theorems:

Every integer is either a triangular number or a sum of 2 or 3 triangular numbers; every integer is either a square or sum of 2, 3, or 4 squares; every integer is either a pentagonal number or the sum of 2, 3, 4 or 5 pentagonal numbers, and so on.

Fermat also discovered that every prime number of the form 4n+1 such as 5, 13, 17, 29, 37, 41, etc. is a sum of two squares. For example,

5=1^{2}+2^{2}; 13=2^{2}+3^{2}; 17=1^{2}+4^{2}; 29=2^{2}+5^{2}; 37=1^{2}+6^{2}; 41=4^{2}+5^{2}

Shortly, after Fermat’s time, the names of Euler (1707-1783), Lagrange (1736-1813), Legendre (1752-1833), Gauss (1777-1855), and Dirichlet (1805-1859) became prominent in the further development of the subject. The first textbook in number theory was published by Legendre in 1798. Three years later Gauss published Disquisitiones Arithmeticae, a book which transformed the subject into a systematic and beautiful science. Although he made a wealth of contributions to other branches of mathematics, as well as to other sciences, Gauss himself considered his book on number theory to be his greatest work.

In the last hundred years or so since Gauss’s time there has been an intensive development of the subject in many different directions. It would be impossible to give in a few pages a fair cross-section of the types of problems that are studied in the theory of numbers. The field is vast and some parts require a profound knowledge of higher mathematics. Nevertheless, there are many problems in number theory which are very easy to state. Some of these deal with prime numbers, and we denote the rest of this introduction to such problems.

The primes less than 100 have been listed above. A table listing all primes less than 10 million was published in 1914 by an American mathematician, D. N. Lehmer. There are exactly 664579 primes less than 10 million, or about 6.5 %. Later, D. H. Lehmer (the son of D. N. Lehmer) calculated the total number of primes less than 10 billion; there are exactly 455052512 such primes, or about 4.5% although all these primes are not known individually.

A close examination of a table of primes reveals that they are distributed in a very irregular fashion. The tables show long gaps between primes. For example, the prime 370261 is followed by 111 composite numbers. There are no primes between 20831323 and 20831533. It is easy to prove that arbitrarily large gaps between prime numbers must eventually occur.

On the other hand, the tables indicate that consecutive primes, such as 3 and 5, or 101 and 103, keep recurring. Such pairs of primes, which differ only by 2 are known as twin primes. There are over 1000 such pairs below 100000 and over 8000 below 1000000. The largest pair known to date (around 1975 AD) is 76.3^{139}-1 and 76.3^{139}+1. Many mathematicians think there are infintely many such pairs, but no one has been able to prove (I think the advanced reader can refer to Google to see the progress in work on twin primes: the work of Dr. Yitang Zhang; I think Dr. Terence Tao also did some further work based on it. Refer to

One of the reasons for this irregularity in distribution of primes is that no simple formula exists for producing all the primes. Some formulas do yield many primes. For example, the expression:


gives a prime for x=0, 1, 2, \ldots, 40, whereas


gives a prime for x=0,1,2, \ldots, 79. However, no such simple formula can give a prime for all x, even if cubes and higher powers are used. In fact, in 1752 Goldbach proved that no polynomial in x with integer coefficient can be prime for all x, or even for all sufficiently large x.

Some polynomials represent infinitely many primes. For example, as x runs through the integers 0, 1, 2, 3, ….the linear polynomial


gives all the odd numbers, hence, infinitely many primes. Also, each of the polynomials

4x+1 and 4x+3

represent infinitely many primes. In a famous memoir published in 1837, Dirichlet proved that, if a and b are positive integers with no prime factors in common, the polynomial


gives infinitely many primes as x runs through all the positive integers. The result is now known as Dirichlet’s theorem on the existence of primes in a given arithmetical progression.

To prove the theorem, Dirichlet went beyond the realm of integers and introduced tools of analysis such as limits and continuity. By so doing, he laid the foundations for a new branch of mathematics called analytic number theory, in which ideas and methods of real and complex analysis are brought to bear on problems about integers.

It is not known if there is any quadratic polynomial ax^{2}+bx+c with a \neq 0 which represents infinitely many primes. However, Dirichlet had used his powerful analytic methods to prove that, if a, 2b, and c have no prime factor in common, the quadratic polynomial in two variables


represents infinitely many primes as x and y run through positive integers.

Fermat thought that the formula 2^{2^{n}}+1 would always give a prime for n=0,1,2,.... These numbers are called Fermat numbers and are denoted by F_{n}. The first five are

F_{0}=1, F_{1}=5, F_{2}=17, F_{3}=257, F_{4}=65537

and they are all primes. However, in 1732 A.D., Euler found that F_{5} is composite. In fact,

F_{5} = 2^{32}+1= (641)(6700417)

These numbers are also of interest in plane geometry. Gauss had proved that if F_{n} is prime, say F_{n}=p, then a regular polygon of p sides can be constructed with straight edge and compass.

Beyond F_{5}, no futher Fermat primes have been found. (Please check this in Google. This is the author’s claim as of 1975 A.D.) In fact, for 5 \leq n \leq 16 each Fermat number F_{n} is composite. Also, F_{n} is known to be composite for the following further isolated values of n:

n=18,19,21, 23,25,26,27,30, 32, 36, 38, 39, 42, 52, 55, 58, 63,73,77,81,117, 125, 144, 150, 207, 226, 228, 260, 267, 268, 284, 316, 452, 1945.

The greatest known Fermat composite F_{1945} (till 1975 AD) has more than 10^{582} digits, a number larger than the number of letters in the Los Angeles and New York telephone directories combined (then in 1975 AD).

It was mentioned earlier that there is no simple formula that gives all the primes. In this connection, we should mention a result discovered in 1947 A.D. by an American mathematician, W. H. Mills. He proved that there is some number A, greater than 1 but not an integer, such that

[A^{3^{x}}] is prime for all x = 1, 2, 3…

Here, [A^{3^{x}}] means the greatest integer \leq A^{3^{x}}. Unfortunately no one knows what A is. (Again the reader can check the latest about this in Google).

The foregoing results illustrate the irregularity of the distribution of the prime numbers. However, by examining large blocks of primes one finds that their average distribution seems to be quite regular. Although there is no end to the primes, they become more widely spread, on the average, as we go further and further in the table. The question of the diminishing frequency of primes was the subject of much speculation in the early nineteenth century. To study this distribution, we consider a function, denoted by \pi{(x)}, which counts the number of primes less than or equal to x. Thus,

\pi{(x)} = the number of primes p satisfying 2 \leq p \leq x.

Here is a brief table of this function and its comparison with \frac{x}{\ln{x}}.

\begin{array}{cccc} x & \pi{(x)} & \frac{x}{\ln{(x)}} & \frac{\pi{(x)}}{\frac{x}{\ln{(x)}}} \\ 10 & 4 & 4.3 & 0.93 \\ 100 & 25 & 21.7 & 1.15 \\ 1000 & 168 & 144.9 & 1.16 \\ 10000 & 1229 & 1086 & 1.11 \\ 100000 & 9592 & 8686 & 1.10 \\ 1000000 & 78498 & 72464 & 1.08 \\ 10000000 & 664579 & 621118 & 1.07 \\ 100000000 & 5761455 & 5434780 & 1.06 \\ 1000000000 & 50847534 & 48309180 & 1.05 \\ 10000000000 & 455052512 & 434294482 & 1.048 \end{array}

By examining a table like this for x \leq 10^{6}, Gauss and Legendre proposed independently that for large x, the ratio


was nearly 1 and they conjectured that this ratio would approach 1 as x approaches \infty. Both Gauss and Legendre attempted to prove this statement but did not succeed. The problem of deciding the truth or falsehood of this conjecture attracted the attention of eminent mathematicians for nearly 100 years.

In 1851 A.D. the Russian mathematician Chebyshev made an important step forward by proving that if the ratio did tend to a limit, then this limit must be 1. However, he was unable to prove that the ratio does tend to a limit.

In 1859, Riemann attacked the problem with analytic methods, using a formula discovered by Euler in 1737 which relates the prime numbers to the function

\zeta{(s)} = \Sigma_{n=1}^{\infty}\frac{1}{n^{s}} for real s greater than 1.

Riemann considered complex values of s and outlined an ingenious method for connecting the distribution of primes to properties of the function \zeta{(s)}. The mathematics needed to justify all the details of his method had not yet been fully developed and Riemann was unable to completely settle the problem before his death in 1866.

Thirty years later the necessary analytic tools were at hand and in 1896 J. Hadamard and and C. J. de la Vallee Poussin independently and almost simultaneously succeeded in proving that

\lim_{n \rightarrow \infty} \frac{\pi{(x)}\ln{(x)}}{x}=1.

This remarkable result is called the prime number theorem, and its proof was one of the crowning achievements of analytic number theory.

In1949, two contemporary mathematicians, Atle Selberg and Paul Erdos caused a sensation in the mathematical world when they discovered an elementary proof of the prime number theorem. Their proof, though very intricate, makes no use of \zeta{(s)} nor of complex function theory and in principle is accessible to anyone familiar with elementary calculus.

One of the most famous problems concerning prime numbers is the so-called Goldbach conjecture (again please refer to Google for the latest reseach results on this). In 1742 A.D., Goldbach wrote to Euler suggesting that every even number greater than or equal to 4 is a sum of two primes. For example,

4=2+2; 6=3+3; 8=3+5; 10=3+7=5+5; 12=5+7

This conjecture is undecided to this day (again, please google for twin prime conjecture, Yitang Zhang and Terence Tao etc.), although it might be true as per the progress suggested. Now, why do mathematicians think it is probably true if they haven’t been able to prove it? First of all, the conjecture has been verified by actual computation for all even numbers less than 33 \times 10^{6}. It has been found that every even number greater than 6 and less than 33 \times 10^{6} is, in fact, not only the sum of two odd primes but the sum of two distinct odd primes. But, in number theory verification of a few thousand cases is not enough evidence to convince mathematicians that something is probably true. For example, all the odd primes fall into two categories, those of the form 4n+1 and those of the form 4n+3. Let \pi_{1}{(x)} denote all the primes less than or equal to x that are of the form 4n+1 and let \pi_{3}{(x)} denote the number that are of the form 4n+3. It is known that there are infinitely many primes of both types. By computation, it was found that \pi_{(x)} \leq \pi_{3}{(x)} for all x \leq 26861. But, in 1957, J. Leech found that for x=26861, we have \pi_{1}{(x)}=1473 and \pi_{3}{(x)}=1472, so the inequality was reversed. In 1914, Littlewood had proved that this inequality reverses back and forth infinitely often. That is, there are infinitely many x for which \pi_{1}{(x)} < \pi_{3}{(x)} and infinitely many x for which \pi_{3}{(x)} < \pi_{1}{(x)}. Conjectures about prime numbers can be erroneous even if they are verified by computations in thousands of cases.

Therefore, the fact that Goldbach’s conjecture has been verified for all even numbers less than 33 \times 10^{6} is only a tiny bit of evidence in its favour.

Another way that mathematicians collect evidence about the truth of a particular conjecture is by proving other theorems which are somewhat similar to the conjecture. For example, in 1930 the Russian mathematician Schnilrelmann proved that there is a number M such that every number n from some point on is a sum of M or lower primes:

n=p_{1}+p_{2}+p_{3}+\ldots+p_{n} for sufficiently large n

If we know that M were equal to 2 for all even n, this would prove Goldbach’s conjecture for all sufficiently large n. In 1956 A.D., the Chinese mathematician Yin Wen-Lin proved that M \leq 18. That is, every number n from some point on is a sum of 18 or fewer primes. Schnilrelmann’s result is considered a giant step toward a proof of Goldbach’s conjecture. It was the first real progress made on this problem in nearly 200 years.

A much closer approach to a solution of Goldbach’s problem was made in 1937 by another Russian mathematician, I. M. Vinogradov, who proved that from some point on every odd number is the sum of three primes:

n=p_{1}+p_{2}+p_{3} when n is odd, n is sufficiently large

In fact, this is true for all odd n greater than 3^{3^{15}}. To date (1975 A.D.) this is the strongest piece of evidence in favour of Goldbach’s conjecture. For one thing, it is easy to prove that Vinogradov’s theorem is a consequence of Goldbach’s statement. That is, if Goldbach’s conjecture is true, then it is easy to deduce Vinogradov’s statement. The big achievement of Vinogradov was that he was able to prove his result without using Goldbach’s statement. Unfortunately, no one has been able to work it the other way around and prove Goldbach’s statement from Vinogradov’s.

Another piece of evidence in favour of Goldbach’s conjecture was found in 1948 by the Hungarian mathematician Renyi who proved that there is a number M such that every sufficiently large even number n can be written as a prime plus another number which has no more than M prime factors:


where A has no more than M prime factors (n even, n sufficiently large). If we know that M=1, then Goldbach’s conjecture would be true for all sufficiently large n. In 1965 A.D., A. A. Buhstab and A. I. Vinogradov proved that M \leq 3, and in 1966 Chen Jing-run proved that M \leq 2.

We conclude this introduction with a brief mention of some outstanding unsolved problems (till date 1975 A.D.) concerning prime numbers:

  1. Goldbach’s problem: Is there an even number greater than 2 which is not the sum of two primes?
  2. Is there an even number greater than 2 which is not the difference of two primes?
  3. Are there infinitely many twin primes?
  4. Are there infinitely many Mersenne primes, that is, primes of the form 2^{p}-1 where p is prime?
  5. Are there infinitely many composite Mersenne numbers?
  6. Are there infintely many Fermat primes, that is, primes of the form 2^{2^{p}}+1?
  7. Are there infinitely many composite Fermat numbers?
  8. Are there infinitely many primes of the form x^{2}+1, where x is an integer? (It is known that there are infinitely many of the form x^{2}+y^{2}, and of the form x^{2}+y^{2}+1, and of the form x^{2}+y^{2}+z^{2}+1.)
  9. Are there infinitely many primes of the form x^{2}+k, where k is given?
  10. Does there always exist at least one prime between n^{2} and (n+1)^{2} for every integer n \geq 1?
  11. Does there always exist at least one prime between n^{2} and n^{2}+n for every integer n>1?
  12. Are there infinitely many primes whose digits (in base 10) are all ones? (Here are two examples: 11 and 11,111,111,111,111,111,111,111)

The professional mathematician is attracted to number theory because of the way all the weapons of modern mathematics can be brought to bear on its problems. As a matter of fact, many important branches of mathematics had their origin in number theory. For example, the early attempts to prove the prime number theorem stimulated the development of the theory of functions of a complex variable especially the theory of entire functions. Attempts to prove that the Diophantine equation x^{n}+y^{n}=z^{n} has no non-trivial solution if n greater than or equal to three (Fermat’s conjecture or Fermat’ s Last Theorem (this has been proved by Sir Andrew Wiles in 1995, Princeton University) led to the development of algebraic number theory, one of the most active areas of modern mathematical research. (1975 A.D. comment by Prof Tom Apostol: Even though Fermat’s conjecture is still undecided, this seems unimportant by comparison to the vast amounts of valuable mathematics that has been created as a result of work on this conjecture.) Another examples has been the theory of partitions which has been an important factor in the development of combinatorial analysis and in the study of modular functions.

There are hundreds of unsolved problems in number theory. New problems arise more rapidly than the old ones are solved, and many of the old ones have remained unsolved for centuries. As the mathematician Sierpinski once said, “…the progress of our knowledge of numbers is advanced not only by what we already know about them, but also by realizing what we yet do not know about them.”

Note: More References:

  1. History of the Theory of Numbers Volumes I, II, III: Dickson
  2. Reviews in Number Theory by LeVeQue, Volumes I, II, III, IV, V, VI.

Happy reading. I hope it arouses tremendous passion/curiosity among some readers to consider number theory as a possible professional option.


Nalin Pithwa

Number theory: let’s learn it the Nash way !

Reference: A Beautiful Mind by Sylvia Nasar.

Comment: This is approach is quite similar to what Prof. Joseph Silverman explains in his text, “A Friendly Introduction to Number Theory.”

Peter Sarnak, a brash thirty-five-year-old number theorist whose primary interest is the Riemann Hypothesis, joined the Princeton faculty in the fall of 1990. He had just given a seminar. The tall, thin, white-haired man who had been sitting in the back asked for a copy of Sarnak’s paper after the crowd had dispersed.

Sarnak, who had been a student of Paul Cohen’s at Stanford, knew Nash by reputation as well as by sight, naturally. Having been told many times Nash was completely mad, he wanted to be kind. He promised to send Nash the paper. A few days later, at tea-time, Nash approached him again. He had a few questions, he said, avoiding looking Sarnak in the face. At first, Sarnak just listened politely. But within a few minutes, Sarnak found himself having to concentrate quite hard. Later, as he turned the conversation over in his mind, he felt rather astonished. Nash had spotted a real problem in one of Sarnak’s arguments. What’s more, he also suggested a way around it. “The way he views things is very different from other people,” Sarnak said later. ‘He comes up with instant insights I don’t know I would ever get to. Very, very outstanding insights. Very unusual insights.”

They talked from time to time. After each conversation, Nash would disappear for a few days and then return with a sheaf of computer printouts. Nash was obviously very, very good with the computer. He would think up some miniature problem, usually very ingeniously, and then play with it. If something worked on a small scale, in his head, Sarnak realized, Nash would go to the computer to try to find out if it was “also true the next few hundred thousand times.”

{What really bowled Sarnak over, though, was that Nash seemed perfectly rational, a far cry from the supposedly demented man he had heard other mathematicians describe. Sarnak was more than a little outraged. Here was this giant and he had been all but forgotten by the mathematics profession. And the justification for the neglect was obviously no longer valid, if it had ever been.}


Nalin Pithwa

PS: For RMO and INMO (of Homi Bhabha Science Foundation/TIFR), it helps a lot to use the following: (it can be used with the above mentioned text of Joseph Silverman also): TI nSpire CAS CX graphing calculator.

Find a flaw in this proof: RMO and PRMO tutorial

What ails the following proof that all the elements of a finite set are equal?

The following is the “proof”;

All elements of a set with no elements are equal, so make the induction assumption that any set with n elements has all its elements equal. In a set with n elements, the first and the last n are equal by induction assumption. They overlap at n, so all are equal, completing the induction.

End of “proof:


Nalin Pithwa

Number theory : A set of friendly examples

Even and odd numbers

Two whole numbers are added together. If their sum is odd, which statements below are
always true? Which are always false? Which are sometimes true and sometimes false?
1 Their quotient is not a whole number.
2 Their product is even.
3 Their difference is even.
4 Their product is more than their sum.
5 If 1 is added to one of the numbers and the product is found, it will be even.
The Collatz conjecture
Choose any whole number to start with.

If it is odd, multiply it by 3 and then add 1.
If it is even, divide it by 2. Then repeat this process on the number just obtained. Keep repeating the procedure.

For example, if you start with 58, the resulting chain of numbers is
58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, …

The Collatz conjecture, made by Lothar Collatz in 1937, claims that, if you repeat this
process over and over, starting with any whole number greater than zero, eventually you will finish up with the sequence … 4, 2, 1, 4, 2, 1.

A conjecture is a statement that is thought to be true but has not been proved mathematically to be true for all cases. Although the Collatz conjecture has been shown to work − often very quickly − for many whole numbers, there are some quite small numbers that take a very long time to come down to … 4, 2, 1, 4, 2, 1.Apply this process to all the whole numbers greater than zero and less than or equal to 30.
For each one, find:
• how many steps it takes to reach 1 the frst time
• the largest number in the sequence. (For the sequence above, 58 takes 19 steps and reaches a maximum of 88.)
Look for shortcuts and work with a partner if you like.

Long division
Here is a way to check how good your long division skills are. If you are able to follow it
through and get to the end without making a mistake, you can consider yourself a qualiꏨed long division champion.
• Start with any two-digit number (for example, 58). Write it three times so that a six-digit  number is formed (585 858).

  • Divide this number by 21. There should not be any remainder. If there is, try and find out where you made your mistake and fix it.
    • Now divide this new four- or possibly five-digit number by 37. Once again, there should be no remainder.
    • Finally, divide this number − which should by now have only three or four digits − by 13.
    You will know if you got it right by looking at the number you are left with.
    Explain why this exercise works.
    (Doing any of this exercise on a calculator is still interesting but is de뀠nitely wimping out!)

Totient numbers

1 A totient number is the number of fractions between 0 and 1 (not including 0 or 1) for
a given denominator that cannot be reduced to a simpler equivalent fraction. The totient
number of 2 is 1, since we have \frac{1}{2}; of 3 it is 2, since we have \frac{1}{3} and \frac{2}{3}; and of 4 it is also 2, since we have \frac{1}{4}
and \frac{3}{4} (\frac{2}{4} can be reduced to \frac{1}{2}). The totient number of 5 is 4, since we have \frac{1}{5}, \frac{2}{5}, \frac{3}{5}, \frac{4}{5}; and of 6 it is 2, since we have \frac{1}{5} and
\frac{5}{6}. Find the totient numbers forall denominators up to 12.

2 For any denominator n, there are n fractions between 0 and 1 (including 0 but not 1). Of
these fractions, some will be counted towards the totient number of n, but others will
cancel down and count towards the totient number of one of the factors of n. Using this
information and the totient numbers from the previous question, calculate the totient
numbers for 15, 18, 20 and 24.

3 The totient number is related to the prime factors of the original number, since these will
determine which fractions can be cancelled. Using this information, calculate the totient numbers of 72, 81, 98 and 100.

\bf{Last \hspace{0.1in}Digits \hspace{0.1in} of \hspace{0.1in}powers}
\bf{Square \hspace{0.1in}Numbers}

Without using a calculator, can you say which of this set of numbers could not be square numbers?

8116801, 251301659, 3186842, 20720704.

You can just by checking the last digit (units digit) of each number.

Do a bit of experimentation with a calculator and find the four digits that square numbers end in. (This eliminates the third number in this set).

Now check out the pairs of digits that your odd square numbers end with. What digits are possible in the tens position of an odd square number? (This number eliminates the second number in the set).

Complete these sentences with what you have discovered:

* In a square number, the last digit (units digit) can only be _____, _______, _______, _______, _______ or _______.
* The second last digit (tens place) of an odd square number is always _______.

\bf{Cube \hspace {0.1in} Numbers}

Cube numbers behave rather differently.

A bit of experimentation will show that cube numbers can end in ANY digit (units place). This digit depends on the last digit (units place) of the original number being cubed.

Complete this table:
\left| \begin{array}{cc}     \mbox {if a number ends in} & \mbox{its cube will end in}\\ 0 & \\ 1 & \\ 2 & \\ 3 & \\ 4 & \\ 5 & \\ 6 & \\ 7 & \\ 8 & \\ 9 & \end{array}\right|

\bf{Fourth \hspace{0.1in}Powers}

Fourth powers are in fact just square numbers that have been squared. For example, 7^{4}=7^{2} \times 7^{2}= 49^{2}=2401.

Since 4^{2}=16 and 9^{2}=81, the last digit of a fourth power can only be 0, 1, 5 or 6.

\bf{Fifth \hspace{0.1in}powers}

Fifth powers have a magic of their own. Do a bit of experimentation to find out what it is. In p, particular, I suggest you create tables of second powers, third powers, fourth powers and fifth powers of all numbers from zero to 20. Check, compare…actually, it is fun to “compare rate of growth of powers with increasing integers”…this idea involves rudimentary ideas of calculus…

\bf{Obstinate \hspace{0.1in} numbers}

An odd number can usually be written as a sum of a prime number and another number, which is a power of two. This is true for all odd numbers greater than one but less than 100.

For example, if we choose 23, we can say that it is equal to 23=19 + 2^{2}. There is one more way to represent 23: it is 7 + 2^{4}. So, there are two ways to represent 23 as a sum of a prime number and a power of two. But, 21+2^{1} and 15+2^{3} do not work as both 21 and 15 are not prime numbers.

Some odd numbers like this can be expressed in many ways.

Try to find various representations as sum(s) of prime number and a power(s) of two of the following integers: 45, 29, 59, 95.

If you are adventurous or courageous, try to find such representations of all odd numbers lying from 1 to 100. You need a lot of patience and stamina and grit…but you will develop an “intuitive feel or tactile feel for numbers”…that’s the way math begins…

There are some odd numbers which cannot be expressed as a sum of a prime number and a power of two. Such numbers are called \bf{obstinate \hspace{0.1in} numbers}.

An example of an obstinate number is \bf{251} as the working below shows:

251-2^{1}=249=3 \times 83

251-2^{2}=247=13 \times 19

251-2^{3}=243=3 \times 81

251-2^{4}=235= 5 \times 47

251-2^{5}=219= 3 \times 73

251-2^{6}= 187= 11 \times 17

251-2^{7}=123=3 \times 41

The next power of 2 is 2^{8}=256, which is clearly greater than 251. Hence, 251 is an obstinate number.

In fact, 251 is the third obstinate number. The first two lie between 100 and 150. Find these two odd numbers keeping track of how you eliminated the other twenty three odd numbers between 100 and 150.

\it{Remember \hspace{0.1in} to \hspace{0.1in} be \hspace{0.1in} systematic \hspace{0.1in}}.

Making a list of the powers of two up to 2^{8} might be a good place to start with. Look for short cuts and patterns as you proceed further.

Have fun with numbers !!

Nalin Pithwa.

Some Number Theory Questions for RMO and INMO

1) Let n \geq 2 and k be any positive integers. Prove that (n-1)^{2}\mid (n^{k}-1) if and only if (n-1) \mid k.

2) Prove that there are no positive integers a, b, n >1 such that (a^{n}-b^{n}) \mid (a^{n}+b^{n}).

3) If a and b>2 are any positive integers, prove that 2^{a}+1 is not divisible by 2^{b}-1.

4) The integers 1,3,6,10, \ldots, n(n+1)/2, …are called the triangular numbers because they are the numbers of dots needed to make successive triangular arrays of dots. For example, the number 10 can be perceived as the number of acrobats in a human triangle, 4 in a row at the bottom, 3 at the next level, then 2, then 1 at the top. The square numbers are 1, 4, 9, \ldots, n^{2}, \ldots The pentagonal numbers 1, 5, 12, 22, \ldots, (3n^{2}-n)/2, \ldots, can be seen in a geometric array in the following way: Start with n equally spaced dots P_{1}, P_{2}, \ldots, P_{n} on a straight line in a plane, with distance 1 between consecutive dots. Using P_{1}P_{2} as a base side, draw a regular pentagon in the plane. Similarly, draw n-2 additional regular pentagons on base sides P_{1}P_{3}, P_{1}P_{4}, \ldots, P_{1}P_{n}, all pentagons lying on the same side of the line P_{1}P_{n}. Mark dots at each vertex and at unit intervals along the sides of these pentagons. Prove that the total number of dots in the array is (3n^{2}-n)/2. In general, if regular k-gons are constructed on the sides P_{1}P_{2}, P_{1}P_{3}, …, P_{1}P_{n}, with dots marked again at unit intervals, prove that the total number of dots is 1+kn(n-1)/2 -(n-1)^{2}. This is the nth k-gonal number.

5) Prove that if m>n, then a^{2^{n}}+1 is a divisor of a^{2^{m}}-1. Show that if a, m, n are positive with m \neq n, then

( a^{2^{m}}+1, a^{2^{n}}+1) = 1, if a is even; and is 2, if a is odd.

6) Show that if (a,b)=1 then (a+b, a^{2}-ab+b^{2})=1 or 3.

7) Show that if (a,b)=1 and p is an odd prime, then ( a+b, \frac{a^{p}+b^{p}}{a+b})=p or 1.

8) Suppose that 2^{n}+1=xy, where x and y are integers greater than 1 and n>0. Show that 2^{a}\mid (x-1) if and only if 2^{a}\mid (y-1).

9) Prove that (n!+1, (n+1)!+1)=1.

10) Let a and b be positive integers such that (1+ab) \mid (a^{2}+b^{2}). Show that the integer (a^{2}+b^{2})/(1+ab) must be a perfect square.

Note that in the above questions, in general, (a,b) means the gcd of a and b.

More later,
Nalin Pithwa.

Fermat-Kraitchik Factorization Method for factoring large numbers: training for RMO

Reference: Elementary Number Theory, David M. Burton, 6th Edition.

In a fragment of a letter in all probability to Father Marin Mersenne in 1643, Fermat described a technique of his for factoring large numbers. This represented the first real improvement over the classical method of attempting to find a factor of n by dividing by all primes not exceeding \sqrt{n}. Fermat’s factorization scheme has at its heart the observation that the search for factors of an odd integer n (because powers of 2 are easily recognizable and may be removed at the outset, there is no loss in assuming that n is odd) is equivalent to obtaining integral solutions of x and y of the equation n = x^{2} - y^{2}.

If n is the difference of two squares, then it is apparent that n can be factored as n = x^{2}-y^{2} = (x+y)(x-y).

Conversely, when n has the factorization n=ab, with a \geq b \geq 1, then we may write n = (\frac{a+b}{2})^{2}-(\frac{a-b}{2})^{2}

Moreover, because n is taken to be an odd integer, a and b are themselves odd, hence, \frac{a+b}{2} and \frac{a-b}{2} will be nonnegative integers.

One begins the search for possible x and y satisfying the equation n=x^{2}-y^{2} or what is the same thing, the equation x^{2}-n=y^{2} by first determining the smallest integer k for which k^{2} \geq n. Now, look successively at the numbers k^{2}-n, (k+1)^{2}-n, (k+2)^{2}-n, (k+3)^{2}-n, \ldots until a value of m \geq n is found making m^{2}-n a square. The process cannot go on indefinitely, because we eventually arrive at (\frac{n+1}{2})^{2}-n=(\frac{n-1}{2})^{2} the representation of n corresponding to the trivial factorization n=n.1. If this point is reached without a square difference having been discovered earlier, then n has no other factors other than n and 1, in which case it is a prime.

Fermat used the procedure just described to factor 2027651281=44021.46061 in only 11 steps, as compared with making 4580 divisions by the odd primes up to 44021. This was probably a favourable case designed on purpose to show the chief virtue of this method: it does not require one to know all the primes less than \sqrt{n} to find factors of n.


To illustrate the application of Fermat’s method, let us factor the integer n=119143. From a table of squares, we find that 345^{2}<119143<346^{2}; thus it suffices to consider values of k^{2}-119143 for those k that satisfy the inequality 346 \leq k < (119143+1)/2=59572. The calculations begin as follows:








This last line exhibits the factorization 119143=352^{2}-69^{2}=(352+69)(352-69)=421.283, where both the factors are prime. In only seven steps, we have obtained the prime factorization of the number 119143. Of course, one does not always fare so luckily — it may take many steps before a difference turns out to be a square.

Fermat’s method is most effective when the two factors of n are of nearly the same magnitude, for in this case, a suitable square will appear quickly. To illustrate, let us suppose that n=233449 is to be factored. The smallest square exceeding n is 154^{2} so that the sequence k^{2}-n starts with:


155^{2}-23449=24025-23449=576=24^{2}. Hence, the factors of 23449 are 23449=(155+24)(155-24)=131

When examining the differences k^{2}-n as possible squares, many values can be immediately excluded by inspection of the final digits. We know, for instance, that a square must end in one of the six digits 0,1,4,5,6,9. This allows us to exclude all the values in the above example, save for 1266, 1961, 4761. By calculating the squares of the integers from 0 to 99 modulo 100, we see further that, for a square, the last two digits are limited to the following 22 possibilities:

00; 01, 04; 09; 16; 21; 24; 25; 29; 36; 41; 44; 49; 56; 61; 64; 69; 76; 81; 84; 89; 96.

The integer 1266 can be eliminated from consideration in this way. Because 61 is among the last two digits allowable in a square, it is only necessary to look at the numbers 1961 and 4761; the former is not a square, but 4761=69^{2}.

There is a generalization of Fermat’s factorization method that has been used with some success. Here, we look for distinct integers x and y such that x^{2}-y^{2} is a multiple of n rather than n itself, that is, x^{2} \equiv y^{2} \pmod {n}
Having obtained such integers d=gcd(x-y,n) (or, d=gcd(x+y,n)) can be calculated by means of the Euclidean Algorithm. Clearly, d is a divisor of n, but is it a non-trivial divisor? In other words, do we have 1<d<n?

In practice, n is usually the product of two primes p and q, with p<q so that d is equal to 1, p, q, or pq. Now, the congruence x^{2} \equiv y^{2} \pmod{n} translates into pq|(x-y)(x+y). Euclid's lemma tells us that p and q must divide one of the factors. If it happened that p|x-y and q|x-y, or expressed as a congruence x \equiv y \pmod{n}. Also, p|x+y and q|x+y yield x \equiv -y \pmod{n}. By seeking integers x and y satisfying x^{2} \equiv y^{2} \pmod{n}, where x \not\equiv \pm \pmod{n}, these two situations are ruled out. The result of all this is that d is either p or q, giving us a non-trivial divisor of n.


Suppose we wish to factor the positive integer n=2189 and happen to notice that 579^{2} \equiv 18^{2} \pmod{2189}. Then, we compute gcd(579-18,2189)=gcd(561,2189)=11 using the Euclidean Algorithm:


This leads to the prime divisor 11 of 2189. The other factor, namely 199, can be obtained by observing that gcd(579+18,2189)=gcd(597,2189)=199

The reader might wonder how we ever arrived at a number, such as 579, whose square modulo 2189 also turns out to be a perfect square. In looking for squares close to multiples of 2189, it was observed that 81^{2} -3.2189 = -6 and 155^{2}-11.2189=-54 which translates into 81^{2} \equiv -2.3 \pmod{2189} and 155^{2} \equiv -2.3^{3} \pmod{2189}.

When these congruences are multiplied, they produce (81.155)^{2} \equiv (2.3^{2})^{2} \pmod{2189}. Because the product 81.155 = 12555 \equiv -579 \pmod{2189}, we ended up with the congruence 579^{2} \equiv 18^{2} \pmod{2189}.

The basis of our approach is to find several x_{i} having the property that each x_{i}^{2} is, modulo n, the product of small prime powers, and such that their product’s square is congruent to a perfect square.

When n has more than two prime factors, our factorization algorithm may still be applied; however, there is no guarantee that a particular solution of the congruence x^{2} \equiv y^{2} \pmod{n}, with x \not\equiv \pm \pmod{n} will result in a nontrivial divisor of n. Of course, the more solutions of this congruence that are available, the better the chance of finding the desired factors of n.

Our next example provides a considerably more efficient variant of this last factorization method. It was introduced by *Maurice Kraitchik* in the 1920’s and became the basis of such modern methods as the *quadratic sieve algorithm*.


Let n=12499 be the integer to be factored. The first square just larger than n is 112^{2} = 12544. So. we begin by considering the sequence of numbers x^{2}-n for x=112, 113, \ldots. As before, our interest is in obtaining a set of values x_{1}, x_{2}, x_{3}, \ldots x_{k} for which the product (x_{1}-n)(x_{2}-n)\ldots (x_{k}-n) is a square, say y^{2}. Then, (x_{1}x_{2}\ldots x_{k})^{2} \equiv y^{2} \pmod{n}, which might lead to a non-factor of n.

A short search reveals that 112^{2}-12499=45; 117^{2}-12499=1190; 121^{2}-12499=2142; or, written as congruences, 112^{2} \equiv 3^{2}.5 \pmod{12499} ; 117^{2} \equiv \pmod{12499}; 121^{2} \equiv 2.3^{2}.7.17 \pmod{12499}. Multiplying these together results in the congruence: (112.117.121)^{2} \equiv (2.3^{2}.5.7.17)^{2} \pmod{12499}, that is, 1585584^{2} \equiv 10710^{2}\pmod{12499}. But, we are unlucky with this square combination. Because 1585584 \equiv 10710 \pmod{12499} only a trivial divisor of 12499 will be found. To be specific,



After further calculation, we notice that

113^{2} \equiv 2.5.3^{3} \pmod{12499}

127^{2} \equiv^{2} \pmod{12499}

which gives rise to the congruence (113.127)^{2} \equiv (2.3^{2}.5.11)^{2} \pmod{12499}.

This reduce modulo 12499 to 1852^{2} \equiv 990^{2} \pmod{12499} and fortunately, 1852 \not\equiv \pm {990}\pm\pmod{12499}. Calculating

gcd(1852-990,12499)=gcd(862,12499)=431 produces the factorization 12499 =29.431

Problem to Practise:

Use Kraitchik’s method to factor the number 20437.

Nalin Pithwa

Questions based on Wilson’s theorem for training for RMO

1(a) Find the remainder when 15! is divided by 17.
1(b) Find the remainder when 2(26!) is divided by 29.

2: Determine whether 17 is a prime by deciding if 16! \equiv -1 {\pmod 17}

3: Arrange the integers 2,3,4, …, 21 in pairs a and b that satisfy ab \equiv 1 {\pmod 23}.

4: Show that 18! \equiv -1 {\pmod 437}.

5a: Prove that an integer n>1 is prime if and only if (n-2)! \equiv 1 {\pmod n}.
5b: If n is a composite integer, show that (n-1)! \equiv 0 {\pmod n}, except when n=4.

6: Given a prime number p, establish the congruence (p-1)! \equiv {p-1} {\pmod {1+2+3+\ldots + (p-1)}}

7: If p is prime, prove that for any integer a, p|a^{p}+(p-1)|a and p|(p-1)!a^{p}+a

8: Find two odd primes p \leq 13 for which the congruence (p-1)! \equiv -1 {\pmod p^{2}} holds.

9: Using Wilson’s theorem, prove that for any odd prime p:
1^{2}.3^{2}.5^{2}.\ldots (p-2)^{2} \equiv (-1)^{(p+1)/2} {\pmod p}

10a: For a prime p of the form 4k+3, prove that either

(\frac{p-1}{2})! \equiv 1 {\pmod p} or (\frac{p-1}{2})! \equiv -1 {\pmod p}

10b: Use the part (a) to show that if 4k+3 is prime, then the product of all the even integers less than p is congruent modulo p to either 1 or -1.

More later,
Nalin Pithwa.