Tricki
a repository of mathematical know-how

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.