How do I find the least x that satisfies this congruence properties?

Question

Suppose $77x \equiv 1 \pmod{144}$ and $67x \equiv 3 \pmod{77}$, how do we find the least x that satisfies this relationship?

Here is what I did:

1. I expressed the first congruence relation in linear combination for $gcd(144,77)$, and I get $1 = 23(144) - 43(77)$.

2. Then I found the multiplicative inverse of 77 to be 101.

I did some computation and found the answer to be 4997, which is divisible by 101 to get 49.

How are all of these facts related? Is it legal to simply multiply the congruence relationships together to give something like $67 \times 77 \times x^2 \equiv 3 \pmod {144 \times 77}$?

Answer 1

As lulu mentions in the comments, you can't just multiply congruences like that. Besides, that creates a quadratic congruence, and they're harder to solve than linear ones.

The usual way to solve simultaneous linear congruences involves an ancient algorithm known as the Chinese remainder theorem.

Firstly, note that if $x$ is any solution, then $x + k \times 144 \times 77$ for any integer $k$ is another solution. $144 \times 77 = 11088$, so all solution are congruent to $x \mod 11088$.

To use the Chinese remainder theorem, we first need to express the congruences in the form $x \equiv a \mod m$.

You've already found that $77^{-1} \mod 144 \equiv 101$ using the extended Euclidean algorithm. So you also know how to find that $67^{-1} \mod 77 \equiv 23$. Thus we can rewrite our simultaneous congruences as

$$x \equiv 101 \mod 144$$ and $$x \equiv 69 \mod 77$$

We can now uses those inverses again to apply the Chinese remainder theorem. Note that $144 \equiv 67 \mod 77$, so we can recycle that previous result to show that $144^{-1} \mod 77 \equiv 23$

Consider $a \times 77 \times 101$ for any integer $a$. It's obviously $\equiv 0 \mod 77$, but $\equiv a \mod 144$. Similarly, $b \times 144 \times 23$ is $\equiv 0 \mod 144$ and $\equiv b \mod 77$ for any $b$. Thus

$$101 \times 77 \times 101 + 69 \times 144 \times 23$$

is $\equiv 101 \mod 144$ and $\equiv 69 \mod 77$. In other words, it's the simultaneous solution to both congruences! So

$$x \equiv 101 \times 77 \times 101 + 69 \times 144 \times 23 = 1014005 \equiv 4997 \mod 11088$$

As the linked Wikipedia article shows, it's easy to extend this algorithm to handle any number of simultaneous congruences. Usually, the moduli need to be mutually coprime, but sometimes you can get solutions when that's not the case.

Answer 2

We have $$77x \equiv 1 \equiv 7777\pmod{144}\implies x\equiv 101 \pmod{144}$$ since $(144,77)=1$ and $$67x\equiv 3\equiv4623\pmod{77}\implies x\equiv69 \pmod{77}$$ since $(77,67)=1$.

Now for the first congruence, $$x=101, 245, ..., 4997$$ and $$4997\equiv69\pmod{77}$$ and since $144\times 77=11088$, $$\boxed{x\equiv4997\pmod{11088}}$$