Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

3 Answers 3

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|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
add comment

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|improve this answer
add comment

$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|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
1  
@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
add comment

Your Answer

 
discard

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.