Proof of a Theorem
on Looking at Prime Numbers
by Leonhard Euler
Commentaries of the Academy of Science of St. Petersburg,
8 (1736), 141-146
Translation by C. Edward Sandifer
Formerly most of the arithmetic theorems of Fermat were given without proofs, and perhaps they were true, and not just exceptional properties of certain numbers; Still, the science of numbers is itself valid, and seeing what the limits of Analysis of numbers ought to be vigorously sought. Although he gave remarkable discoveries of many things in geometry, theorems he asserted which he could prove, or at least which he was sure of their truth, for many it has been left to me to search for their proofs. Indeed, Fermat saw that most of his theorems would be proved by observation, for indeed that is nearly the only way the properties can be proved. In truth, it is possible to find examples in which observation may be used; from these one will suffice which Fermat himself is reported to have selected. I speak of course of that theorem whose falsity has only this year been announced, in which Fermat asserted that all numbers of the form are prime numbers. In truth, observation is seen to suffice in proving this proposition.
For apart from the fact that all those prime numbers less than 100,000 are known, and it is easy to show that no prime number less than 600 can divide a number of the form , however large a number is substituted for n. Nevertheless, it is easily seen that this proposition is not true, and the use of observation prevails in this kind of speculation.
For all these reasons, those properties of numbers which are shown only by observation for a long time have been judged to be uncertain, until either a direct proof has been build or they are altogether disproved. Yet there are no theorems which I have found in those pages of the memorable theorems of Fermat but those which are connected with, to be faithful to the judgment, observation. and which knowledge of their truth is discovered by observation. In fact since I am most firmly adept at these particular proofs of these theorems, their truth is not at all doubtful. Wherefore, thus, the truth of that theorem is made plain by that method, the proofs of which I have set forth, and it can contribute strongly in other investigations of numbers, as I will show in this dissertation.
The proposition which I have supported with this proof is the following:
If p is a prime number in the formula , then this number is always divisible by p, unless a can be divided by p.
In this way alone, the truth of the remainder of the proof of this theorem flows. In the case of the formula where a=2, the proof of the theorem will be given, and this proof cannot extend to the general formula. For which reason the proof will be given in the case of this prime, to make easier the transition to the general case. Therefore the following proposition will be proved:
If p is an odd prime number, then the formula can always be divided by p.
In place of 2 write 1+1 and get
The number of terms in this series is p, and is thus odd. Moreover, any term which has the form of a fraction gives an integer number since the numerator is always divisible by its denominator. Cutting off the first term, 1, of this series gives
The number of terms of this series is p-1, and is thus even. Thus, collecting pairs of terms into one sum, so the number of terms will be half as many, gives
Since p is an odd number, the last term of this series will be
It now becomes visible that each term is divisible by p, since p is a prime number larger than any factor in the denominator, so division by the denominator cannot eliminate the factor. For that reason, if p is an odd prime number, then may always be divided by it. Q. E. D.
In another way, if can be divided by a prime number p, so also, in turn, will be its double, , and so (see note)
Cutting off the first and last terms of this series gives
Looking at this series, each term is divisible by p, since p is a prime number. Thus always can be divided by p, unless p=2. Q. E. D.
Since can be divided by an odd prime, it is easily known that p divides any formula , where m denotes any integer whatsoever. Thus the prime number p can divide the following forms , , etc. Therefore the truth of this theorem is proved in general for all cases where a is any power of 2 and p is a prime number except two.
We will now prove the following
Denoting by p any prime number except 3, the formula can always be divided by p.
If is divisible by a prime number other than 3, then is divisible by it, and conversely. It is true then that
in which series each term except the first and the last is divisible by p, if p is a prime number. Therefore the formula is divisible by p, which is equal to this:
And is always divisible by the prime number p, and so also is .
And so is always divisible by p, as long as p is a prime number other than 3. Q. E. D.
In this manner it is possible to progress from a given value a to the value one greater. But by this proof one may produce a general theorem by putting together carefully larger and larger numbers, which leads to the following
Denoting by p a prime number, if can be divided by p, then so also can the formula .
is resolved into a series in the usual way to get
in which series each term is divisible by p except the first and the last, if p is a prime number. For that reason, can be divided by p, and this formula is the same as . And can be divided by p, by hypothesis, and therefore can be also. Q. E. D.
Therefore, with the knowledge that ap-a can be divided by the prime number p, it admits the division of by p, and it follows , and then and generally to be divisible by p. Putting a=2, and we have already shown that can be divided by p, and it follows that the formula ought to admit division by p, whatever number is substituted in place of b.
Therefore p divides , and consequently , unless a=p or a is a multiple of p.
And so this is a proof of the general theorem, which I have handed down for posterity.
Translated by C Edward Sandifer
August 20, 1996