notice
then
so
Solve 7x = 11 mod 9 by finding an inverse for 7. (= is congruence not equality)
I'm trying to do this by using the euclidean algorithm:
9 = 1(7) + 2
7 = 2(3) + 1
3 = 1(3) + 0
If have done the above correctly, How do I use this to find the inverse of 7?
Thanks.
Well, in this case the best method involves trial and error.
Since , then has a multiplicative inverse modulo . That inverse is a positive integer greater than and less than , and it is coprime to . So, we have just a few possibilities: . Let's try them, one by one:
And we can stop there. So , which means
,
or, equivalently,
.
Why would you want to solve to find an inverse for modulo ? Let's do it together :
Aim : find the inverse of modulo .
Mathematical aim : solve , that is, solve for .
. Good, we know an inverse exists.
Can you use the Euclidian Algorithm on to solve for and hence find the inverse of modulo ?
7x= 1 (mod 9) means that 7x= 9n+ 1 for some integer n.
That is the same as 7x- 9n= 1.
7 divides into 9 once with remainder 2: 9- 7= 2.
2 divides into 7 3 times with remainder 1: 7- 3(2)= 1.
Replacing that "2" with "9- 7", 7- 3(9- 7)= 4(7)- 3(9)= 1.
Once solution is x= 4, n= -3 which is enough to tell us that 1/7= 4 (mod 9)
Of course, it would be jjust as simple to solve 7x= 11= 2 (mod 9) directly:
7x= 2 (mod 9) means 7x= 9n+ 2 for some integer n. Once we have arrived at 4(7)- 3(9)= 1, multiplying both sides of the equation by 2, (8)(7)- 6(9)= 2 so that x= 8 satisfies 7x= 2 (mod 9).