Thread: Solve by finding an inverse for 7

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.

notice
then

so

I still don't get it...

Why 7x4...? Is that arbitrary?

Originally Posted by jzellt

I still don't get it...

Why 7x4...? Is that arbitrary?

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 ?

Is so that the inverse of is ...

Kind regards

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).