Tricki

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

### Quick description

If and are both coprime to , then so is . From this it follows easily that the integers mod that are coprime to 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 be a prime. Then every integer that is not a multiple of is coprime to , so the non-zero integers mod form a group. This group has elements, so by Lagrange's theorem every element of the group has order dividing . Therefore, mod for every integer that is not a multiple of . This is Fermat's little theorem.

### Example 2: Euler's theorem

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

### Example 3: Wilson's theorem

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

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

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

Let be a group and let be an arbitrary element of . Then the map is a bijection from to . Proof: the map is its inverse. Let be the group of all integers mod that are coprime to . Let us list these integers as , where . Let be one of them.

Since multiplication by is a bijection, the product is congruent to the product , which is congruent to . Multiplying both sides by the inverse of (we happen to know that this is but we do not need to use this fact) we find that , so Euler's theorem has a group-theoretic proof that does not even use Lagrange's theorem.