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$
Best Answer
CRT becomes trivial via 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\overset{\small (2,13+2k)=1}\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
$\bbox[8px,border:1px solid #c00]{{\bf 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(16)13}$
See this answer for how to choose the residues in A.P. when only the moduli are in A.P.