# Thread: linear congruence by euclidean algorithm

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

2. ## Re: linear congruence by euclidean algorithm

Hello, jethrotulL!

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

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}$

3. ## 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?