Exercise 0.3.12 (Divisors of $0$)

Proof. By hypothesis $d=a\wedge n>1$.

Since $d=a\wedge n$ divides $a$ and $n$, there are integers $e$ and $b$ such that

Then

Moreover, $d>1$ and $n=\mathit{𝑑𝑏}$, where $n>0$, thus $1\le b<n$.

So if $a$ and $n$ are not relatively prime, their exists an integer $b$ with $1\le b<n$ such that $\mathit{𝑎𝑏}\equiv 0(\mathit{𝑚𝑜𝑑}n)$.

Reasoning by contradiction, if some integer $c$ satisfies $\mathit{𝑎𝑐}\equiv 1(\mathit{𝑚𝑜𝑑}n)$, then

so $n\mid b$, where $b\ge 1$, thus $b\ge n$, in contradiction with $b<n$.

There cannot be an integer $c$ such that $\mathit{𝑎𝑐}\equiv 1(\mathit{𝑚𝑜𝑑}n)$. □