# Homework Help: Congruence problem finding smallest modulus.

1. Apr 1, 2012

### sg001

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

Solve the congruence 20x $\equiv$16 (mod 92)

2. Relevant equations

3. The attempt at a solution

so 20x -92y=16

Hence,

92=20(4) +12.....

gcd = 4

working back,

I have -16(-9)= z (mod 92)

so z = 52

and if I divide through by my gcd =4

36$\equiv$ 13 (mod 23)

but the answer says -36$\equiv$ 10 (mod 23)

??

Im lost.

2. Apr 1, 2012

### Hurkyl

Staff Emeritus
Try explaining what you're doing, and do it without so much shorthand.

3. Apr 1, 2012

### sg001

Ok, I was being lazy

Here it is step by step.

20x$\equiv$16(mod92)

so..

20x - 92y =16

20 goes into 92, 4 times with 12 remainder

Hence,

92 = 20(4) + 12

12 = 92 - 20(4)

20= 12(1) + 8

8= 20 - 12(1)

12= 8(1) + 4

4= 12 - 8(1)

8= 4(2) + 0 $\Rightarrow$ gcd = 4

working backwards

4= 12 - (20-12)

= (92-20(4)) - (20-12)

= (92-20(4)) - (20-(92-20(4)))

= 92(2) -9(20)

so..

-16(-9) = (?) (mod92)

144 = 52 (mod92)

Now dividing through by gcd...

36$\equiv$ 13 (mod 23)

-36$\equiv$10(mod23)

I dont understand?

4. Apr 1, 2012

### Hurkyl

Staff Emeritus
I was more interested in having you explain what you're doing and why you're doing it, than detailing the individual steps in actually doing it.

This far, I can determine you intended to find gcd(92,20), along with coefficients u,v satisfying
gcd(92,20) = 92u + 20v​
I won't ask why you went off into this calculation, since it's frequently useful enough that it's probably fine to do habitually and without comment.

However, I can't tell what you were intending to do with the rest of your work:

Last edited: Apr 1, 2012
5. Apr 1, 2012

### sg001

I figured it out I just was shown a bad way with a simpler problem and have been using that approach since.(I was only using one coefficient instead of the two).

Thanks for the help thoe.