Mod[a[n],p]
KY
Mod[n^9 - n^3, 9]=0
Derek Holt
It's easy - prove it yourself!
Derek Holt.
Chip Eastham
For an extra challenge, prove it by induction:
f(n) = n^9 - n^3
f(n+1) - f(n) = ???
--c
Bill Dubuque
HINT Trivial if 3|n, else 3|n^6-1 by ELT = Euler's little theorem [1],
i.e. (a,n) = 1 => a^E(n) = 1 (mod n) for E(n) = Euler_phi(n)
More generally see my post [4] on the Carmichael lambda function
(esp. Theorem 2) - which I've appended below for convenience:
LEMMA m squarefree => n^(phi(m)+1) = n (mod m)
This has a very simple direct proof, e.g. see my sci.math
post [1] on Apr 24, 2003. However, with only a little
more effort one may prove the following generalizations
of the Euler/Fermat little Theorems to arbitrary moduli.
THEOREM 1 For natural numbers a,e,n with e,n>1
n|a^e-a for all a <=> n squarefree & prime p|n => p-1|e-1
PROOF (<=) Since a squarefree natural divides another iff all its
prime factors do, we need only show p|a^e-a for each prime p|n, or,
that a != 0 => a^(e-1) = 1 mod p, which, since p-1|e-1, follows
from a != 0 => a^(p-1) = 1 mod p, by FlT (Fermat's little Theorem).
(=>) Given that n|a^e-a for all naturals a we must show
(1) n is squarefree and (2) p|n => p-1|e-1.
(1) If n isn't squarefree it has a nontrivial divisor aa
hence aa|n|a^e-a => aa|a =><= (via e>1 => aa|a^e)
(2) Let a be a generator of the multiplicative group of Z/p.
Thus a has order p-1. Now p|n|a(a^(e-1)-1) but not p|a,
so a^(e-1) = 1 mod p, thus e-1 must be divisible by p-1,
the order of a mod p. QED
Notice that the least such e is e = 1 + lcm{p_i - 1},
i.e. 1 + L(n), where L = Carmichael lambda defined below.
i.e. a^(L(n)+1) = a (mod n) for all a, squarefree n.
Case e = n is Korselt's criterion for Carmichael numbers [2].
Similarly we prove an analogous criterion for n|a^e-1 by
using the cyclicity of the group Z/p^k* (vs. Z/p* above).
for odd p, and using Z/2^k* = C(2) * C(2^(k-2)) for k>2,
i.e. with notation: p^k||n means p^k|n but not p^(k+1)|n
THEOREM 2 For natural numbers a,e,n with e,n>1
n|a^e-1, all a coprime n <=> prime p^k||n => E(p^k)|e
where E(p^k) = phi(p^k) for odd primes p, or p=2, k<3
and E(2^k) = 2^(k-2) for k>2
The latter exception is due to the reduced universal expt
in the noncyclic group Z/2^k* = C(2) * C(2^(k-2)) for k>2.
Notice that the least such e is L(n) := lcm{E(p_i^k_i)}.
Function L(n) is known as the Carmichael lambda function,
or the universal exponent of the multiplicative group Z/n*.
--Bill Dubuque
[1] http://google.com/groups?selm=y8zhe8n5383.fsf%40nestle.ai.mit.edu
[2] http://google.com/groups?selm=y8zmzpsrxr2.fsf%40nestle.csail.mit.edu
[3] http://en.wikipedia.org/wiki/Euler's_totient_function
[4] http://at.yorku.ca/cgi-bin/bbqa?forum=ask_an_algebraist;task=show_msg;msg=1000.0001.0001.0001.0001.0003
Bill Dubuque
>KY <wkfk...@yahoo.co.jp> wrote:
>>
>> Mod[a^9 - a^3, 9] = 0
>
> HINT Trivial if 3|a, else 3|a^6-1 by ElT = Euler's little theorem [1],
>
> i.e. (a,n) = 1 => a^E(n) = 1 (mod n) for E(n) = Euler_phi(n)
Above I meant 9|a^6-1, not 3|a^6-1; i.e. put n = 9 in ElT above.