You are Here: Home >< Maths

# Linear Algebra watch

1. Let n be a positive integer, and let G be the set of integers x with 1<=x<n such that n and x are comprime. Let theta(n) = |G|.

Show that G forms a group under this multiplication (mod n), and deduce that, for any number a coprime to n, a^((theta(n)) = 1 (mod n).
2. (Original post by Zagani)
Let n be a positive integer, and let G be the set of integers x with 1<=x<n such that n and x are comprime. Let theta(n) = |G|.

Show that G forms a group under this multiplication (mod n), and deduce that, for any number a coprime to n, a^((theta(n)) = 1 (mod n).
To show that its a group, consider two elements a and b in G. Then a and b are both coprime to n. That is to say, gcd(a,n)=1 and gcd(b,n)=1. Hence, we can write ar+ns=1, and bp+nq=1 for some integers r,s,p,q. Now, multiply (ar+ns) by (bp+nq) to get (ab)rp+n(arq+spb+sq)=1, so that ab and n are coprime. Hence, ab is also in G, and closure is verified. Verifying that multiplication is associative is trivial; i'll leave it to you. Now, 1, which is certainly in G for all n, is the multiplicative identity. Showing that any element in the group has a multiplicative inverse can be done in a variety of ways. For example, let a be in G, so that a and n are coprime. Let A be the set of numbers coprime to n={a1,a2,...,atheta(n)}, and let aA be the product set={aa1,aa2,...,aatheta(n)}. Now, due to congruence mod n, the sets aA and A must be equal. Hence, the product of their elements must be equal, so that a1.a2...atheta(n)=atheta(n).a1.a2...atheta(n) (mod n). Since a1.a2...atheta(n) is coprime to n, cancel this out, to get that 1=atheta(n). With this last verification, it follows that the inverse of a exists and that it is equal to atheta(n)-1.

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: February 5, 2006
Today on TSR

### University open days

Wed, 21 Nov '18
• Buckinghamshire New University
Wed, 21 Nov '18
• Heriot-Watt University
Wed, 21 Nov '18
Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams