# Prove that $[a]$ and $[n]$ are not relatively prime if and only if there is a nonzero element $[b] \in \Bbb{Z}_n$ such that $[a][b] = 0$

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.

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

• 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 – alkabary Oct 5 '14 at 6:38
• 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]$. – André Nicolas Oct 5 '14 at 6:49

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.
• 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 – alkabary Oct 5 '14 at 6:36