Inverse mod problem

**Frostking** · May 20th 2008, 12:57 PM

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!

**Moo** · May 20th 2008, 01:02 PM

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 :

${\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

**TheEmptySet** · May 20th 2008, 01:06 PM

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

Thread: Inverse mod problem

LinkBack

Thread Tools

Display

Inverse mod problem

Similar Math Help Forum Discussions

Domain Problem and Inverse Problem

Inverse Matrices Problem

Matrix Inverse Problem

Inverse Iteration -Problem

Help with inverse problem, please?

Search Tags