Troubles finding inverse modulus [duplicate]

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!

-

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

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

-
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

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.

-