Proving Theorems

Date: 07/20/2001 at 06:55:45
From: Condensate
Subject: How to prove Euler's Theorem, i.e., a^f(n) = 1 (mod n) where 
f(n) is the phi function.

Dear Dr. Math,

I would like to ask two questions:

(1) How to prove Euler's Theorem, i.e.,
    let f(x) be the Euler phi-function. Then a^f(n) = 1 (mod n) for 
    any integer a.

(2) Is there a theorem stating that 'If (a, p) = 1, then a^(p-1) = 1 
    (mod p)? (I think it is a bit different from Fermat's Little 
    Theorem.) If so, can you give me a proof of it?

Thanks for your help!
Condensate

Date: 07/20/2001 at 14:30:57
From: Doctor Rob
Subject: Re: How to prove Euler's Theorem, i.e., a^f(n) = 1 (mod n) 
where f(n) is the phi function.

Thanks for writing to Ask Dr. Math, Condensate.

Your statement of Euler's Theorem is incorrect. It doesn't work for
any integer a. For example, try a = 2 and n = 4. You must add the
condition that (a,n) = 1.

(1) Look at the multiplicative group G of integers x such that
1 <= x < n and (x,n) = 1, with multiplication done modulo n. By
definition, f(n) = #G = the number of elements in G. Let 
A = a (mod n), where 1 <= A < n, so A is in G. Now consider the
subgroup H of G consisting of powers of A. By Lagrange's Theorem,
#H | #G.  Then #H is the order of A, ord(A), so ord(A) | f(n).
Since A^ord(A) = 1 (mod n) by the definition of the order of an
element of a group, that implies that A^f(n) = 1 (mod n), which in
turn implies that a^f(n) = 1 (mod n).

Lagrange's Theorem is proved by showing that if H is a subgroup of
a finite group G, then any two left cosets of H are disjoint or
coincident; all left cosets of H have the same size; and the left
cosets of H exhaust G. Thus G can be split into a number m of sets
all of whose sizes are #H.  Thus #G = m*#H, and so #H | #G.

(2) This is false. Try a = 3 and p = 4. If you add the condition that 
p is prime, then it is Fermat's Little Theorem, and so it is true.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/