If $z$ is not divisible by $r$, where $r$ is a prime of the form $(4n+3)$, then there exists an integer $z_{1}$ such that $zz_{1} \equiv 1 (mod r) $

Question

I was reading Diophantine Analysis (Robert Carmichael), and on Page No.-34 of the book, it says :

If $z$ is not divisible by $r$, where $r$ is a prime of the form (4n+3), then there exists an integer $z_{1}$ such that $zz_{1} \equiv 1 mod r $.

I tried and couldn't prove this. If anyone could help me with the proof, I would greatly appreciate it.

Answer 1

Since $r$ is prime and $r\nmid z$, $\gcd(r,z)=1$. Therefore, there are integers $z_1$ and $n$ such that $rn+zz_1=1$. In particular, $zz_1\equiv1\pmod r$.

Answer 2

A Fun Overkilling Solution

Let $q\in\{1,2,\ldots,r-1\}=:[r-1]$ be the remainder of $z$ when divided by $r$. Using Wilson's Theorem, we have $$z\,\prod_{j\in[r-1]\setminus\{q\}}\equiv q\,\prod_{j\in[r-1]\setminus \{q\}} j=(r-1)!\equiv-1\pmod{r}\,.$$ Therefore, $z_1:=-\prod_{j\in[r-1]\setminus\{q\}}\,j$ will work, albeit being quite inefficient to determine.