Exercises — Chinese Remainder Theorem (intro)

We only need $\gcd$ of each pair of moduli.

• (a) $\gcd (3,5)=1$ → coprime, CRT applies.
• (b) $\gcd (6,9)=3\ne 1$ → not coprime, basic CRT does not apply.
• (c) $\gcd (7,10)=1$ → coprime, CRT applies.

Answer: (a) and (c).

The moduli $4,9,25$ are pairwise coprime ($\gcd$ of any pair is $1$). CRT says the solution is unique modulo their product: $M=4\cdot 9\cdot 25=900.$ Exactly one solution lies in $\{0,\dots ,899\}$; all others differ from it by multiples of $900$.

Use the substitution method (WHAT: turn the first congruence into a formula for $x$; WHY: then we only have one unknown left).

First congruence: $x=2+3k$ for some integer $k$. Put into the second: $2+3k\equiv 4(\mathrm{mod}7)\Rightarrow 3k\equiv 2(\mathrm{mod}7)$. Now we need $3^{-1}\mathrm{mod}7$. We want $3y\equiv 1(\mathrm{mod}7)$: try $y=5$ since $3\cdot 5=15=2\cdot 7+1\equiv 1$. So $3^{-1}\equiv 5$. Multiply both sides: $k\equiv 5\cdot 2=10\equiv 3(\mathrm{mod}7)$. Back-substitute: $x=2+3\cdot 3=11$. $\boxed{x\equiv 11(\mathrm{mod}21)}$ Check: $11=3\cdot 3+2\equiv 2(\mathrm{mod}3)$ ✓, $11=7+4\equiv 4(\mathrm{mod}7)$ ✓.

$M=3\cdot 4\cdot 5=60$. $M_1=60/3=20,M_2=60/4=15,M_3=60/5=12.$ Inverses ($y_i=M_i^{-1}\mathrm{mod}{m}_i$):

• $20\mathrm{mod}3=2$; need $2y_1\equiv 1(\mathrm{mod}3)$ → $y_1=2$ ($2\cdot 2=4\equiv 1$).
• $15\mathrm{mod}4=3$; need $3y_2\equiv 1(\mathrm{mod}4)$ → $y_2=3$ ($3\cdot 3=9\equiv 1$).
• $12\mathrm{mod}5=2$; need $2y_3\equiv 1(\mathrm{mod}5)$ → $y_3=3$ ($2\cdot 3=6\equiv 1$).

Assemble: $x\equiv 2\cdot 20\cdot 2+3\cdot 15\cdot 3+1\cdot 12\cdot 3=80+135+36=251.$ $251\mathrm{mod}60=251-4\cdot 60=11.$ $\boxed{x\equiv 11(\mathrm{mod}60)}$ Check: $11\equiv 2(\mathrm{mod}3)$ ✓, $11\equiv 3(\mathrm{mod}4)$ ✓, $11\equiv 1(\mathrm{mod}5)$ ✓.

WHAT we check first (WHY: for non-coprime moduli the generalized rule is solvable iff the two required-values agree modulo the shared gcd): $a_1\equiv a_2(\mathrm{mod}\gcd (4,6))?3\equiv 5(\mathrm{mod}2)?1\equiv 1\text{ ✓ — consistent.}$ So solutions exist. Solve by substitution. $x=3+4k$. Then $3+4k\equiv 5(\mathrm{mod}6)\Rightarrow 4k\equiv 2(\mathrm{mod}6)$. Divide the whole congruence by $\gcd (4,6,2)$… carefully: $4k\equiv 2(\mathrm{mod}6)$ ⇔ $2k\equiv 1(\mathrm{mod}3)$ (divided by $2$, and modulus $6/2=3$). Then $2^{-1}\mathrm{mod}3=2$, so $k\equiv 2(\mathrm{mod}3)$, i.e. $k=2+3t$. $x=3+4(2+3t)=11+12t.$ The true period is $\mathrm{lcm}(4,6)=12$, not $4\cdot 6=24$. $\boxed{x\equiv 11(\mathrm{mod}12)}$ Check: $11\equiv 3(\mathrm{mod}4)$ ✓, $11\equiv 5(\mathrm{mod}6)$ ✓.

WHY the design works: $M_i=M/m_i$ is a product that includes every modulus except $m_i$. So $m_j$ (for $j\ne i$) is one of its factors, giving $M_i\equiv 0(\mathrm{mod}{m}_j)$. Multiplying by $y_i$ and $a_i$ keeps that zero. Meanwhile, by construction $M_i{y}_i\equiv 1(\mathrm{mod}{m}_i)$, so the single surviving term equals $a_i\cdot 1=a_i$ in the $m_i$ world.

Concrete check with $a_2{M}_2{y}_2=3\cdot 15\cdot 3=135$:

• $135=45\cdot 3\Rightarrow 135\equiv 0(\mathrm{mod}3)$ ✓ (vanishes)
• $135=27\cdot 5\Rightarrow 135\equiv 0(\mathrm{mod}5)$ ✓ (vanishes)
• $135=33\cdot 4+3\Rightarrow 135\equiv 3(\mathrm{mod}4)$ ✓ (survives, contributes exactly $a_2=3$)

So the term is a "switch": ON for its own modulus, OFF for all others.

Translate the words into congruences (WHAT: "by 3s, 2 remain" = "remainder $2$ mod $3$"): $x\equiv 2(\mathrm{mod}3),x\equiv 3(\mathrm{mod}5),x\equiv 2(\mathrm{mod}7).$ Moduli $3,5,7$ are pairwise coprime, $M=105$. $M_1=35,M_2=21,M_3=15.$ Inverses:

• $35\mathrm{mod}3=2$; $2y_1\equiv 1(\mathrm{mod}3)\Rightarrow y_1=2$.
• $21\mathrm{mod}5=1$; $y_2=1$.
• $15\mathrm{mod}7=1$; $y_3=1$.

$x\equiv 2\cdot 35\cdot 2+3\cdot 21\cdot 1+2\cdot 15\cdot 1=140+63+30=233.$ $233\mathrm{mod}105=233-2\cdot 105=23.$ $\boxed{x\equiv 23(\mathrm{mod}105)}$ Smallest positive count = 23 eggs. Check: $23\equiv 2(\mathrm{mod}3)$ ✓, $23\equiv 3(\mathrm{mod}5)$ ✓, $23\equiv 2(\mathrm{mod}7)$ ✓.

$M=7\cdot 11\cdot 13=1001$. $M_1=1001/7=143,M_2=1001/11=91,M_3=1001/13=77.$ Inverses:

• $143\mathrm{mod}7$: $143=20\cdot 7+3$, so $3y_1\equiv 1(\mathrm{mod}7)\Rightarrow y_1=5$ ($3\cdot 5=15\equiv 1$).
• $91\mathrm{mod}11$: $91=8\cdot 11+3$, so $3y_2\equiv 1(\mathrm{mod}11)\Rightarrow y_2=4$ ($3\cdot 4=12\equiv 1$).
• $77\mathrm{mod}13$: $77=5\cdot 13+12$, so $12y_3\equiv 1(\mathrm{mod}13)$. Since $12\equiv -1$, $-y_3\equiv 1\Rightarrow y_3=12$.

$x\equiv 6\cdot 143\cdot 5+4\cdot 91\cdot 4+8\cdot 77\cdot 12.$ Compute each: $6\cdot 143\cdot 5=4290$; $4\cdot 91\cdot 4=1456$; $8\cdot 77\cdot 12=7392$. Sum $=4290+1456+7392=13138$. $13138\mathrm{mod}1001$: $13\cdot 1001=13013$, remainder $13138-13013=125$. $\boxed{x\equiv 125(\mathrm{mod}1001)}$ Check: $125=17\cdot 7+6\equiv 6(\mathrm{mod}7)$ ✓; $125=11\cdot 11+4\equiv 4(\mathrm{mod}11)$ ✓; $125=9\cdot 13+8\equiv 8(\mathrm{mod}13)$ ✓.

Coprimality: $9=3^2$, $5$, $11$ share no prime → pairwise coprime, so period $=9\cdot 5\cdot 11=495$. $M=495$, $M_1=55,M_2=99,M_3=45.$ Inverses:

• $55\mathrm{mod}9$: $55=6\cdot 9+1\Rightarrow 55\equiv 1$, so $y_1=1$.
• $99\mathrm{mod}5$: $99=19\cdot 5+4\Rightarrow 99\equiv 4$, need $4y_2\equiv 1(\mathrm{mod}5)\Rightarrow y_2=4$ ($4\cdot 4=16\equiv 1$).
• $45\mathrm{mod}11$: $45=4\cdot 11+1\Rightarrow 45\equiv 1$, so $y_3=1$.

$x\equiv 1\cdot 55\cdot 1+4\cdot 99\cdot 4+7\cdot 45\cdot 1=55+1584+315=1954.$ $1954\mathrm{mod}495$: $3\cdot 495=1485$, $1954-1485=469$. $\boxed{x\equiv 469(\mathrm{mod}495)}$ Check: $469=52\cdot 9+1\equiv 1(\mathrm{mod}9)$ ✓; $469=93\cdot 5+4\equiv 4(\mathrm{mod}5)$ ✓; $469=42\cdot 11+7\equiv 7(\mathrm{mod}11)$ ✓. Period confirmed: the next solution is $469+495=964$, and no smaller step repeats all three remainders since $\mathrm{lcm}(9,5,11)=495$.

WHAT we do: subtract the two solutions and study the difference $d=x-x^{\prime }$. Because $x\equiv a_i$ and $x^{\prime }\equiv a_i(\mathrm{mod}{m}_i)$, subtracting gives $d=x-x^{\prime }\equiv 0(\mathrm{mod}{m}_i)\text{for every }i.$ So each $m_i$ divides $d$. WHY coprimality now matters: if several numbers each divide $d$ and are pairwise coprime, then their product divides $d$ (a divisor built from disjoint prime factors). Hence $m_1{m}_2\cdots m_k=M\mid d,$ which is exactly $x\equiv x^{\prime }(\mathrm{mod}M)$. Any two solutions coincide modulo $M$, so the solution in $\{0,\dots ,M-1\}$ is unique. $■$

(Note: without coprimality, "each $m_i\mid d$" only gives $\mathrm{lcm}(m_i)\mid d$, not $\prod m_i\mid d$ — which is precisely why the period shrinks in L3.1.)

One-line answers to lock it in. Which levels needed a modular inverse? ::: L2, L4, L5 — every construction-formula problem. What replaces $\prod m_i$ as the period when moduli aren't coprime? ::: $\mathrm{lcm}(m_1,\dots ,m_k)$. The consistency condition for non-coprime solvability? ::: $a_i\equiv a_j(\mathrm{mod}\gcd (m_i,m_j))$ for all pairs.