Proving Closure and Identity for 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.

 

[Kaguro]

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

 

[fresh_42]

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

Yes, it has. We can write all these numbers as $[0],[1],[2],\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 $[0]$. 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?

 

[Kaguro]

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...

 

[fresh_42]

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

 

[Kaguro]

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.

 

[fresh_42]

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.

 

[Kaguro]

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.

 

[Kaguro]

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!

 

[fresh_42]

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 \{[0],[1],[2],\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 ]=[1]$ per definition. We get from $[a]=\pi(a),[ b ]=\pi(b),[1]=\pi(1)$ with the above formulas, that $\pi(a\cdot b- 1)=[0]$, 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!

 

[Kaguro]

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.

Let me ask several questions:
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)?

 

[fresh_42]

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.

Let me ask several questions:
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 $[0]=\{\ldots,-12,-6,0,6,12,18,\ldots\}$ or $[2]=\{\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]

I use square brackets to indicate that they are not numbers, but entire sets. Let's take $n=6$. Then $[0]=\{\ldots,-12,-6,0,6,12,18,\ldots\}$ or $[2]=\{\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?

 

[fresh_42]

Are you talking about the binary number system?

Yes. And for $n=5$ we get $U(5)\cong\{i,-1,-i,1\}.$

 

[Kaguro]

[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]How about these?

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.

 

[fresh_42]

How about these?

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]

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.