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

[cbarker1]

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

 

[Olinguito]

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

 

[cbarker1]

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

 

[topsquark]

[/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

 

[cbarker1]

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.

 

[Olinguito]

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:

Spoiler

Multiply $\fbox1$ by $b$ and substitute for $b$ in $\fbox2$.

 

[I like Serena]

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

 

[topsquark]

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