$112x\equiv392\pmod{91}$ has $7$ solutions?

Question

True or false? $112x\equiv392\pmod{91}$ has exactly $7$ solutions.

---

A necessary and sufficient condition for a linear congruence equation to have solution says that $\gcd(112,91)\mid392$, and the solutions are $\gcd(112,91)=7$. Since $7\mid392$ then the statement is true.

Is it correct? Am I supposed to find the general solution $(x=10+91k,\;0\leq k<7)$?

Thanks!

Answer 1

Since $91=13\cdot 7$ we have that

$$112x\equiv392\pmod{91} \iff 21x\equiv 28\pmod{91}$$

is equivalent to

$$21x\equiv 28\pmod{7} \iff 0\equiv 0 \pmod{7}$$

$$21x\equiv 28\pmod{13} \iff 8x\equiv 2\pmod{13}\iff 4x\equiv 1\pmod{13}$$

and for the latter since $10\cdot4-3\cdot13=1$ we have

$$10\cdot 4x\equiv 10\cdot 1\pmod{13}\iff x\equiv 10\pmod{13}$$

therefore the $7$ positive solutions less than $91$ are

$$x\in\{10,23,36,49,62,75,88\}$$

Answer 2

Indeed it is a necessary and sufficient condition that $\gcd(112,91)\mid392$, and indeed it is satisfied. But this does not imply that the congruence has $7$ solutions. It only implies that it has some solutions; the condition does not tell you how many solutions there are.

Because $112$, $392$ and $91$ are all multiples of $7$, solving the congruence comes down to solving $$112x=392+91k\qquad\text{ or equivalently }\qquad 16x=56+13k,$$ so it suffices to solve the congruence $16x\equiv56\pmod{13}$. This can be further reduced to $$3x\equiv4\pmod{13},$$ and it is quickly verified that this does not have $7$ solutions, but only one.