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.