Solve the congruence to the smallest possible modulus.

[sg001]

Homework Statement

solve the congruence to the smallest possible modulus.

38x$\equiv$10 (mod84)

Homework Equations

The Attempt at a Solution

Ok so I thought I knew how to do these but apparently not.

So I start out by

38x+84y = 10

Now I think I should find the gcd so I can simplify

so

84 = 38(2) + 8$\Rightarrow$ 8= 84 - 38(2)

38= 8(4) + 6 $\Rightarrow$ 6= 38 - 8(4)

8 = 6(1) + 2 $\Rightarrow$ 2 = 8 - 6(1)

6 = 2(3) + 0 $\Leftrightarrow$ gcd = 2

so 19x + 42y = 5


but then where? I seem to get lost at this point?

 

[K^2]

You need to use GCD algorithm, but not just to find GCD. It's a more powerful tool. Let me demonstrate.

Lets start with your simplified version, 19x=5 (mod42), which you turn into 19x+42y=5. But if you know x, you know y. If you know y, you know x. So we can switch things around.

42y=5 (mod19)

Except 42>19, and we can take 19 away twice.

4y=5 (mod19)

Better! But why should we stop?

4y+19z=5

19z=5 (mod4)

3z=5 (mod4)

3z+4w=5

4w=5 (mod3)

w=5

Woo-hoo! Now, you can use w to find z, z to find y... I'll let you do all that.

 

[sg001]

You need to use GCD algorithm, but not just to find GCD. It's a more powerful tool. Let me demonstrate.

Lets start with your simplified version, 19x=5 (mod42), which you turn into 19x+42y=5. But if you know x, you know y. If you know y, you know x. So we can switch things around.

42y=5 (mod19)

Except 42>19, and we can take 19 away twice.

4y=5 (mod19)

Better! But why should we stop?

4y+19z=5

19z=5 (mod4)

3z=5 (mod4)

3z+4w=5

4w=5 (mod3)

w=5

Woo-hoo! Now, you can use w to find z, z to find y... I'll let you do all that.

ok good got it now thanks.