Can anyone help me with this? I know there are many different ways to do this and threads explaining this question. However I can't seem to find one that uses only group/ring theory. I haven't taken number theory so maybe that's the problem.


These both follow from Lagrange's theorem, which states that for finite groups, the order of a subgroup divides the order of the group: $H < G$ implies $|H|\ \ |\ \ |G|$.

This then implies that the order of an element divides the order of the group, for the subgroup $\left<x\right>$ generated by an element $x \in G$ consists of elements $\{1,x,x^2,\ldots,x^{n-1}\}$ where $n$ is the order of $x$. Thus $|\left<x\right>| = n$, so we see that $n\ | \ \ |G|$.

This then implies that any element raised to the order of the group is the identity: $x^{|G|} = 1$, because $x^{|G|} = x^{kn}$ for $n$ the order of $x$ and $k$ some integer (because $|G| = nk$ for some $k$, because $n$ divides $|G|$). Thus $x^{|G|} = x^{kn} = (x^{n})^k = 1^k = 1$.

Fermat's little theorem:

Consider the multiplicative group $(\mathbb{Z}/p\mathbb{Z})^\times$, consisting of the units (i.e. elements with a multiplicative inverse) of the ring $\mathbb{Z}/p\mathbb{Z}$.

$(\mathbb{Z}/p\mathbb{Z})^\times$ has order $p-1$, consisting of the elements $\{1, 2, \ldots, p-1\}$, with the group operation multiplication modulo $p$. (To see why each of these is invertible, see my comment about the Euclidean Algorithm in the section below.)

Thus any element $x \in (\mathbb{Z}/p\mathbb{Z})^\times$ satisfies $x^{p-1} = 1$.

Thus any integer $a$ not divisible by $p$ satisfies $a^{p-1} \equiv 1\ (\mathrm{mod} \ p)$.

Euler's generalization:

The totient function $\phi(n)$ is simply the number of elements in the multiplicative group $(\mathbb{Z}/n\mathbb{Z})^\times$, consisting of the units of the ring $\mathbb{Z}/n\mathbb{Z}$ (i.e. elements with a multiplicative inverse). That is, the elements which are invertible modulo $n$ are precisely those coprime to $n$.

(The proof of this is by the Euclidean Algorithm: There exist $h$ and $k$ such that $ha + kn = \gcd(a,n)$. Then $\gcd(a,n) = 1$ if and only if there exist $h$ and $k$ with $ha + kn = 1$, i.e. if and only if there exists $h$ such that $ha \equiv 1\ (\mathrm{mod} \ n)$, i.e. if and only if $a$ is invertible modulo $n$.)

Thus if $a$ is coprime to $n$, we get $a^{\phi(n)} \equiv 1 \ (\mathrm{mod} \ n)$ just as in the proof of Fermat's little theorem.


Take a look at this site: http://www.artofproblemsolving.com/Wiki/index.php/Fermat%27s_Little_Theorem

The first proof they show is by induction, and it doesn't use any particularly difficult mathematics. Proof three is my favourite, and uses only combinatorics. The second one can be generalised to prove the Fermat-Euler theorem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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