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.

Possible Duplicate:
finding inverse of $x\bmod y$

Hello all

Me and some friends are studying for a discrete exam and we are having some troubles finding the inverse modulus of things. The question we are suck on is "what is the inverse of 8 mod 29".

Thanks a lot!

share|improve this question
add comment

marked as duplicate by Aryabhata, Arturo Magidin, Ross Millikan, J. M., Qiaochu Yuan Dec 17 '10 at 2:49

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2 Answers

The inverse of $8$ modulo $29$ is an integer $k$ such that $8k \equiv 1\pmod{29}$.

There are many ways of finding such an integer. The standard way is to use the Extended Euclidean Algorithm, but sometimes you can do it without using this algorithm.

For example, since $8\times 3 = 24 = -5\bmod 29$, and $-5\times -6 =30=1\bmod 29$, then $8\times(3\times-6) = 1\bmod 29$. Now just adjust by adding multiples of $29$ to get an answer between $0$ and $28$.

share|improve this answer
    
Thanks bro, Going to have to look more into this but it helps a lot. I owe you a Jager Bomb. Edit: Got it! Thanks so much! You should come party with us! –  Binary Bro Dec 16 '10 at 21:56
add comment

Using Gauss's algorithm we have $\rm\displaystyle\ \frac{1}8\ \to\ \frac{4}{32}\ \equiv\ \frac{4}{3}\ \to\ \frac{40}{30}\ \equiv\ \frac{11}{1}\ \ (mod\ 29)$

I.e. scale $\rm A/B\ \to AN/BN\ $ by the least $\rm\:N\:$ so that $\rm\ BN > 29\:.\ $ Then reduce the numerator and denominator $\rm\ mod\ 29,\:$ and iterate. You will eventually obtain a denominator of $1$ since each step reduces the denominator. Isn't that sweet? That's they key idea that led Gauss to the first proof of the Fundamental Theorem of Arithmetic, i.e. unique factorization of integers.

share|improve this answer
add comment