Those Fascinating Numbers 227

77 867

• the third prime number p such that

37p−1

≡ 1 (mod

p2):

the only prime

numbers p

232

satisfying this congruence are 2, 3 and 77 867 (see Ribenboim

[169], p. 347).

78 498

• the number of prime numbers ≤ 1 000 000.

78 557

• the smallest known Sierpinski number: an odd number k is called a Sierpinski

number if

k·2n

+1 is composite for each n ≥ 1; Sierpinski proved that there exist

infinitely many such numbers k, and in particular that 201 446 503 145 165 177 is

one of these numbers; in 1962, Selfridge proved that 78 557 is also a Sierpinski

number166,

without however claiming it was the smallest Sierpinski number

(see H.C. Williams

[204])167;

see also the number 509 203.

166To prove that 78 557 is a Sierpinski number, Selfridge showed that at least one of the prime

numbers 3, 5, 7, 13, 19, 37, 73 divides 78 557 ·

2n

+1 for all integers n ≥ 1. More precisely he showed

that

n ≡ 1 (mod 3) =⇒ 7|78557 ·

2n

+ 1

n ≡ 11 (mod 12) =⇒ 13|78557 ·

2n

+ 1

n ≡ 0 (mod 2) =⇒ 3|78557 ·

2n

+ 1

n ≡ 1 (mod 4) =⇒ 5|78557 ·

2n

+ 1

n ≡ 15 (mod 18) =⇒ 19|78557 ·

2n

+ 1

n ≡ 27 (mod 36) =⇒ 37|78557 ·

2n

+ 1

n ≡ 3 (mod 9) =⇒ 73|78557 ·

2n

+ 1.

These congruences are respectively equivalent to

n ≡ 1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34 (mod 36),

n ≡ 11, 23, 35 (mod 36),

n ≡ 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34 (mod 36),

n ≡ 1, 5, 9, 13, 17, 21, 25, 29, 33 (mod 36),

n ≡ 15, 33 (mod 36),

n ≡ 27 (mod 36),

n ≡ 3, 12, 21, 30 (mod 36).

Since these congruences cover all congruence classes modulo 36, this establishes that 78557 ·

2n

+ 1

is composite for all integers n ≥ 1.

167It is known today that the smallest number k which could possibly be a Sierpinski number

is k = 10 223; in fact, as of 2008, there remains six numbers smaller than 78 557 which could

possibly be Sierpinski numbers: 10 223, 21 181, 22 699, 24 737, 55 459 and 67 607; one of the last

“false Sierpinski numbers”, namely 19 249, was eliminated in 2007 by K. Agafonov, who proved that

19 249 · 213 018 586 + 1 is prime.