# Group theory proof of Euler's theorem ($a^{\phi(m)} \equiv 1\mbox{ }(\mbox{mod }m)$ if $\gcd(a,m)=1$)

From A Classical Introduction to Modern Number Theory by Ireland and Rosen, page 33:

Corollary 1 (Euler's Theorem). If $(a,m) = 1$, then $a^{\phi(m)} \equiv 1\,(m)$.

Proof. The units in $\mathbb{Z}/m\mathbb{Z}$ form a group of order $\phi(m)$. If $(a,m) = 1$, $\bar{a}$ is a unit. Thus $\bar{a}^{\phi(m)} = \bar{1}$ or $a^{\phi(m)} \equiv 1\,(m)$.

If I'm interpreting this correctly, this proof implicitly uses the fact(?) that if $G$ is a group and $x\in G$, then $x^{|G|}=1$, where $1$ is the identity element of $G$.

If this is indeed true, can someone explain why? (I have had no prior exposure to group theory.)

-
This is a consequence of [Lagrange's Theorem](en.wikipedia.org/wiki/Lagrange's_theorem_(group_theory). Explanation of this fact is on the wikipedia article. –  Dedede Mar 19 '12 at 7:38
@Dedede, actually, one does not need Lagrange's Theorem here. See KPK's answer. –  lhf Mar 19 '12 at 10:53

Yes, $x^{|G|} = 1$ is correct for any finite group $G$ and any $x \in G$.

1. (Lagrange's Theorem) If $H$ is a subgroup of $G$, then $|H|$ is a divisor of $|G|$.

2. If $x \in G$, then there is a smallest positive integer $k$ such that $x^k = 1$. This number $k$ is called the order of $x$.

3. If $k$ is the order of $x$, then $\{1, x, x^2, \ldots, x^{k-1}\}$ is a subgroup of $G$ having $k$ elements. By step 1, $k$ is a divisor of $|G|$, so $kl = |G|$ for some integer $l$.

4. $x^{|G|} = x^{kl} = (x^k)^l = 1^l = 1$.

-

There's another proof that works for any finite Abelian (ie. commutative) group $A$. For any $a\in A$ the mapping $x\mapsto ax$ is a bijection $A\to A$ (this works in any group). Using commutativity we get $$\prod_{x\in A} x = \prod_{x\in A} ax = a^{|A|} \prod_{x\in A} x.$$ Multiplying with the inverse of the product yields $a^{|A|}=1$.

-
I wish I knew a direct proof of $x^{|G|}=1$ that works for all finite groups, not just Abelian ones, but which does not need Lagrange's Theorem... –  lhf Mar 19 '12 at 10:51
I think it's necessary the master the techniques used in the proof of Lagrange's theorem very early in any case. It seems to me that the results about non-Abelian groups very often are derived using group actions. Abelian case is easier. –  KPK Mar 19 '12 at 19:03
That's my exact feeling, hence my question. I just wish there was a less sophisticated proof of $x^{|G|}=1$. –  lhf Mar 19 '12 at 20:50

Yes that is what is going on. Any element to the power of the size of the group yields the unit.

First of all you need an exposure to Lagrange's Theorem: http://en.wikipedia.org/wiki/Lagrange's_theorem_(group_theory)

Then you have to observe the following:

$1)$ The order of $x$ equals to the order of the cyclic group generated by $x$, usually denoted $\langle x \rangle$.

$2)$By Lagrange's theorem we have that the order of any subgroup of $G$ divides the order of $G$. That is, if $H$ is a subgroup of $G$ then $\frac{|G|}{|H|}$ is an integer.

$3)$Given $x^{|G|}=x^{|H|\cdot k}$, where $H=\langle x\rangle$, and $k$ is an integer by our previous observation. Then $$x^{|G|}=x^{|H|\cdot k}=(x^{|H|})^k=e^k=e$$Where we use the fact that $|H|$ is the order of $x$ by observation $1$.

-

Lagrange says that the order of a subgroup divides the order of the (finite) group.

Now take any element $g$, then it generates a cyclic subgroup $\langle g \rangle$. Its order is the smallest $n$ such that $g^n = e$.

Since $n$ divides $|G|$ we must then have that $g^{|G|} = e$.

-