I’m looking for a method to solve pairs of simultaneous linear modular equations, such as
323x + 37y = 0 Mod 243;
-397x + 683y = 0 Mod 32
I’ve simplified this to
80x+37y = 243g;
19x+11y = 32h
Although I can produce results by brute force, whatever I try just produces further equations.
I’m not even sure if I should try to solve one equation first, or both together.
I’ve found plenty of examples, even a calculator, for ax + by = c, but can’t see how to expand from here.
I’ve also found examples of pairs of two variable modular equations, but with a common modulus.
Best Answer
Here's a full solution. You're solving $\begin{cases}80x\equiv 206y\pmod{3^5}\\ 19x\equiv 21y \pmod{2^5}\end{cases}$
Now find the Modular Multiplicative Inverse of $80$ mod $3^5$ and of $19$ mod $2^5$. You can apply the Extended Euclidean Algorithm (EEA).
We have $\gcd\left(80,3^5\right)=\gcd\left(19,2^5\right)=1$. By Bézout's lemma this means there exist $r,s,t,u\in\mathbb Z$ such that $80r+3^5s=1$ and $19t+2^5u=1$. We can find the $r,s,t,u$ using EEA.
Here's how you can use EEA. Subtract consecutive equations: $$243=80(0)+243(1)\\80=80(1)+243(0)\\3=80(-3)+243(1)\\2=80(79)+243(-26)\\1=80(-82)+243(27)$$
$$32=19(0)+32(1)\\19=19(1)+32(0)\\13=19(-1)+32(1)\\6=19(2)+32(-1)\\1=19(-5)+32(3)$$
Therefore $80(-82)\equiv 1\pmod{243}$, so $80^{-1}\equiv -82\pmod{243}$.
Also $19(-5)\equiv 1\pmod{32}$, so $19^{-1}\equiv -5\pmod{32}$.
Therefore your system of linear modular equations is equivalent to:
$$\begin{cases}x\equiv (206)(-82)y\equiv 118y\equiv -1097y\pmod{3^5}\\x\equiv (21)(-5)y\equiv 23y\equiv -1097y\pmod{2^5}\end{cases}$$
$$\iff \begin{cases}3^5\mid x-(-1097y)\\2^5\mid x-(-1097y)\end{cases}$$
$$\iff \text{lcm}\left(3^5,2^5\right)=2^5\cdot 3^5\mid x-(-1097y)$$
$$\iff x\equiv -1097y\pmod{2^5\cdot 3^5=7776}$$
I used the property that the system $a\mid c$, $b\mid c$ is equivalent to $\text{lcm}(a,b)\mid c$. Some people might call this property "the universal $\text{lcm}$ property" (see, e.g., here) but it is quite trivial.
You could've also used the Chinese Remainder Theorem instead of this property.
Answer: $(x,y)\equiv (-1097k,k)\pmod{7776}$ for any $k\in\mathbb Z$.