Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 1 down vote accepted

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.

share|cite|improve this answer
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.

share|cite|improve this answer
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}$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.