Power residue counting

[franktaw at netscape.net]

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.

Franklin T. Adams-Watters

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