## 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.