# linear congruence by euclidean algorithm

• Nov 10th 2012, 09:07 AM
jethrotulL
linear congruence by euclidean algorithm
Hey!

I have a question about solutions of linear congruences with Euclidean algorithm. I'd be very happy if you can help.

9x=1 (mod 16)
What I know is gcd of 9 and 16 is equal to 1 and it divides 1. Thus exists a unique solution.
But I cannot figure out how to find x=9 by Euclidean way.

If someone helps or just tries, thanks in advance :)
• Nov 10th 2012, 11:13 AM
Soroban
Re: linear congruence by euclidean algorithm
Hello, jethrotulL!

Even if you don't know (or understand) the Euclidean algorithm,
. . you can still solve it.

Quote:

Solve by the Euclidean algorithm: .$\displaystyle 9x\:\equiv\:1\text{ (mod 16) }$

We have: .$\displaystyle 9x \:=\:16a + 1\,\text{ for some integer }a.$

Solve for $\displaystyle x\!:\;x \:=\:\frac{16a+1}{9} \:=\:a + \frac{7a+1}{9}$ .[1]

Since $\displaystyle x$ is an integer, $\displaystyle 7a+1$ must be a multiple of 9.
. . That is: .$\displaystyle 7a+1 \:=\:9b\,\text{ for some integer }b.$

Solve for $\displaystyle a\!:\;a \:=\:\frac{9b-1}{7} \:=\:b + \frac{2b-1}{7}$ .[2]

Since $\displaystyle a$ is an integer, $\displaystyle 2b-1$ must be a multiple of 7.
. . The first time this happens is $\displaystyle b = 4$

Substitute into [2]: .$\displaystyle a \:=\:4 + \frac{2(4)-1}{7} \quad\Rightarrow\quad a\,=\,5$

Substitute into [1]: .$\displaystyle x \:=\:5 + \frac{7(5)+1}{9} \quad\Rightarrow\quad \boxed{x \,=\,9}$
• Nov 10th 2012, 11:25 AM
jethrotulL
Re: linear congruence by euclidean algorithm
Thank you, but I need to solve it by euclidean algorithm. Can you also solve by this way please?