Page 64 - DMTH403_ABSTRACT_ALGEBRA

Unit 4: Lagrange's Theorem

For example, (2) = I and (6) = 2 (since the only positive integers < 6 and relatively prime to 6 are Notes
1 and 5).
We will now prove a lemma, which will be needed to prove the theorem that follows it. This
lemma also gives us examples of subgroups of Z,, for every n 2 2.

Lemma: Let G = G  {r  Z,|(r,n)  1}, where n 2 2. Then (G,.) is a group, where r . s =
rs  r, s  Zn. Further, o(G) =  (n).
Proof: We first check that G is closed under multiplication.

Now, r, s  G  (r, n) = 1 and (s, n) = 1  (rs, n) = 1.

 rs  G. Therefore, is a binary operation on G.

1  G, and is the identity.
Now, for any r  G, (r, n) = 1.

 ar + bn = 1 for some a, b  Z
 n | ar – 1
 ar  1 (mod n),

 a r  1.

 a  r  1

Further, a G, because if a and n have a common factor other than 1; then this factor will ‘divide
ar + bn = 1. But that is not possible.

Thus, every element in G has an inverse.
Therefore, (G, .) is a group.
In fact, it is the group of the elements of Z, that have multiplicative inverses.

Since G consists of all those r  Z, such that r < n and (r, n) = I, o(G) = (n).
Lemma and Lagrange’s theorem immediately give us the following result due to the
mathematicians Euler and Pierre Fermat.
Theorem 8 (Euler-Fermat): Let a  N and n  2 such that (a,n) = 1.
Then,, a  I (mod n).
(n)
Proof:

1. Leonhard Euler published a proof in 1789. Using modern terminology, one may prove the
theorem as follows: the numbers a which are relatively prime to n form a group under
multiplication mod n, the group G of (multiplicative) units of the ring Z/nZ. This group
has (n) elements. The element a : = a (mod n) is a member of the group G, and the order
o(a) of a (the least k > 0 such that a = 1) must have a multiple equal to the size of G.
k
(The order of a is the size of the subgroup of G generated by a, and Lagrange’s theorem
states that the size of any subgroup of G divides the size of G.)
Thus for some integer M > 0, M· o(a) = (n). Therefore, a = a o(a)·M = (a ) = 1 = 1. This
o(a) M
M
(n)
means that a = 1 (mod n).
(n)

LOVELY PROFESSIONAL UNIVERSITY 57