Discovered New Theorem while solving Chinese Remainder Theorem

I was working through some Chinese Remainder Theorem (CRT) problems today (9/24/22), using a new technique introduced in the UKMT Introduction to Number Theory Book. And I noticed a pattern:

\[9a \equiv 1 \pmod 7 \rightarrow a = 4\]

\[7b \equiv 1 \pmod 9 \rightarrow b = 4\]

Which is cool. But it continues:

\[7c \equiv 1 \pmod 5 \rightarrow c = 3\]

\[5d \equiv 1 \pmod 7 \rightarrow d = 3\]

And:

\[35e \equiv 1 \pmod 33 \rightarrow e = 17\]

\[33f \equiv 1 \pmod 35 \rightarrow f = 17\]

Each modular inverse for these pairs were the same! I formed a conjecture, and proved it as a new theorem:

Theorem: The solutions $a, b$ to the modular equivalences

\[(n-1)a \equiv 1 \pmod {n+1}\]

\[(n+1)b \equiv 1 \pmod {n-1}\]

for positive even integers $n$ satisfy $a = b = \frac{n}{2}$.

Update (12/25/23): More intuitive understanding of Chinese Remainder Theorem (CRT) process.

I was looking back at this post, and realized that I had forgotten how the Chinese Remainder Theorem process worked! So I revisited it and found a complicated formula for finding $x$ that satisfies the following 3 (or any number of) modular congruences:

\[ x \equiv a_1 \pmod {m_1} \]

\[ x \equiv a_2 \pmod {m_2} \]

\[ x \equiv a_3 \pmod {m_3}. \]

The formula is

\[ x \equiv  a_1 M_1 y_1 + a_2 M_2 y_2 + a_3 M_3 y_3 \pmod M \]

where $M = \prod_i m_i = m_1 m_2 m_3$, $M_i = M / m_i$ for $i=1, 2, 3$, and $y_i$ is the modular inverse of $M_i$ modulo $m_i$, meaning $y_i \cdot M_i \equiv 1 \pmod {m_i}$.

But just by looking at the CRT formula, it's hard to understand what each term means.

Note: The modular inverse can be found using the Extended Euclidean Algorithm, an ingenious technique of using back substitution of the Euclidean Algorithm (of coprime numbers) to find $ax + by = 1$ where $x = m_i$ and $y = M_i$, and $b$ is the modular inverse $y_i$ of $M_i \pmod {m_i}$ since $by = y_i \cdot M_i \equiv 1 \pmod {m_i}$.

Let's go though an example to understand it better!

Chinese Remainder Theorem example

Find the smallest positive integer $x$ that satisfies the following modular congruences:

\[ x \equiv 4 \pmod 7 \]

\[ x \equiv 3 \pmod {11} \]

\[ x \equiv 2 \pmod 8. \]

Using the Chinese Remainder Theorem (CRT) formula, we get 

\[ x \equiv  a_1 M_1 y_1 + a_2 M_2 y_2 + a_3 M_3 y_3 \pmod M \]

where $a_1 = 4, a_2 = 3, a_3 = 2$ and $M = 7 \cdot 11 \cdot 8$. Then, we find $M_1 = M / 7 = 8 \cdot 11$, $M_2 = M / 11 = 7 \cdot 8$, and $M_3 = M / 8 = 7 \cdot 11$.

Let's focus on just the first term in the expression $a_1 M_1 y_1 = (4) (8 \cdot 11) y_1$. This term is the modulo-7 term, meaning $x \equiv a_1 M_1 y_1 \pmod 7$.

So what do all the terms in the modulo-7 term do? Here, $a_1$ represents the given remainder of $4$ when $x$ is divided by $M$. Including $M_1 = m_2 m_3 = 8 \cdot 11$ ensures that this modulo-7 term is a multiple of $m_2 = 8$ and $m_3 = 11$ so it has no influence when testing $x$ modulo $m_2, m_3$. Finally, we include $y_1$, the modular inverse of $M_1$ to "cancel out" the effect $M_1$ has on the remainder term $a_1 = 4$ since $M_1 \cdot y_1 \equiv 1 \pmod {m_1}$. This means $a_1 M_1 \cdot y_1 \equiv a_1 \pmod {m_1}$.

Then we see that the other terms $a_2 M_2 y_2$ and $a_3 M_3 y_3$ (the modulo-11 and modulo-8 terms, respectively) are both multiples of $7$ since $M_2 = 7 \cdot 8$ and $M_3 = 7 \cdot 11$. This means that these two terms will not affect the remainder of $x$ when divided by $7$, which ensures $x \equiv a_1 M_1 y_1 \equiv a_1 \pmod 7$ as we wanted.

The same logic can be applied to the modulo-11 and modulo-8 terms to see that $x \equiv a_2 M_2 y_2 \equiv a_2 \pmod {11}$ and $x \equiv a_3 M_3 y_3 \equiv a_3 \pmod {8}$. Thus, $x$ satisfies all the modular congruences in the problem statement.

Finally, we can find that $y_1 = 2$ since $M_1 y_1 = 88 \cdot 2 \equiv 1 \pmod 7$, $y_2 = 1$ since $M_2 y_2 = 56 \cdot 1 \equiv 1 \pmod {11}$, and $y_3 = 5$ since $M_3 y_3 = 77 \cdot 5 \equiv 1 \pmod 8$. Then, we can substitute these numbers into our equation and find

\[ x \equiv  (4)(88)(2) + (3)(56)(1) + (2)(77)(5) \equiv 410 \pmod {616}. \]

Thus, the smallest positive integer $x$ that satisfies all three modular congruences is $410$.

Further Reading 

Extended Euclidean Algorithm to find modular inverse of a number mod n:

- http://www-math.ucdenver.edu/~wcherowi/courses/m5410/exeucalg.html (doesn't seem to work)

- [To be added later: Extended Euclidean Algorithm walk-through]