Solution: Day 1, problem 1


Call the numbers in question "good." Clearly every good number is square-free, since if p2 | n for some prime p then the congruence an+1 = a (mod n) fails for a = p.
Write
n = p1 ... pr with p1 < p2 < ... < pr, with pi prime.
It then follows from Fermat's little theorem (correctly stated!) that n is good if and only if pi - 1 divides n for every i, and since pi - 1 is smaller than and hence coprime to the primes pj with ji

This means that pi - 1 divides p1 ... pi-1 for each integer i = 1, ... , r. Taking i = 1 forces (p1 - 1) | 1, so if r ≥ 1 then p1 = 2 (this is obvious anyway by taking a = -1 in the defining property of "good"). Similarly, taking i = 2 then gives (p2 - 1) | 2, so if r ≥ 2 then p2 = 3.

Continuing, we find: if r ≥ 3, then (p3 - 1) | p1 p2 = 6, so p3 = 7; if r ≥ 4 then (p4 - 1) | p1 p2 p3 = 42, so p4 = 43 (the numbers d + 1 are not prime for the other divisors of 42 larger than 6): and if r ≥ 5 then p5 - 1 must divide p1 p2 p3 p4 = 1806. But 1, 2, 6 and 42 are the only divisors of 1806 with d + 1 prime, so p5 cannot exist.

Hence r ≤ 4 and the only good integers are 1, 2, 6, 42, and 1806.