# Can $[a] \times [b]$ be an element of ${\Z / n\Z}^{\times}$?

• MHB
• cbarker1
In summary, the conversation discusses the problem of proving that if $[a]$ and $[b]$ are in the group ${\Z / n\Z}^{\times}$, then $[a] \times [b]$ is also in the group. A counterexample is provided, but it is shown that the elements $[a]$ and $[b]$ do have multiplicative inverses. It is then proven that $[ab]$ also has a multiplicative inverse and is therefore also an element of the group.
cbarker1
Gold Member
MHB
Dear Everybody,

I don't know where to begin. So Here is the problem:
$\newcommand{\Z}{\mathbb{Z}}$
Prove that if $[a]$ and $$are in {\Z / n\Z}^{\times}, then [a] \times  is in {\Z / n\Z}^{\times}. Thanks, Cbarker1 Last edited: Hi Cbarker1. This is not true. For example: [2]\in\left(\mathbb Z/6\mathbb Z\right)^\times and [3]\in\left(\mathbb Z/6\mathbb Z\right)^\times but [2]\times[3]=[2\times3]=[6]=[0]\not\in\left(\mathbb Z/6\mathbb Z\right)^\times. [QUOTE=Olinguito;114000]Hi Cbarker1. This is not true. For example: [2]\in\left(\mathbb Z/6\mathbb Z\right)^\times and [3]\in\left(\mathbb Z/6\mathbb Z\right)^\times but [2]\times[3]=[2\times3]=[6]=[0]\not\in\left(\mathbb Z/6\mathbb Z\right)^\times.[/QUOTE] Sorry, I forget to define the set: {\mathbb Z/n\mathbb Z}^{\times}=\left\{[a] \in{\mathbb Z/n\mathbb Z}^{\times}: GCD(a,n)=1 \right\} I think the counterexample is wrong? If not, please explain. Cbarker1;114002 I think the counterexample is wrong? If not said: [/SIZE] What don't you understand? The example shows that $$\displaystyle [2] \times [3] \equiv [0]$$. By your own definition of the module no representation of [0] exists in $$\displaystyle \mathbb{Z}/n \mathbb{Z} ^{\text{x}}$$. In case this isn't clear the set $$\displaystyle \mathbb{Z}/n \mathbb{Z} ^{\text{x}} = \{ [1], [2], [3], [4], [5] \}$$, so [0] is not a member of the set. This is in contrast to $$\displaystyle \mathbb{Z}/ n \mathbb{Z}$$ which does contain [0]. -Dan topsquark said: What don't you understand? The example shows that $$\displaystyle [2] \times [3] \equiv [0]$$. By your own definition of the module no representation of [0] exists in $$\displaystyle \mathbb{Z}/n \mathbb{Z} ^{\text{x}}$$. In case this isn't clear the set $$\displaystyle \mathbb{Z}/n \mathbb{Z} ^{\text{x}} = \{ [1], [2], [3], [4], [5] \}$$, so [0] is not a member of the set. This is in contrast to $$\displaystyle \mathbb{Z}/ n \mathbb{Z}$$ which does contain [0]. -Dan Thanks for the clarification. I understand. Cbarker1 said: Sorry, I forget to define the set: {\mathbb Z/n\mathbb Z}^{\times}=\left\{[a] \in{\mathbb Z/n\mathbb Z}^{\times}: GCD(a,n)=1 \right\} Ah, I get it. So we want to show that if \gcd(a,n)=\gcd(b,n)=1 then \gcd(ab,n)=1. That is exactly what the problem is asking – in simpler, non-group-theory language. There are integers r,s,t,u\in\mathbb Z such that$$ra+sn\ =\ 1\ \cdots\ \fbox1 \\ tb+un\ =\ 1\ \cdots\ \fbox2.$$From these, you want to get an equation of the form Rab+Sn=1, R,S\in\mathbb Z. Can you do that? Hint: Multiply \fbox1 by b and substitute for b in \fbox2. Erm... in group theory (\mathbb Z/n\mathbb Z)^\times is the set \mathbb Z/n\mathbb Z with the usual multiplication \times and with all elements removed that do not have a multiplicative inverse, so that if forms a group. So (\mathbb Z/6\mathbb Z)^\times only has the elements [1] and [5]. It is isomorphic to (\mathbb Z/3\mathbb Z)^\times, and also to \mathbb Z/2\mathbb Z (with addition).So indeed, the problem asks to verify that [ab] has a multiplicative inverse. And it is already given that [a] and$$ have multiplicative inverses.
We can call them $[a]^{-1}$ respectively $^{-1}$.
In the example $[5]^{-1}=[5]$ as we can see that $5\times 5 \bmod{6}=1$. Suppose we try $[ab]^{-1}=^{-1}\times[a]^{-1}$.
Then $[ab]\times[ab]^{-1}=[a]\times\times^{-1}\times[a]^{-1}=[1]$.
Therefore $[ab]$ has a multiplicative inverse and both are elements of $(\mathbb Z/n\mathbb Z)^\times$.

Klaas van Aarsen said:
Erm... in group theory the set $(\mathbb Z/n\mathbb Z)^\times$ is the set $\mathbb Z/n\mathbb Z$ with the usual multiplication $\times$ and with all elements removed that do not have a multiplicative inverse, so that if forms a group.
Yeah, I was thinking about that problem in the shower this morning. (I do my best thinking there. I need to get a girlfriend to rub lotion on my back!) Thanks for the catch.

-Dan

## 1. Can $[a] \times [b]$ be an element of ${\Z / n\Z}^{\times}$ if $a$ and $b$ are both relatively prime to $n$?

Yes, if $a$ and $b$ are both relatively prime to $n$, then $[a]$ and $[b]$ will also be relatively prime in ${\Z / n\Z}^{\times}$, and their product $[a] \times [b]$ will also be an element of ${\Z / n\Z}^{\times}$.

## 2. Can $[a] \times [b]$ be an element of ${\Z / n\Z}^{\times}$ if either $a$ or $b$ is a multiple of $n$?

No, if either $a$ or $b$ is a multiple of $n$, then their corresponding equivalence classes $[a]$ or $[b]$ will be equal to $[0]$, which is not an element of ${\Z / n\Z}^{\times}$.

## 3. Can $[a] \times [b]$ be an element of ${\Z / n\Z}^{\times}$ if $a$ and $b$ are not relatively prime to $n$?

No, if $a$ and $b$ are not relatively prime to $n$, then their corresponding equivalence classes $[a]$ and $[b]$ will not be relatively prime in ${\Z / n\Z}^{\times}$, and their product $[a] \times [b]$ will not be an element of ${\Z / n\Z}^{\times}$.

## 4. Can $[a] \times [b]$ be an element of ${\Z / n\Z}^{\times}$ if $a$ or $b$ is negative?

Yes, in the context of ${\Z / n\Z}^{\times}$, negative numbers are equivalent to their positive counterparts. Therefore, if $[a]$ or $[b]$ is negative, it can be rewritten as a positive number and their product $[a] \times [b]$ will still be an element of ${\Z / n\Z}^{\times}$.

## 5. Can $[a] \times [b]$ be an element of ${\Z / n\Z}^{\times}$ if $n$ is not a prime number?

Yes, ${\Z / n\Z}^{\times}$ is the set of all equivalence classes of integers relatively prime to $n$. This set can still exist even if $n$ is not a prime number, as long as there are integers that are relatively prime to $n$.

Replies
1
Views
2K
Replies
5
Views
1K
Replies
6
Views
1K
Replies
1
Views
1K
Replies
2
Views
716
Replies
1
Views
1K
Replies
13
Views
1K
Replies
10
Views
2K
Replies
1
Views
1K
Replies
2
Views
1K