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?

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/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search