How to find the inverse of integer $i$ in $\mathbb Z_{n}$

Question

In my understanding, a number $i$ has an inverse $i^{-1}$ in $\mathbb Z_{n}$ if $i\times i^{-1} \equiv 1 \pmod{n}$

e.g.: In $\mathbb Z_{14}$ the inverse of $3$ is $5$ since $3\times5\equiv1\pmod{14}$

But what about in $\mathbb Z_{35}$? The inverse of $5$ is supposedly $29$ but $5\times29=145\equiv5\pmod{35}$ and not $1$

How do you actually find an inverse of $i$ in $\mathbb Z_{n}$?

edit: Oops, forget it, I just misread the question - it was meant to be $\mathbb Z_{36}$ in which case $145 \equiv 1 \pmod{36}$

Answer 1

In $\mathbb{Z}_{35}$, 5 has no inverse. If it did, then we would have $(1) \cdot 7 \equiv (5^{-1} \cdot 5) \cdot 7 \equiv 5^{-1} \cdot (5 \cdot 7) \equiv 5^{-1} \cdot 0 \equiv 0$.

In general, $i$ has an inverse in $\mathbb{Z}_n$ if and only if $i$ and $n$ are relatively prime. I'm not sure who told you that 5 and 29 were inverses mod 35, but they were wrong.

As far as finding the inverse, I don't know what the most efficient algorithm is in general. For small $n$, you can just try different values until it works. If $n$ is prime, then Fermat's Little Theorem says that the inverse of $i$ in $\mathbb{Z}_n$ is $i^{n-2}$. You can find a proof of Fermat's Little Theorem on Wikipedia or other sources, I don't know of any brief proofs.

Answer 2

$5$ does not have a multiplicative inverse in $\Bbb Z_{35}$ as $5$ and $35$ are not relatively prime. You may want to take a look at this.

Answer 3

Suppose that $\gcd(a,m) = 1$, so that $a^{-1}$ exists in $\mathbb{Z}_m$. One (fairly) efficient way to find the inverse is to use the Euclidean algorithm to find the Bézout coefficients. Recall the Bézout coefficients are the integers $s$ and $t$ such that $as + mt =1$.

Once you have found the Bezout coefficients, then: \begin{align} 1 = as + mt \implies 1 \equiv as \pmod{m}, \end{align} so that $s = a^{-1}$ in $\mathbb{Z}_m$. Thus, to find $a^{-1}$, find the Bézout coefficients, and then if $1 = as + mt$, then $s = a^{-1}$.