Pythagoras and the Pythagoreans
12
as
2
p
−
1
a
, where
a
is odd and of course
p >
1
. First, recall that the sum
of the factors of
2
p
−
1
, when
2
p
−
1
itself is included, is
(2
p
−
1)
Then
2
m
= 2
p
a
= (2
p
−
1)(
a
+
· · ·
+ 1)
where the term
· · ·
refers to the sum of all the other factors of
a
. Since
(2
p
−
1)
is odd and
2
p
is even, it follows that
(2
p
−
1)
|
a
, or
a
=
b
(2
p
−
1)
.
First assume
b >
1
. Substituting above we have
2
p
a
= 2
p
(2
p
−
1)
b
and
thus
2
p
(2
p
−
1)
b
= (2
p
−
1)((2
p
−
1)
b
+ (2
p
−
1) +
b
+
· · ·
+ 1)
= (2
p
−
1)(2
p
+ 2
p
b
+
· · ·
)
where the term
· · ·
refers to the sum of all other the factors of
a
. Cancel
the terms
(2
p
−
1)
. There results the equation
2
p
b
= 2
p
+ 2
p
b
+
· · ·
which is impossible. Thus
b
= 1
. To show that
(2
p
−
1)
is prime, we
write a similar equation as above
2
p
(2
p
−
1) = (2
p
−
1)((2
p
−
1) +
· · ·
+ 1)
= (2
p
−
1)(2
p
+
· · ·
)
where the term
· · ·
refers to the sum of all other the factors of
(2
p
−
1)
.
Now cancel
(2
p
−
1)
. This gives
2
p
= (2
p
+
· · ·
)
If there are any other factors of
(2
p
−
1)
, this equation is impossible.
Thus,
(2
p
−
1)
is prime, and the proof is complete.
4
The Primal Challenge
The search for large primes goes on. Prime numbers are so fundamental
and so interesting that mathematicians, amateur and professional, have
been studying their properties ever since. Of course, to determine if a
given number
n
is prime, it is necessary only to check for divisibility by
a prime up to
√
n
. (Why?) However, finding large primes in this way
is nonetheless impractical
17
In this short section, we depart history and
17
The current record for largest prime has more than a million digits. The square root of
any test prime then has more than 500,000 digits. Testing a million digit number against all
such primes less than this is certainly impossible.