I have the following problem:

Solve the congruence $20x \equiv 16 \pmod{92}$. Give your answer as

(i) a congruence to the smallest possible modulus;

(ii) a congruence modulo $92$.

I just recently solved another congruence equations problem:

Solve the following congruences, or explain why they have no solution:

(i) $28x \equiv 3 \pmod{67}$;

(ii) $29x \equiv 3 \pmod{67}$.

I'm confused about how to solve (i) for the first problem. I usually solve these problems by using (1) the Euclidean algorithm to find the greatest common divisor, and (2) then using the extended Euclidean algorithm. But how would the way you solve (i) in the first problem differ from how you solve the second problem?

Also, would I be correct in saying that solving (ii) of the first problem is just done in the same way you solve the second problem?

I found this related question on congruences to the smallest possible modulus, but it doesn't seem to actually explain anything; it just goes straight to some calculations.

I would greatly appreciate it if people could please take the time to clarify this.

  • 1
    $\begingroup$ So, what is the GCD in the first example? $\endgroup$ – Lord Shark the Unknown Aug 26 '18 at 7:11

Yor first equation can by written as $$5x\equiv 4\mod 23$$, then you can write $$x\equiv \frac{4}{5}\equiv \frac{27}{5}\equiv \frac{50}{5}\equiv 10\mod 23$$

  • $\begingroup$ Oh, so that's what is meant by smallest possible modulus: we actually have to use the laws of acceptable algebra on congruence equations to get the modulus to the smallest possible integer, and then we solve it as normal? $\endgroup$ – The Pointer Aug 26 '18 at 7:16
  • 1
    $\begingroup$ Yes this is right, have you got the solutions for the other equations? $\endgroup$ – Dr. Sonnhard Graubner Aug 26 '18 at 7:17
  • $\begingroup$ Yes, I already solved them. Thanks for the clarification! $\endgroup$ – The Pointer Aug 26 '18 at 7:18
  • 1
    $\begingroup$ Ok, nice that i could help you, have a nice day! $\endgroup$ – Dr. Sonnhard Graubner Aug 26 '18 at 7:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.