linear congruence by euclidean algorithm

**jethrotulL** · November 10th 2012, 09:07 AM

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

**Soroban** · November 10th 2012, 11:13 AM

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

**jethrotulL** · November 10th 2012, 11:25 AM

Thank you, but I need to solve it by euclidean algorithm. Can you also solve by this way please?

Thread: linear congruence by euclidean algorithm

LinkBack

Thread Tools

Display

linear congruence by euclidean algorithm

Re: linear congruence by euclidean algorithm

Re: linear congruence by euclidean algorithm

Similar Math Help Forum Discussions

how Euclid's Algorithm can be used to solve linear congruence?

Euclidan Algorithm linear congruence

Euclidean Algorithm - Linear Combination

congruence EQ using Euclidean!!

Euclidean algorithm gcd lcm help..

Search Tags