# Thread: Solve by finding an inverse for 7

1. ## 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.

2. notice $7\times4=28\equiv 1\pmod{9}$
then $11\times4=44\equiv 8\pmod{9}$

so $x\equiv 8\pmod{9}$

3. I still don't get it...

Why 7x4...? Is that arbitrary?

4. 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 $(7,9)=1$, then $7$ has a multiplicative inverse modulo $9$. That inverse is a positive integer greater than $1$ and less than $9$, and it is coprime to $9$. So, we have just a few possibilities: $2,4,5,7,8$. Let's try them, one by one:

$2\times 7=14\equiv 5\pmod{9}$

$4\times 7=28\equiv 1\pmod{9}$

And we can stop there. So $4\equiv 7^{-1}\pmod{9}$, which means

$4\times 7x\equiv 4\times 11\pmod{9}$,

or, equivalently,

$x\equiv 8\pmod{9}$.

5. Why would you want to solve $7x \equiv 11 \pmod{9}$ to find an inverse for $7$ modulo $9$ ? Let's do it together :

Aim : find the inverse of $7$ modulo $9$.
Mathematical aim : solve $x \equiv \frac{1}{7} \pmod{9}$, that is, solve $7x \equiv 1 \pmod{9}$ for $x$.

$gcd(7, 9) = 1$. Good, we know an inverse exists.

Can you use the Euclidian Algorithm on $7x \equiv 1 \pmod{9}$ to solve for $x$ and hence find the inverse of $7$ modulo $9$ ?

6. Is $7 \times 4 = 28 = 1 \pmod{9}$ so that the inverse of $7 \pmod{9}$ is $4$ ...

Kind regards

$\chi$ $\sigma$

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