- MacTutor History of Mathematics

Solution: Day 1, problem 1

Call the numbers in question "good." Clearly every good number is square-free, since if

p^{2} | n

for some prime

p

then the congruence

a^{n+1} = a (mod n)

fails for

a = p

.
Write

n = p_{1} ... p_{r}

with

p_{1} < p_{2} < ... < p_{r}

, with

p_{i}

prime.
It then follows from Fermat's little theorem (correctly stated!) that

n

is good if and only if

p_{i} - 1

divides

n

for every

i

, and since

p_{i} - 1

is smaller than and hence coprime to the primes

p_{j}

with

j ≥ i

This means that

p_{i} - 1

divides

p_{1} ... p_{i-1}

for each integer

i = 1, ... , r

. Taking

i = 1

forces

(p_{1} - 1) | 1

, so if

r ≥ 1

then

p_{1} = 2

(this is obvious anyway by taking

a = -1

in the defining property of "good"). Similarly, taking

i = 2

then gives

(p_{2} - 1) | 2

, so if

r ≥ 2

then

p_{2} = 3

.

Continuing, we find: if

r ≥ 3

, then

(p_{3} - 1) | p_{1} p_{2} = 6

, so

p_{3} = 7

; if

r ≥ 4

then

(p_{4} - 1) | p_{1} p_{2} p_{3} = 42

, so

p_{4} = 43

(the numbers

d + 1

are not prime for the other divisors of 42 larger than 6): and if

r ≥ 5

then

p_{5} - 1

must divide

p_{1} p_{2} p_{3} p_{4} = 1806

. But 1, 2, 6 and 42 are the only divisors of 1806 with

d + 1

prime, so

p_{5}

cannot exist.

Hence

r ≤ 4

and the only good integers are 1, 2, 6, 42, and 1806.