The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

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!

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   
Associated Topics:
College Number Theory

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.