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

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|cite|improve this question

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.

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|cite|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

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