"a^21 is congruent to a (mod 15)" (I'll use == to mean congruent)
Presumably the problem is to show that this is true, and why it is true. Of
course just checking all cases for a = 1,2,3,...14 is a "proof," but not a
satisfying one, since it does not explain why it is true, nor lead to any
other examples.
One possible generalization is: let p and q be different primes, and let
m=1+n(lcm(p-1,q-1)), for some n; that is m is 1 more than some common
multiple of p-1 and q-1. Then a^m == a (mod pq). So in the original
problem note that 21 is 1 more than a common multiple of 3-1 and 5-1. But
we might as easily use a^5.
If a is relatively prime to p and q, then by Fermat's Little Theorem,
a^(p-1) == 1 mod q and a^(q-1)==1 mod p, so a^(m-1) is 1 more than some
multiple of p and also 1 more than some multiple of q (remember how m was
defined), so it is also ==1 (mod pq). Therefore a^m == a (mod pq).
Consider kp, for k an element of 1,2,3,...q-1..
(kp)^(q-1) - 1 == 0 (mod q) by Fermat, so kp((kp)^(q-1) -1) is divisible by
p and by q, and thus
(kp)^q - kp == 0 (mod pq), or (kp)^q == kp (mod pq).
Then also (kp)^(q + q-1) == (kp)^q * (kp)^(q-1) == kp * (kp)^(q-1) == kp.
Similarly (kp)^(q+2(q-1)) == kp, and so on.
The same holds for kq, for k an element of 1,2,3,..., p-1, with respect to
mod pq.
For example, if p=5, q=7, the lcm(5,7) =12, so we should have a^13==a
(mod35), for all a.
I think this is all correct, but I've never seen this question before, so
if someone can correct me I'd appreciate it.
Karl Schaffer ---------------> khs2700@mercury.fhda.edu
(408) 864-8214 (offc) -------> De Anza College, 21250 Stevens Creek Blvd.
Cupertino, CA 95014
****************************************************************************
* To post to the list: email mathedcc@archives.math.utk.edu *
* To unsubscribe, send mail to: majordomo@archives.math.utk.edu *
* In the mail message, enter ONLY the words: unsubscribe mathedcc *
* Words in the Subject: line are NOT processed! *
* Archives at http://archives.math.utk.edu/hypermail/mathedcc/ *
****************************************************************************