Determine all solutions of the congruence $4 953^m \cdot n \equiv 13 383 \pmod{14 553}$ in integers $m,n$.

Question

Determine all solutions of the congruence $4 953^m \cdot n \equiv 13 383 \pmod{14 553}$ in integers $m,n$.

Hi everyone, I need some help with this one. I saw another thread that solved $12^x \equiv 17 \pmod{ 25}$, however I do not know how to retrace the steps when I also have an integer $n$. Some help would be appreciated.

Answer 1

Hint; The congruence needs to hold mod $\gcd(13383,14553)=9$.

Answer 2

A bit of general advice: modular equations modulo a composite number can generally be simplified by looking at its prime power factors. In this case, $14553 = 3^3 \cdot 7^2 \cdot 11$, so an equation $A \equiv B \pmod{14453}$ is equivalent to the system of equations \begin{align} A &\equiv B \pmod{3^3} \\ A &\equiv B \pmod{7^2} \\ A &\equiv B \pmod{11} \end{align} (This is justified by the Chinese Remainder Theorem.)

For complicated equations, this might not solve the problem for you, but it's a good first step no matter what you're doing. (And in this case, one of the three equations narrows down your possibilities to only three values of $m$...)