Smallest integer which leaves remainder 3, 2, 1 when divided by 17, 15, 13

Solution 1:

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.

Solution 2:

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).