# Inverse mod problem

• May 20th 2008, 01: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, 02: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 :

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

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

-> $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 $3*5=1+2*7=1 \mod 7$

d=3
• May 20th 2008, 02: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

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

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

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

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

I hope this helps