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

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

-

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.

-
Thanks, I actually just misread the question, (I got the answer from the back of the book) it was meant to be $36$ instead of $35$. What you said about using FLT to find the inverse is quite interesting though. I am aware of FLT but never thought about using it as a way to find an inverse - I was just using it to calculate large congruences. Thanks for this tip! – Arvin Nov 10 '12 at 4:23

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

-
My mistake, it was meant to be $\mathbb Z_{36}$ and indeed $29$ would then be the inverse. I misread the question! Sorry! – Arvin Nov 10 '12 at 4:16
@Arvin alright. Then you can see $5\times 29=145=36\times 4+1\equiv 1\pmod{36}$, so $5^{-1}\equiv 29\pmod{36}$. – ՃՃՃ Nov 10 '12 at 4:21
OK, I just saw the edit. – ՃՃՃ Nov 10 '12 at 4:23
Thanks anyway :) – Arvin Nov 10 '12 at 4:24

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

-