Eli Bendersky’s website » Blog Archive » A group-theoretic proof of Euler’s theorem

A group-theoretic proof of Euler’s theorem

August 1st, 2009 at 8:00 am

A very important and useful theorem in number theory is named after Leonhard Euler:

$a^{\varphi (n)} \equiv 1 \pmod{n}$

Where $\varphi (n)$ is Euler’s totient function – the amount of numbers smaller than n that are coprime to it.

Here I want to present a nice proof of this theorem, based on group theory. I begin with some preliminary definitions and gradually move towards the final goal.

(I) Congruence class: Let a and n > 0 be integers. The set of all integers that have the same remainder as a when divided by n is called the congruence class of a modulo n and is denoted by [a]_n , where:

$[a]_n=\{x\in \mathbb{Z}|x\equiv a(mod n)\}$

$\mathbb{Z}_n$ is the set of all congruence classes modulo n.

(II) Units of $\mathbb{Z}_n$ : If for [a]_n we find some [b]_n such that [a]_n[b]_n=[1]_n , we call [a]_n a unit of $\mathbb{Z}_n$ . The set of units of $\mathbb{Z}_n$ is denoted by $\mathbb{Z}^{\times}_{n}$

For example, [2]_n is a unit of $\mathbb{Z}_7$ , because [2]_7[4]_7=[1]_7 .

(III) The congruence class [a]_n is a unit of $\mathbb{Z}_n$ if and only if (a,n) = 1 (the GCD of a and n is 1, in other words they’re co-prime).

Proof: By definition of units, there exists some [b]_n such that [a]_n[b]_n=[1]_n . Therefore $ab\equiv 1(mod n)$ , which implies that for some q, ab=1+qn . Thus ab+(-q)n=1 . So 1 is a linear combination of a and n. Therefore (a,n)=1 .
On the other hand, if (a,n)=1 , there exist q and b such that ab+qn=1 , or $ab\equiv 1(mod n)$ , so .

(IV) By definition, since every unit of $\mathbb{Z}_n$ is coprime to n, the amount of units of $\mathbb{Z}_n$ (or, the number of elements of $\mathbb{Z}^{\times}_{n}$ ) is $\varphi (n)$ .

Let’s keep this result in mind and prepare some more theorems in order to attack the proof.

(V) Lagrange’s theorem: If H is a subgroup of the finite group G, then the order of H is a divisor of the order of G.

Proof: Let’s first define |G|=n and |H|=m . Also, let $\sim$ be the equivalence relation defined in example (III) of the previous post. Since it’s an equivalence relation, it partitions G into equivalence classes. Define [a] as the equivalence class of a with $\sim$ , for any $a\in G$ .

To prove Lagrange’s theorem, we’re going to show that [a] has the same amount of elements as H. For this purpose, let’s define a function $p_a:H\rightarrow [a]$ by p_a(x)=xa for all $x\in H$ and prove that it’s an isomorphism. To do that, we’ll have to separately prove that it’s onto and one-to-one.

But first, let’s verify that the stated codomain of p_a is correct. If $h\in H$ then $p_a(h)=ha\in [a]$ because $(ha)a^{-1}=h\in H$ , so by definition of $\sim$ we have $a\sim ha$ . So indeed the codomain of p_a is [a] .

Let’s pick some y in G such that $y\sim a$ . By definition of our $\sim$ it means that $ya^{-1}=h$ for some $h\in H$ . So has a solution (since $ha=(ya^{-1})a=y$ ). Therefore is onto.
Suppose that $h,k\in H$ with . Then and by cancellation in groups we have , which proves that is one-to-one.

So we’ve proved that p_a is an isomorphism, which means that |[a]|=|H| (we can map each element of [a] to one and only one element of |H| ).

We’ve previously shown that the equivalence classes of $\sim$ partition G. But now we see that the size of each equivalence class is equal to |H| . Therefore, all the equivalence classes are of the same size, and n=mt where t is the amount of equivalence classes. This proves Lagrange’s theorem.

We’re almost there. To see how all of this relates to Euler’s theorem, let’s first define the order of an element of a group.

(VI) Order of group element: Let $a\in G$ . If there exists a positive integer n such that a^n=e , then a is said to have finite order and the smallest such positive integer is called the order of a, denoted by o(a) .

We’ll also define the subgroup generated by an element:

(VII) Cyclic subgroup: $\langle a \rangle =\{a^k:k\in \mathbb{Z}\}$ is a cyclic subgroup of G generated by $a\in G$ . For a finite G this subgroup is also finite, and its size is: $|\langle a \rangle| = o(a)$ .

Armed with these definitions, we’re now ready for the following corollary of Lagrange’s theorem:

(VIII) Lagrange theorem corollary: Let G be a finite group of order n. Then:

For any $a\in G$ , divides n
For any $a\in G$ ,

Proof: As we’ve seen, $|\langle a \rangle| = o(a)$ and by Lagrange’s theorem $|\langle a \rangle|$ divides n (since $\langle a \rangle$ is a subgroup of G). Therefore (1) is proven.
For (2), note that if a has order m, then by (1) we have n=mq for some integer q. Thus $a^n=a^{mq}=(a^m)^q$ . But a has order m, so a^m=e and therefore (a^m)^q=e . Q.E.D.

We now finally have all the tools required to prove Euler’s theorem.

Proof of Euler’s theorem: Let $G=\mathbb{Z}^{\times}_{n}$ the group of units modulo n. The order of G is $\varphi (n)$ (by (IV)). Now, by (VIII) part (2), raising any congruence class to the power $\varphi (n)$ must give the identity element. The statement $[a]^{\varphi (n)} = [1]$ is equivalent to $a^{\varphi (n)}\equiv 1(mod\: n)$

Q.E.D.

This entry was posted on Saturday, August 1st, 2009 at 08:00 and is filed under Math. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.

Comments are closed.