# Prove that U(n) is a group

• Kaguro
In summary, the conversation discusses the closure, associativity, identity, and inverse properties of the multiplicative group U(n). The concept of Bezout's Lemma is also mentioned, which states that for any two integers a and b, their greatest common divisor is the smallest positive linear combination of a and b. It is used to explain the existence of an inverse for every element in the multiplicative group U(n).

#### Kaguro

Homework Statement
If U(n) denotes the set of all positive integers less than n which are coprime with n. Then prove that U(n) is a group under multiplication modulo n.
Relevant Equations
I don't know..
Closure
Let a,b ∈U(n).
a has no common factor with n (other than 1)
b has no common factor with n(,,)
So,
If ab < n, then ab doesn't have any common factors with n.
If ab>n, then for some p,ab-pn < n.
Since ab doesn't have any common factor with n, ab-pn can't either.
(ab≠ n, because neither a nor b can have any common factors with n)

So, ab ∈ U(n)

Closure is verified.

Associativity:
Multiplication modulo n is associative( I'm not even going to think about proving that)

Identity: 1 is the identity.

Inverse:
This is where I got obliterated...

Let a ∈ U(n).

We need an x such that:
Consider ax= pn+1 for some p.

I need to prove that
1)x= (pn+1)/a is an integer

2)It also doesn't have anything common with n.

I have zero idea how do I prove something like this... Please give me some direction.

Does it have anything to do with the Euclid division algorithm?

Kaguro said:
Does it have anything to do with the Euclid division algorithm?
Yes, it has. We can write all these numbers as ##,,,\ldots,[n-1]##. They are the remainders of a division by ##n##. Since we are looking for a multiplicative group, we do not need the zero ####. Now try to understand what ##[a]\cdot [ b ]## means! Here Euclid comes into play: Say we have two integers ##p,q## and divide them by ##n##. Then we get for instance ##p=s\cdot n +a ## and ##q=t\cdot n +b##. So what is ##[a]\cdot [ b ]## then?

If you understood this, then the question about the group axioms have to be answered. Hint: It are the inverse elements which cause the trouble here. Hence ask yourself the question: What has to happen, such that a certain ##[c]## is not invertible?

fresh_42 said:
Say we have two integers p and qp,q and divide them by n n. Then we get for instance p=sn+a,,p=s⋅n+a and q=t⋅n+bq=tn+b. So what is [a]⋅ ab then?

Just ab. Absolutely nothing special about it.

Given n, and fixing an element a, I am to find integer x for
ax = yn+1

For every real x, there is a y (just a straight line). For every integer x, also some real y is there.

For some integers x, y also happens to be an integer. Actually there are an infinite number of them.
For example consider U(7). And take element 5.
5*3=15 = 2*7+1. So for x=3,y=2
But also for 5*10=50=49+1=7*7+1. For x=10,y=7..

I need only x<n.

Such an integer pair (x,y) will exist seems like a world-shattering claim to me...

What about ##U(12)##? What is ##3^{-1}## in this case?

fresh_42 said:
What about ##U(12)##? What is ##3^{-1}## in this case?
U(12)={1,5,7,11}

It doesn't have 3. So 3 inverse doesn't make any sense.

3x=12p+1 for no integers x and p.

Yes. That's the point why only coprime elements are considered. Coprime numbers ##a,n## means, that we can write ##1=pa+qn## with some integers ##p,q## according to Bezout's lemma. This equation is equivalent to the possibility to find an inverse for ##a## modulo ##n##, namely ##p##.

It is what this exercise was made for. Associativity is inherited from the integers, and the coset of ##1## is the natural neutral element.

fresh_42 said:
Yes. That's the point why only coprime elements are considered. Coprime numbers ##a,n## means, that we can write ##1=pa+qn## with some integers ##p,q## according to Bezout's lemma. This equation is equivalent to the possibility to find an inverse for ##a## modulo ##n##, namely ##p##.

It is what this exercise was made for. Associativity is inherited from the integers, and the coset of ##1## is the natural neutral element.
I have understood what Bezout's Lemma is trying to say. Given integers a and b, the GCD of them lies in their integer span.
But this claim seems highly non-trivial to me. I will have to read a simple proof of it to help me understand.

Okay, so I understand the proof of Bezout's Lemma.
Basically, consider two integers a and b. Consider the set of all positive integer linear combinations of them. Let d be the smallest such element. Prove that this thing has to divide both a and b. Then prove that given any common divisor c of a and b, c has to divide d. So d is the HCF of a and b.

Source : https://www.expii.com/t/bezouts-identity-on-linear-combinations-3397
Now considering coprime a and b, d=1. So we can always write:
a=my+1

Now, let's prove the existence of inverse:

Let a∈U(n) ⇒ HCF(a,n)=1
Let x∈U(n) ⇒ HCF(x,n)=1

So, HCF(ax,n) = 1
So, we can always write: ax = pn + 1 for some integer p.
This, under multiplication mod n, will come out to be 1. So one particular x is the inverse of a. There always exists such an x.

Number Theory is powerful!

All the formulations with Bezout's lemma, the definition of ##U(n)##, and Euclid's algorithm, which allows division such that ##u=q\cdot n + 1## can be written for ##u\in U(n),## are closely related:

If you consider the function ##\pi : \mathbb{Z} \longrightarrow \{,,,\ldots,[ n ]\}=:\mathbb{Z}_n## which maps any integer onto its remainder from division by ##n##, then you can observe that ##\pi(a+b)=\pi(a)+\pi(b)## and ##\pi(a\cdot b)=\pi(a)\cdot\pi(b)##.

The elements of ##\mathbb{Z}_n\supseteq U(n)=\{[d]\,|\,gcd(d,n)=1\}## are called units of ##\mathbb{Z}_n## which is why they are abbreviated by a ##U##. For those units we have an equation ##[a]\cdot[ b ]=## per definition. We get from ##[a]=\pi(a),[ b ]=\pi(b),=\pi(1)## with the above formulas, that ##\pi(a\cdot b- 1)=##, which means ##n\,|\,(a\cdot b -1)## which means ##1=a\cdot b + q\cdot n## for some integer ##q##.

The sophisticated answer to the exercise is either

##\pi## is a ring homomorphism, so ##U(n)=\pi(\{1\})## is a multiplicative group as homomorphic image of the group ##\{1\}.##

or

Unities in a ring are always a multiplicative group.

The purpose of this exercise was to shine some light on these different points of view along an easy to compute example. I think you should prove the two formulas (##\pi(a+b)=\pi(a)+\pi(b)## and ##\pi(a\cdot b)=\pi(a)\cdot\pi(b) \Longrightarrow \pi## is a ring homomorphism) above as an exercise. Not so much for the formulas themselves or to learn what a ring homomorphism is, but to practice proof writing!

Wait!
I'm just a third year undergraduate physics student studying group theory for the fist time. I have just read the first two chapters of "Contemporary abstract algebra by Joseph Gallian". I have to go slowly.

Why do you keep writing the numbers with square brackets?

Zn is {0,1,2,...n-1} under addition modulo n. It contains 0. U(n) doesn't. So why did you say Zn is subset of U(n)?

Kaguro said:
Wait!
I'm just a third year undergraduate physics student studying group theory for the fist time. I have just read the first two chapters of "Contemporary abstract algebra by Joseph Gallian". I have to go slowly.

Why do you keep writing the numbers with square brackets?

Zn is {0,1,2,...n-1} under addition modulo n. It contains 0. U(n) doesn't. So why did you say Zn is subset of U(n)?
I use square brackets to indicate that they are not numbers, but entire sets. Let's take ##n=6##. Then ##=\{\ldots,-12,-6,0,6,12,18,\ldots\}## or ##=\{\ldots,-16,-10,-4,2,8,14,\ldots\}##. They are equivalence classes: all possible remainders which are considered to be the same: ##-10=(-2)\cdot 6 + 2 = (-1)\cdot 6 + (-4) = 0\cdot 6 - 10= (-3)\cdot 6 + 8=\ldots ## The numbers between ##0## and ##n-1## are only the most comfortable representatives of these sets, but ##-10 \equiv 2 \mod 6## so it is only convenience which makes us choose ##2## and not ##-10##.

As I already mentioned. You should prove ##[a+ b ]=\pi(a+b)=\pi(a) + \pi( b) = [a] + [ b ]## and ##[a\cdot b ]=\pi(a\cdot b)=\pi(a) \cdot \pi( b) = [a] \cdot [ b ]## to practice proof writing. It will also show you why this example is an important one. And a closer look will show you, that while communicating here we are using the case ##n=2## all the time!

• Kaguro
fresh_42 said:
I use square brackets to indicate that they are not numbers, but entire sets. Let's take ##n=6##. Then ##=\{\ldots,-12,-6,0,6,12,18,\ldots\}## or ##=\{\ldots,-16,-10,-4,2,8,14,\ldots\}##. They are equivalence classes: all possible remainders which are considered to be the same: ##-10=(-2)\cdot 6 + 2 = (-1)\cdot 6 + (-4) = 0\cdot 6 - 10= (-3)\cdot 6 + 8=\ldots ## The numbers between ##0## and ##n-1## are only the most comfortable representatives of these sets, but ##-10 \equiv 2 \mod 6## so it is only convenience which makes us choose ##2## and not ##-10##.

As I already mentioned. You should prove ##[a+ b ]=\pi(a+b)=\pi(a) + \pi( b) = [a] + [ b ]## and ##[a\cdot b ]=\pi(a\cdot b)=\pi(a) \cdot \pi( b) = [a] \cdot [ b ]## to practice proof writing. It will also show you why this example is an important one.
Okay! Don't mind if I take some time.

And a closer look will show you, that while communicating here we are using the case ##n=2## all the time!
Are you talking about the binary number system?

Kaguro said:
Are you talking about the binary number system?
Yes. And for ##n=5## we get ##U(5)\cong\{i,-1,-i,1\}.##

[a] ≡ π(a) = a-pn such that 0 ≤ a-pn <n
[b ] ≡ π(b) = b-qn such that 0 ≤ b-qn <n

So, [a]+[b ] = a+b - (p+q)n
If a+b - (p+q)n < n then,
[a]+[b ] = [a+b]

If a+b - (p+q)n ≥ n, then a+b - (p+q+1)n < n and this is equal to [a+b]
Hence, [a]+[b ] = [a+b]

Similarly,
[a][b ] = (a-pn)(b-qn) = ab-aqn - bpn + pqn^2

If this is less than n, then it can be written as:
[a][b ] = (a-pn)(b-qn) = ab -(aq+ bp + pqn)n = [ab]

If this is greater than or equals to n, then ab -(aq+ bp + pqn+1)n <n and this is equal to [ab]

Hence [a][b ] = [ab]

P.S.: I spent some time thinking why I couldn't write square bracket b and all the text was somehow bold... Then it hit me. Kaguro said:
Except for your emphasis on numbers between ##0## and ##n## it is fine. We do not need those numbers. We have entire sets as elements. So if ##\pi(a)=[a]## then we can think of ##[a]=a+n\cdot \mathbb{Z}##. Now every integers ##a,b## can be written as ##a=pn+r## and ##b=qn+s##. Hence ##ab=rs+c\cdot n## for some ##p,q,c##. This means ##(a+n\mathbb{Z})\cdot(b+n\mathbb{Z})=r\cdot s +n\mathbb{Z} \Longleftrightarrow \pi(a)\cdot \pi(b) = \pi(ab)##. No considerations about the range of ##r,s## are necessary.
P.S.: I spent some time thinking why I couldn't write square bracket b and all the text was somehow bold... Then it hit me.
Yes, I regularly run into the same trap. And by the way, ##[ i ]## has a similar effect.

• Kaguro
fresh_42 said:
Except for your emphasis on numbers between ##0## and ##n## it is fine. We do not need those numbers. We have entire sets as elements. So if ##\pi(a)=[a]## then we can think of ##[a]=a+n\cdot \mathbb{Z}##. Now every integers ##a,b## can be written as ##a=pn+r## and ##b=qn+s##. Hence ##ab=rs+c\cdot n## for some ##p,q,c##. This means ##(a+n\mathbb{Z})\cdot(b+n\mathbb{Z})=r\cdot s +n\mathbb{Z} \Longleftrightarrow \pi(a)\cdot \pi(b) = \pi(ab)##. No considerations about the range of ##r,s## are necessary.
Oh okay! I understand.

Thank you very much for helping me.
I aspire to grow mathematically mature one day.