Euclidean Algorithm Inverse: Find inverse of 2 (mod 5)

[Huski]

Hello, I was to find the inverse of $\displaystyle 2\enspace (mod\enspace 5)$ by using Euclidean's Algorithm and I can't do it for this simple problem.

forwards steps:

$\displaystyle 2\enspace (mod\enspace 5)$

$\displaystyle 2 = 5(0)+2$

$\displaystyle 5 = 2(2) + 1$

$\displaystyle 2 = 1(2) + 0$

Now find inverse (backwards steps):

$\displaystyle 1 = 5 - 2(2)$

$\displaystyle 2 = 2 - 5(0)$ (this is what we'll substitute 2 from the previous equation for)

$\displaystyle 1 = 5 - (2 - 5(0))(2)$

$\displaystyle 1 = 5 - 2(2)$

this is wrong because it should be 2(3) (the 3 is the inverse of 2 mod 5)

If i do it for a problem like $\displaystyle 5\enspace (mod\enspace 7)$ I get the right answer

forwards steps:

$\displaystyle 5\enspace (mod\enspace 7)$

$\displaystyle 5 = 7(0)+5$

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

$\displaystyle 5 = 2(2) + 1$

$\displaystyle 2 = 1(2) + 0$

backward steps:

$\displaystyle 1 = 5 - 2(2)$

$\displaystyle 2 = 7 - 5(1)$ (this is what we'll substitute 2 from the previous equation for)

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

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

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

$\displaystyle 5 = 5 - 7(0)$ (this is what we'll substitute 5 from the previous equation for)

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

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

this gives me the right solution because 3 is the inverse for 5 mod 7.

 

[HallsofIvy]

Hello, I was to find the inverse of $\displaystyle 2\enspace (mod\enspace 5)$ by using Euclidean's Algorithm and I can't do it for this simple problem.

forwards steps:

$\displaystyle 2\enspace (mod\enspace 5)$

$\displaystyle 2 = 5(0)+2$

$\displaystyle 5 = 2(2) + 1$

$\displaystyle 2 = 1(2) + 0$

Now find inverse (backwards steps):

$\displaystyle 1 = 5 - 2(2)$

$\displaystyle 2 = 2 - 5(0)$ (this is what we'll substitute 2 from the previous equation for)

$\displaystyle 1 = 5 - (2 - 5(0))(2)$

$\displaystyle 1 = 5 - 2(2)$

this is wrong because it should be 2(3) (the 3 is the inverse of 2 mod 5)

You have 5= 1+ 2(2) but to have an inverse you should have 2x= 1 (mod 5) which is equivalent to 2x= 1+ 5y or the Diophantine equation 2x- 5y= 1, not 5y- 2x= 1. The result you got is actually -2 which is equal to 3 (mod 5).

Using the "Euclidean Algorithm" I would argue: 2 divides into 5 twice with remainder 1: 5(1)- 2(2)= 1. But we want "5y- 2x= 1" not "2x- 5y= 1" so we need to change the signs. One solution is y= -1, x= -2. More generally, y= -1+ 2k, x= -2+ 5k for any integer k. If we want an answer between 0 and 5, take k= 1 so y= -1+ 2= 1 and x= -2+ 5= 3.

If i do it for a problem like $\displaystyle 5\enspace (mod\enspace 7)$ I get the right answer

forwards steps:

$\displaystyle 5\enspace (mod\enspace 7)$

$\displaystyle 5 = 7(0)+5$

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

$\displaystyle 5 = 2(2) + 1$

$\displaystyle 2 = 1(2) + 0$

backward steps:

$\displaystyle 1 = 5 - 2(2)$

$\displaystyle 2 = 7 - 5(1)$ (this is what we'll substitute 2 from the previous equation for)

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

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

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

$\displaystyle 5 = 5 - 7(0)$ (this is what we'll substitute 5 from the previous equation for)

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

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

this gives me the right solution because 3 is the inverse for 5 mod 7.