Back to Advanced source practice
AdvancedVery HardTITA Source: LaTeX
Number System/Remainders / CRT

Question

TITA} Let NN be the smallest positive integer such that NN leaves remainder 33 when divided by 77, remainder 55 when divided by 1111, and is divisible by 1313. If MM is the next positive integer (after NN) satisfying all three conditions, find the value of MNM-N.

Answer

MN=1001.M - N = 1001.

Detailed solution

N3(mod7), N5(mod11), N0(mod13).N\equiv 3\pmod 7,\ N\equiv 5\pmod{11},\ N\equiv 0\pmod{13}.

Since 7,11,137,11,13 are pairwise coprime, by the Chinese Remainder Theorem, NN is uniquely determined modulo 71113=1001.7\cdot 11\cdot 13 = 1001.

Finding NN: Write N=13kN=13k. Then

13k3(mod7)6k3k3k4(mod7),13k5(mod11)2k5k56=308(mod11).\begin{align*} 13k \equiv 3\pmod 7 &\Rightarrow 6k \equiv 3 \Rightarrow -k \equiv 3 \Rightarrow k \equiv 4\pmod 7, 13k \equiv 5\pmod{11} &\Rightarrow 2k \equiv 5 \Rightarrow k \equiv 5\cdot 6 = 30 \equiv 8 \pmod{11}. \end{align*}

(216(mod11)2^{-1}\equiv 6 \pmod{11} since 26=1212\cdot 6 = 12\equiv 1.)

Combine: k=7m+4k=7m+4, then 7m+48(mod11)7m4m48=3210(mod11)7m+4\equiv 8\pmod{11} \Rightarrow 7m\equiv 4 \Rightarrow m\equiv 4\cdot 8=32\equiv 10\pmod{11} (since 78=561(mod11)7\cdot 8 = 56\equiv 1\pmod{11}).

So m=11j+10m = 11j+10, k=77j+74k = 77j+74. Smallest positive kk is 7474, giving N=1374=962.N = 13\cdot 74 = 962.

Verification: 962=7137+3962 = 7\cdot 137 + 3 \checkmark, 962=1187+5962 = 11\cdot 87 + 5 \checkmark, 962/13=74962/13 = 74 \checkmark.

The next solution is N+1001=1963N + 1001 = 1963. So M=1963M = 1963 and MN=1001.M-N = 1001.

Why this is CAT-level: The question looks like a standard CRT problem, but the third condition (``divisible by 1313'') is the moduli twist -- it must be expressed as N0(mod13)N\equiv 0\pmod{13}. Two layers of modular inversion (21(mod11)2^{-1}\pmod{11}, 71(mod11)7^{-1}\pmod{11}) are required. The clean route exploits the fact that MNM-N is simply lcm(7,11,13)=1001\mathrm{lcm}(7,11,13)=1001, sidestepping the entire computation of NN itself. Students who don't see this shortcut compute NN first and then add the LCM -- which works but is slower.

Answer: MN=1001.M - N = 1001.