# linear congruence by euclidean algorithm

• Nov 10th 2012, 10: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, 12:13 PM
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: . $9x\:\equiv\:1\text{ (mod 16) }$

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

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

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

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

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

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

Substitute into [1]: . $x \:=\:5 + \frac{7(5)+1}{9} \quad\Rightarrow\quad \boxed{x \,=\,9}$
• Nov 10th 2012, 12:25 PM
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?