1
$\begingroup$

Here is my attempt

(1) ---> First of all I know that $[n] = [0]$ and then we assume that a and n are not relatively prime then there exists an integer $x = \gcd(a,n)$ and $x \neq 1$ and so there exists integers $q$ and $r$ such that $qx = a$ and $rx = n$ but how I can get to $[a][b] = 0$ from here, I can't find any way. Any suggestions would be greatly appreciated.

$\endgroup$
1
$\begingroup$

Let $d=\gcd(a,n)$, let $a=da'$, and let $n=db$. Then $ab=(da')b=a'(db)=a'n$.

So $ab$ is a multiple of $n$, but $1\le b\lt n$.

That takes care of showing that if $a$ and $n$ are not relatively prime, then there is an appropriate $b$.

To show that when $a$ and $n$ are not relatively prime, there is no such $b$, suppose $[a][b]=[0]$. So $n$ divides $ab$. Since $a$ and $n$ are relatively prime, the by a theorem you probably already know, we have that $n$ divides $b$.

$\endgroup$
  • $\begingroup$ I am kinda confused on how to argue for the second implication which is given a nonzero [b] in Zn and [a][b] = 0 , i need to show that a and n are not relatively prime $\endgroup$ – alkabary Oct 5 '14 at 6:38
  • $\begingroup$ I gave the proof in the answer. Suppose they are relatively prime. If $[a][b]=0$, then $n$ divides $ab$. But then, by a standard result, since $a$ and $n$ are relatively prime, we have $n$ divides $b$, which implies $[b]=[0]$. $\endgroup$ – André Nicolas Oct 5 '14 at 6:49
1
$\begingroup$

We have: $$\exists\;\Bbb Z_n\ni \overline b\ne0\;|\; \overline a \overline b= \overline 0\iff \exists b\in\Bbb Z\; n\not| \;b, n|ab\iff \gcd(a,n)\ne1$$ and to explain the last equivalence:

  • $\Leftarrow)\quad$ let $r=\gcd (a,n)$ so $a=ra'$ and $n=rn'$ with $\gcd(a',n')=1$ so let $b=n'$
  • $\Rightarrow)\quad$ By contradiction reason and using the Euclid's lemma we get the result.
$\endgroup$
  • $\begingroup$ how to argue by contradiction though ? So i am now stuck at the second implication which is given a nonzero [b] in Zn and [a][b] = 0 , i need to show that a and n are not relatively prime $\endgroup$ – alkabary Oct 5 '14 at 6:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.