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

Question

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$

Answer 1

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

Answer 2

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

Answer 3

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.