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