TITLE: Convert modulo 65 into modulo 26.
QUESTION [0 upvotes]: 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?

REPLY [2 votes]: 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}$
{"set_name": "stack_exchange", "score": 0, "question_id": 714566}