# Power residue counting

franktaw at netscape.net franktaw at netscape.net
Wed Aug 29 05:56:30 CEST 2007

```Actually, c(n) = A051903(n) for n = 1, too.  The correct values for n=1
are a(n) = b(n) = 1, c(n) = 0.  There is only one residue module 1, so
there is only one possible sequence of residues.

The powers modulo any maximal prime power divisor p^k of n are
periodic, except when p also divides r.  When p exactly divides r (that
is, p^2 does not divide r), then the residues modulo p^k have k
non-zero values, then zero.  So the first k values are unique, and
after that everything is periodic.  The residues modulo n can be built
up using the Chinese remainder theorem from these residues, thus
showing that the first A051903(n) values are unique, and the rest recur
infinitely often.

And yes, b(n) = A002322(n); the proof you sketched goes through.

-----Original Message-----
From: David Wilson

For modulus n, generate all sequences of powers of the residues mod n.
...
For general n > 1, there are a(n) power residue sequences mod n, of
which b(n) occur for an infinite number of exponents and c(n) for one
exponent.
...
It looks as if b(n) = A002322(n), the reduced totient function. I could
probably
prove this by showing that the cycle length of S(k) = {r^k} is the LCM
cycle lengths
of the sequences s(k) = r^k.

However, it looks as if c(n) = A051903(n) for n >= 2, but I can't see an
easy way to prove this if it is indeed true.

________________________________________________________________________
Check Out the new free AIM(R) Mail -- Unlimited storage and
industry-leading spam and email virus protection.

```