Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Fermat's Little Theorem, in Fermat-Euler form, states that: if $\gcd(a,m)=1$, then $a^{\varphi(m)} \equiv 1 \pmod{m}$.

Now, I've been asked to prove it via modular arithmetic. In order to do this I understand that I'm to use two lemmas:

  1. $\varphi(p^n) = p^{n} - p^{n-1}$. This I can prove by working out that there are $p^n$ numbers less than $p^n$ of which $p^{n-1}$ of them are divisible by $p$.
  2. Given $gcd(r,s) = 1$, $\varphi(rs) = \varphi(r)\varphi(s)$. This I'm having problems with.

My lecturer suggested the proposition that $\varphi(n) = n\prod_{p|n}\left(1-\frac{1}{p}\right)$. I can re-arrange this to equal lemma 1, but what I can't understand how that proposition proves 2, which my lecturer claims it does, and why these two points together prove the theorem.

I suspect I might follow the argument correctly if I fully understood lemma 2.

share|improve this question
    
For 2., $r$ and $s$ need to be relatively prime... –  Eric O. Korman Dec 12 '10 at 21:03
    
You have a couple of errors. First, you either should have $a^{\varphi(p)}\equiv 1\pmod{p}$ (cf. exponents) or $a^{\varphi(m)}\equiv 1 \pmod{m}$. Either way, you also need to require that $a$ be relatively prime to the modulus. Also, and more serious, is that (2) as stated is false: you need to also ask that $\gcd(r,s)=1$ (otherwise, take $r=s=p$ a prime to see it does not work). –  Arturo Magidin Dec 12 '10 at 21:08
    
@Arturo Sorry, my omission/typo. corrected question. –  Ninefingers Dec 12 '10 at 21:10
    
@Arturo The Euler generalisation. Also, not homework. We weren't asked to prove it, the lecturer's logic just makes quantum leaps I don't grasp. –  Ninefingers Dec 12 '10 at 21:16
    
Okay: I fixed the text, then; you had changed it to Fermat's Little Theorem instead of fixing the modulus to get Euler. –  Arturo Magidin Dec 12 '10 at 21:18

2 Answers 2

up vote 4 down vote accepted

Part 2 can be proven in many different ways; what your lecturer suggests, if you already know the identity, will do it. Just notice that if $p|rs$, then either $p|r$ or $p|s$, and not both, since $\gcd(r,s)=1$. So we have: $$\varphi(rs) = rs\prod_{p|rs}\left(1 - \frac{1}{p}\right) = rs\left(\prod_{p|r}\left(1 - \frac{1}{p}\right)\right)\left(\prod_{p|s}\left(1-\frac{1}{p}\right)\right),$$ and go from there.

One you have this, the proof of the Fermat-Euler Theorem reduces to proving that if $\gcd(a,p)=1$, then $a^{\varphi(p^n)} \equiv 1 \pmod{p^n}$ for every positive integer $n$; you can use 2 and the Chinese Remainder Theorem to prove that this suffices, and then you can use 1 to try to establish the condition modulo a prime power.

share|improve this answer
    
Aaah. Now that makes sense. Thanks! –  Ninefingers Dec 12 '10 at 21:26

Here is another way to prove Euler's generalization. You do not need to know the formula of $\varphi(n)$ for this method which I think makes this method elegant.

Consider the set of all numbers less than $n$ and relatively prime to it. Let $\{a_1,a_2,...,a_{\varphi(n)}\}$ be this set.

Consider a number $c < n$ and relatively prime to it i.e. $c \in \{a_1,a_2,\ldots,a_{\varphi(n)}\}$.

First observe that for any $a_i$, $c a_{i} \equiv a_{j} (\bmod n)$ for some $j$. (True since $c$ and $a_i$ are themselves relatively prime to $n$, their product has to be relatively prime to $n$).

And if $c a_{i} \equiv c a_{j} (\bmod n)$ then $a_i = a_j$. (True as cancellation can be done since $c$ is relatively prime to $n$).

Hence, if we now consider the set $\{ca_1,ca_2,...,ca_{\varphi(n)}\}$ this is just a permutation of the set $\{a_1,a_2,...,a_{\varphi(n)}\}$.

Thereby, we have $\displaystyle \prod_{k=1}^{\varphi(n)} ca_k \equiv \prod_{k=1}^{\varphi(n)} a_k (\bmod n)$.

Hence, we get $\displaystyle c^{\varphi(n)} \prod_{k=1}^{\varphi(n)} a_k \equiv \prod_{k=1}^{\varphi(n)} a_k (\bmod n)$.

Now, note that $\displaystyle \prod_{k=1}^{\varphi(n)} a_k$ is relatively prime to $n$ and hence you can cancel them on both sides to get

$$c^{\varphi(n)} \equiv 1 (\bmod n)$$ whenever $(c,n) = 1$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.