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

Best Answer

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