# Solve the congruence to the smallest possible modulus.

1. Apr 2, 2012

### sg001

1. The problem statement, all variables and given/known data

solve the congruence to the smallest possible modulus.

38x$\equiv$10 (mod84)

2. Relevant equations

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

2. Apr 2, 2012

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

3. Apr 2, 2012

### sg001

ok good got it now thanks.