Congruence problem finding smallest modulus.

[sg001]

Homework Statement

Solve the congruence 20x \equiv16 (mod 92)
Give your answer to the smallest possible modulus.

Homework Equations

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.

 

[Hurkyl]

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

 

[sg001]

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

Ok, I was being lazy

Here it is step by step.

20x\equiv16(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)


But the answer says

-36\equiv10(mod23)

I don't understand?

 

[Hurkyl]

20x - 92y =16
...
4 = 92(2) -9(20)

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:

so..

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

144 = 52 (mod92)Now dividing through by gcd...

36\equiv 13 (mod 23)But the answer says

-36\equiv10(mod23)

I don't understand?

 

[sg001]

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:

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.