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.
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.
More information about the SeqFan
mailing list