Euclidean Algorithm

[shelly89]

find a value of x between 0 and 77 such that

\(\displaystyle 10x = 1(mod77) \)

I did the algorithm and got

1 = -23 *10 + 3*77

so should the value of x be 54?

 

[HallsofIvy]

Have you not checked it yourself? 54 certainly is between 0 and 77! 10(54)= 540. 540/77= 7+ 1/77.

 

[shelly89]

Have you not checked it yourself? 54 certainly is between 0 and 77! 10(54)= 540. 540/77= 7+ 1/77.

yes but this is not the correct answer.....I did this in my test and got it wrong!

 

[HallsofIvy]

If x= 54, 10x= 540= 7*77+ 1.

If the problem was to solve 10x= 1 (mod 77) then x= 54 certainly is the correct answer.