1. ## 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!

2. Hello,

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

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