## The Primary Pretenders

4, 4, 341, 6, 4, 4, 6, 6, 4, 4, 6, 10, 4, 4, 14, 6, 4, 4, 6, 6, 4, 4, 6, 22, 4, 4, 9, 6, ...

If p is a prime number, then

n^p is congruent to n (mod p) ....... (*)

for all n, by Fermat's little theorem.

But p need not be prime for (*) to be true!
The sequence gives, for each n = 0, 1, 2, ..., the smallest composite number c such that n^c is congruent to n (mod c). We call c the Primary Pretender to base n.

The composite numbers are 4, 6, 8, 9, 10, 12, 14, ..., and we calculate as follows:

```0^4 = 0   is congruent to 0 (mod 4),
1^4 = 1   is congruent to 1 (mod 4),
2 is harder!
2^341 =
447948948435560842111488456113688855624329099446929906979997820192758374236032\
1890761754986543214231552
is congruent to 2 (mod 341),
3^6 = 729 is congruent to 3 (mod 6),
4^4 = 64  is congruent to 4 (mod 4),
and so on.
```
Thus the sequence of Primary Pretenders begins 4, 4, 341, 6, 4, ... This sequence has many interesting properties, one of which is that it is periodic with period 19568584333460072587245340037736278982017213829337604336734362- 294738647777395483196097971852999259921329236506842360439300
For more information see the full paper: The Primary Pretenders, by J. H. Conway, R. K. Guy, W. A. Schneeberger and N. J. A. Sloane.

See also [ On-Line Encyclopedia of Integer Sequences | my home page ]