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.

Comments

Post new comment

(Note: commenting is not possible on this snapshot.)

Before posting from this form, please consider whether it would be more appropriate to make an inline comment using the Turn commenting on link near the bottom of the window. (Simply click the link, move the cursor over the article, and click on the piece of text on which you want to comment.)

snapshot
Notifications