# Solve by finding an inverse for 7

• Feb 28th 2010, 07:46 PM
jzellt
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.
• Feb 28th 2010, 08:12 PM
dani
notice $\displaystyle 7\times4=28\equiv 1\pmod{9}$
then $\displaystyle 11\times4=44\equiv 8\pmod{9}$

so $\displaystyle x\equiv 8\pmod{9}$
• Feb 28th 2010, 09:57 PM
jzellt
I still don't get it...

Why 7x4...? Is that arbitrary?
• Mar 1st 2010, 03:29 AM
hatsoff
Quote:

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

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

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

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

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

or, equivalently,

$\displaystyle x\equiv 8\pmod{9}$.
• Mar 1st 2010, 04:01 AM
Bacterius
Why would you want to solve $\displaystyle 7x \equiv 11 \pmod{9}$ to find an inverse for $\displaystyle 7$ modulo $\displaystyle 9$ ? Let's do it together :

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

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

Can you use the Euclidian Algorithm on $\displaystyle 7x \equiv 1 \pmod{9}$ to solve for $\displaystyle x$ and hence find the inverse of $\displaystyle 7$ modulo $\displaystyle 9$ ?
• Mar 1st 2010, 04:19 AM
chisigma
Is $\displaystyle 7 \times 4 = 28 = 1 \pmod{9}$ so that the inverse of $\displaystyle 7 \pmod{9}$ is $\displaystyle 4$ ...

Kind regards

$\displaystyle \chi$ $\displaystyle \sigma$
• Mar 1st 2010, 06:18 AM
HallsofIvy
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).