# Inverse mod problem

• May 20th 2008, 12:57 PM
Frostking
Inverse mod problem
I know I must be the stupidest person alive but to save my life I can not figure out:

inverse of 5 mod 7!!!! I know it is 3 but I CAN NOT figure out the way to get this and I really want to pull all my hair out!!! If someone can help I would really appreciate it!
• May 20th 2008, 01:02 PM
Moo
Hello,

Quote:

Originally Posted by Frostking
I know I must be the stupidest person alive but to save my life I can not figure out:

inverse of 5 mod 7!!!! I know it is 3 but I CAN NOT figure out the way to get this and I really want to pull all my hair out!!! If someone can help I would really appreciate it!

You're looking for d such that 5d=1 mod 7

For this, use the Euclidian algorithm :

\$\displaystyle {\color{red}7}={\color{blue}5}*1+{\color{magenta}2 }\$ -> \$\displaystyle {\color{magenta}2}={\color{red}7}-{\color{blue}5}\$

\$\displaystyle {\color{blue}5}={\color{magenta}2}*2+1\$

-> \$\displaystyle 1={\color{blue}5}-{\color{magenta}2}*2={\color{blue}5}-2({\color{red}7}-{\color{blue}5})=3*{\color{blue}5}-2*{\color{red}7}\$

Hence \$\displaystyle 3*5=1+2*7=1 \mod 7\$

d=3
• May 20th 2008, 01:06 PM
TheEmptySet
Quote:

Originally Posted by Frostking
I know I must be the stupidest person alive but to save my life I can not figure out:

inverse of 5 mod 7!!!! I know it is 3 but I CAN NOT figure out the way to get this and I really want to pull all my hair out!!! If someone can help I would really appreciate it!

You can use the Euclidean algorithm

\$\displaystyle 7=1(5)+2 \iff 2=7-1(5)\$
\$\displaystyle 5=2(2)+1 \iff 1=5-2(2)\$

Now subbing the first equation into the 2nd for 2 gives

\$\displaystyle 1=5-2(7-1(5)) \iff 1=3(5)-2(7)\$

The last shows that \$\displaystyle 3(5)=1 \mod 7\$

I hope this helps