# Solving the Congruence $20x \equiv 16 \pmod{92}$ and Giving Answer As a Congruence to the Smallest Possible Modulus

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.

• So, what is the GCD in the first example? 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$$

• 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? Aug 26 '18 at 7:16
• Yes this is right, have you got the solutions for the other equations? Aug 26 '18 at 7:17
• Yes, I already solved them. Thanks for the clarification! Aug 26 '18 at 7:18
• Ok, nice that i could help you, have a nice day! Aug 26 '18 at 7:18

For part (i):

$$20x\equiv 16\pmod{92}$$

$$20x = 16 + 92n$$ for integer $$n$$. Dividing both sides by 4, we obtain:

$$5x = 4 + 23n$$

$$5x\equiv 4\pmod{23}$$. Multiplying 5 by its inverse modulo 23, namely 14, we obtain:

$$x\equiv 4\cdot14\pmod{23}$$

$$\boxed{x\equiv 10\pmod{23}}$$