26
$\begingroup$

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?

  • 0
    I wouldn't call this a dupe, as that one only allows a specific kind of proof and this one disallows a specific kind of proof.2011-07-10

1 Answers 1

28

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} \pmod{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} \pmod{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 \pmod{n}$.

Hence, we get $\displaystyle c^{\varphi(n)} \prod_{k=1}^{\varphi(n)} a_k \equiv \prod_{k=1}^{\varphi(n)} a_k \pmod{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 \pmod{n}$ whenever $(c,n) = 1$.

  • 0
    @PeteL.Clark: when I have taught undergraduate abstract algebra, early in the course I prove two results about every element $g$ in a finite abelian group $G$: (i) $g^{|G|} = 1$ and (ii) the order of $g$ divides $|G|$. First I prove (i) and then I prove (ii) using (i). Later on I prove these same results in any finite group, but I have to switch the order of reasoning, to get (ii) first and then (i), since the method of cosets naturally leads to (ii).2013-11-23