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.

Every proof I've seen of Euler's Theorem (that $\gcd(a,m) = 1 \implies a^{\phi(m)} \equiv 1 \pmod m$) involves the fact that the units of $\mathbb{Z}/m\mathbb{Z}$ form a group of order $\phi(m)$. While this is a perfectly good proof, I have to wonder if it was the one that Euler used. I know that there are fairly old precursors to group theory, but it still seems incongruous.

Thus, my question is: Are there proofs of Euler's Theorem that do not use group/ring theory? In particular, what proof (if any; I don't know whether Euler actually discovered the theorem) did Euler use himself?

share|improve this question
    
Only tangentially related, but: Is there a way to write congruences in LaTeX so that they look nice? The spacing in the question is suboptimal. –  Calvin McPhail-Snyder Jul 9 '11 at 18:37
4  
use \bmod for no space, and \pmod for parenthesis, i.e. $1 \pmod m$ –  Harry Stern Jul 9 '11 at 18:44
3  
Euler gave essentially the group-theoretic proof in Chapter 7 of his Tractatus de numerorum doctrina, 1849 (according to Weil). –  Bill Dubuque Jul 9 '11 at 18:51
    
f2.org/maths/nthproof.html check this link –  user9413 Jul 9 '11 at 19:08
    
possible duplicate of Proof of the Euler Generalisation of Fermat's Little Theorem using modular arithmetic. I remember having written the same answer earlier and now I have found the question –  user17762 Jul 9 '11 at 19:08
show 4 more comments

1 Answer

up vote 12 down vote accepted

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$. This follows immediately from the definition).

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
    
+1, very nice. By the way, this proof is in the Wikipedia article on Euler's theroem. –  joriki Jul 9 '11 at 18:56
    
But that is essentially the group theoretic way - which the OP seeks to avoid. –  Bill Dubuque Jul 9 '11 at 19:01
3  
Yes. I think the correct answer may just be "the theorem is fundamentally group-theoretic, so all the proofs are fundamentally group-theoretic (or are disguised versions of such)", but I was hoping for some confirmation. –  Calvin McPhail-Snyder Jul 9 '11 at 19:34
1  
I do think that the first point is that Euler did write as group-theoretic a proof as was possible at that date, and the second point is that, in any case, this result is a poster-child for group theory in number theory. –  paul garrett Jul 9 '11 at 20:09
1  
This answer doesn't explicitly use any abstract algebra or require any such knowledge on the part of the reader. As paul garrett says, if you know any group theory then inevitably you will see the result itself in that light. If this is not a satisfactory answer to the question, then perhaps the question should be clarified: what would constitute a less algebraic proof than this? –  Pete L. Clark Jul 10 '11 at 4:20
show 8 more comments

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.