求证同余式性质：a≡b(mod m₁)且a≡b(mod m₂)⇒a≡b(mod L)

Hey there, let's break down these congruence properties clearly and fill in the proof gap you mentioned:

1. The Property You Initially Learned (Same Residue Across Moduli) #

You referenced this unproven rule:

If $a\equiv b\pmod {m_1}$ and $a\equiv b\pmod {m_2}$, then $a\equiv b\pmod L$, where $L = \text{lcm}(m_1, m_2)$ (the least common multiple of $m_1$ and $m_2$).

Proof of This Property #

Let's walk through the logic step by step:

• From $a \equiv b \pmod{m_1}$, we know $m_1$ divides the difference $(a - b)$. In integer terms, this means $a - b = k_1 m_1$ for some integer $k_1$.
• Similarly, $a \equiv b \pmod{m_2}$ tells us $m_2$ divides $(a - b)$, so $a - b = k_2 m_2$ for some integer $k_2$.

Since $(a - b)$ is a common multiple of both $m_1$ and $m_2$, it must be a multiple of their least common multiple $L$. By definition, $L$ is the smallest positive integer that both moduli divide, so $L$ divides $(a - b)$. This directly translates to $a \equiv b \pmod{L}$.

2. Konrad's Article (Different Residues Across Moduli) #

Konrad's content focuses on a separate, more complex scenario:

$a \equiv b_1\pmod {m_1}$ and $a \equiv b_2\pmod {m_2}$ (where $b_1$ and $b_2$ are not necessarily equal), with the stated condition that $\gcd(m_1, m_2) = 1$ (the moduli are coprime).

This is a simplified case of the Chinese Remainder Theorem (CRT). The coprimality condition ensures two things:

1. A solution for $a$ exists.
2. All solutions are congruent modulo $m_1 m_2$ (since $\text{lcm}(m_1, m_2) = m_1 m_2$ when moduli are coprime).

For non-coprime moduli, a solution only exists if $b_1 \equiv b_2 \pmod{\gcd(m_1, m_2)}$—Konrad likely skipped this edge case by focusing on coprime moduli.

Core Difference Between the Two Scenarios #

• Your original property deals with the same residue $b$ for both congruences, so we only need to use the LCM of moduli to extend the congruence. No coprimality is required here!
• Konrad's scenario deals with different residues $b_1, b_2$, so we need additional conditions (coprimality or residue compatibility) to guarantee a solution exists.

内容的提问来源于stack exchange，提问作者jitender