Convert modulo 65 into modulo 26.

Question

Is there anyway to convert x ≡ 9 (mod 65) into x ≡ something (mod 26)? Generally is there a way to convet one modulo into some other modulo?

Answer 1

For some $k\in\mathbb{Z}$, $x=65k+9$

$65k+9\equiv x\pmod{26} \Leftrightarrow 65k\equiv x-9\pmod{26}$

Because $65\equiv13\pmod{26}$, we have $13k\equiv x-9\pmod{26}$

Theorem: If $\gcd(a, n)=1$, then the congruence $ax \equiv b \pmod n$ has a solution $x \equiv c \pmod n$

But because $\gcd(13,26)\ne1$, there does not exist a solution for $k$.

Thus we have to use modulus $13$.

$13k\equiv 0\equiv x-9\pmod{13} \Leftrightarrow x \equiv 9\pmod{13} \Leftrightarrow x \equiv 9,22\pmod{26}$