Use the fact that integers coprime to m have multiplicative inverses mod m

Quick description

If $a$ and $b$ are both coprime to $m$ , then so is $ab$ . From this it follows easily that the integers mod $m$ that are coprime to $m$ form a group under multiplication. This fact leads to simple proofs of several results in elementary number theory.

Prerequisites

Basic definitions of modular arithmetic and group theory. Lagrange's theorem.

Example 1: Fermat's little theorem

Let $p$ be a prime. Then every integer that is not a multiple of $p$ is coprime to $p$ , so the non-zero integers mod $p$ form a group. This group has $p-1$ elements, so by Lagrange's theorem every element of the group has order dividing $p-1$ . Therefore, $x^{p-1}\equiv 1$ mod $p$ for every integer $x$ that is not a multiple of $p$ . This is Fermat's little theorem.

Example 2: Euler's theorem

Let $m$ be any positive integer greater than 1. Then the integers coprime to $m$ form a group under multiplication, and this group has order $\phi(m)$ , where $\phi(m)$ is the number of positive integers less than $m$ and coprime to $m$ . By Lagrange's theorem, every element of this group has order dividing $\phi(m)$ , which implies that $x^{\phi(m)}\equiv 1$ mod $m$ for every integer $x$ that is coprime to $m$ . This is Euler's theorem.

Example 3: Wilson's theorem

What is $(p-1)!$ mod $p$ ? Since every $x$ between $1$ and $p-1$ has a multiplicative inverse, we have a lot of cancellation in the product $(p-1)!$ . Indeed, if we take the numbers from $1$ to $p-1$ and partition them into sets of the form $\{x,x^{-1}\}$ , then it looks as though everything cancels and we get 1. However, this isn't quite right because the set $\{x,x^{-1}\}$ is a singleton if $x=x^{-1}$ . But this happens only if $x=\pm 1$ , since if $x=x^{-1}$ then $x^2=1$ , which implies that $(x+1)(x-1)=0$ . So everything cancels except for the singleton $-1$ , and we obtain the result that $(p-1)!\equiv -1$ mod $p$ . This is Wilson's theorem.

The same argument shows that the product of all the positive integers less than $m$ and coprime to $m$ is congruent to $-1$ mod $m$ . This observation does not have a name.

Example 4: another proof of Euler's (and hence Fermat's) theorem

Let $G$ be a group and let $h$ be an arbitrary element of $G$ . Then the map $g\mapsto gh$ is a bijection from $G$ to $G$ . Proof: the map $g\mapsto gh^{-1}$ is its inverse. Let $G$ be the group of all integers mod $m$ that are coprime to $m$ . Let us list these integers as $a_1,a_2,\dots,a_r$ , where $r=\phi(m)$ . Let $x$ be one of them.

Since multiplication by $x$ is a bijection, the product $a_1a_2\dots a_r$ is congruent to the product $(a_1x)(a_2x)\dots(a_rx)$ , which is congruent to $a_1a_2\dots a_rx^r$ . Multiplying both sides by the inverse of $a_1a_2\dots a_r$ (we happen to know that this is $-1$ but we do not need to use this fact) we find that $x^r\equiv 1$ , so Euler's theorem has a group-theoretic proof that does not even use Lagrange's theorem.