Find the smallest positive integer so that the remainder when it is divided by $17,15,13$ is $3,2,1$ respectively.
This question can be solved using Chinese remainder theorem, but the theorem gives any integer, not the smallest.
For example, we have, letting $n_1, n_2, n_3 = 17, 15, 13$ and $a_1, a_2, a_3 = 3, 2, 1$ and $N_j = \frac{1}{n_j}\cdot\prod n_i$:
$$x = \sum a_i N_i^{\phi(n_i)} \\x = 3\cdot(15\cdot 13)^{16} + 2\cdot(17\cdot13)^{8} + (17\cdot 15)^{12}$$
Essentially here $ N_1^{15} = (15\cdot 13)^{15}$ is root of $N_1 x \equiv 1(\mathrm{mod} \ 17)$
By choosing different roots, we get different answers, but how can we find the minimum $x$ that satisfies the condition?
Just so in this case the minimum is $1652$
$\endgroup$ 63 Answers
$\begingroup$CRT becomes trivial if we exploit the innate Arithmetic Progression (A.P.) structure. Note
$$\begin{align} &x\equiv 1\!\!\pmod{\!13}\\ &x\equiv 2\!\!\pmod{\!15}\\ &x\equiv 3\!\!\pmod{\!17}\\[.2em] {\rm i.e.}\ \ \ &x\equiv 1\!+\!k\!\!\!\pmod{\!13\!+\!2k},\ \ k=0,1,2\end{align}$$
with progressions: $\ 1,2,3 = 1\!+\!k,\ $ & $\,\ 13,15,17 = 13\!+\!2k.\,$ Hence
$\!\!\bmod \color{#c00}{13\!+\!2k}\!:\,\ x\equiv 1\!+\!k\iff 2x \equiv 2\!+\!\color{#c00}{2k}\equiv 2\color{#c00}{-13}\equiv -11\iff 2x\!+\!11\equiv 0$
So $\ 13,15,17\mid 2x\!+\!11 \!\iff\! n\!=\!13(15)17\mid 2x\!+\!11,\,$ by lcm = product for pair-coprimes.
So $\bmod n\!:\,\ 2x \equiv -11\equiv n\!-\!11\iff x \equiv (n\!-\!11)/2\equiv \bbox[5px,border:1px solid #c00]{\!\!1652}\:$ by $\,n=3315\,$ is odd.
Hence $\ x = 1652 + 3315\,k,\, $ so $\,x = 1652\,$ is clearly the smallest positive solution.
Remark $\ $ If modular fractions are known then more clearly we have by CCRT
$$ x\equiv \dfrac{-11}2\!\!\! \pmod{\!13,15,17} \iff x\equiv \dfrac{-11}2\!\!\! \pmod {\!13\cdot 15\cdot 17}\qquad\qquad$$
More generally the same method shows that if $\,(a,b) = 1\,$ then
Theorem $\ \left\{\:\!x\equiv d\!+\!ck\pmod{\!b\!+\!ak}\:\!\right\}_{k=0}^{m_{\phantom{|}}}\!\!$ $\iff\! x\equiv \dfrac{ad\!-\!bc}a\pmod{{\rm lcm}\{b\!+\!ak\}_{k=0}^{m_{\phantom{|}}}} $
Proof $ $ by $\,(a,b\!+\!ak)=(a,b)=1,\,$ LHS $\!\overset{\times\ a}\iff\!\bmod \color{#c00}{b\!+\!ak}\!:\ ax\equiv ad\!+\!c(\color{#c00}{ak})\equiv ad\!\color{#c00}{-b}c\!$ $\!\iff\! ax\!-\!(ad\!-\!bc)\,$ is divisible by all moduli $\!\iff\!$ it is divisible by their lcm $n\, $ (since $\,a\,$ is coprime to each modulus $\,n_k\,$ it is invertible $\!\bmod n_k\,$ so it is invertible mod their lcm $ n)$.
OP is special case $\ a,b,c,d = 2,13,1,1\,$ so $\ x\equiv \dfrac{2(1)\!-\!13(1)}2\equiv\dfrac{-11}2\!\pmod{\!17\cdot16\cdot13}$
See this answer for how to choose the residues in A.P. when only the moduli are in A.P.
$\endgroup$ 2 $\begingroup$The system is $$\begin{cases} x\equiv 3 \pmod{17} \\ x\equiv 2 \pmod{15} \\ x\equiv 1 \pmod{13} \end{cases}$$and it's solution is given by $x\equiv 1652 \pmod{3315}$, which means $$x=1652+3315t$$for some $t\in \mathbb{Z}$. Making $t=0$ gives you the smallest positive integer (in this case, the remainder).
$\endgroup$ 1 $\begingroup$If $x\equiv3\mod 17$ and $x\equiv2\mod 15,$ then $17a+3\equiv 15b+2\mod 17\times15,$
so $17a+3\equiv2\mod 15,$ so $17a\equiv -1 \mod 15,$ so $2a\equiv -1\mod 15,$ so $a\equiv7 \mod 15,$
so $x=17(15c+7)+3=255c+122$.
If also $x\equiv1\mod 13$ then $255c+122\equiv13e+1$ so $255c+122\equiv1 \mod 13,$
so $255c\equiv-121\mod 13,$ so $8c\equiv9 \mod 13,$ so $c\equiv45\equiv6\mod 13,$ so $c=13d+6,$
so $x=255c+122=255(13d+6)+122=3315d+1652.$
$\endgroup$ 2
