Find minimal $x\in\Bbb N$ that solves the linear congruence I need to find minimal $x\in\Bbb N$ that solves the linear congruences: 
$6x \equiv 2 \pmod {\!4}$
$3x \equiv 6 \pmod {\!9}$
$x  \equiv 15 \pmod {\! 17}$
I divided the first congruence by $2$ and the second congruence by $3$, then used the Chinese remainder theorem.
I got $x\equiv 393 \pmod {2\cdot 3\cdot 17} $
I checked that this solution actually solves the 3 equations.
But is it the smallest one? If so, then why ? 
Thanks.
 A: Your congruences may be reduced to 
$x\equiv 1\pmod{2}$
$x\equiv 2 \pmod{3}$
$x\equiv 15 \pmod{17}$
We have $\mod {17}$, $x\equiv 15\equiv 32\equiv 49 \equiv 66 \equiv 83$.
And we note that $83$ satisfies the other two congruences.  
The general solution is then $x\equiv 83 \pmod{102}$
A: From the comments you're interested in using Chinese Remainder Theorem in general. Here is one algorithm you can use.   
Inbetween, instead of using clever manipulations, you can use EEA, etc. as explained below.   
$x\equiv 1\pmod{\! 2}\iff (x=2k+1$ for some $k\in\Bbb Z)$.   
$\,\bmod{3}\!:\ \ \ x\equiv 2\iff \color{#00F}2k+1\equiv 2\iff \color{#00F}{-1}k\equiv 1\iff k\equiv -1\equiv 2$   
$\iff (k=3n+2$ for some $n\in\Bbb Z)\iff x=2(3n+2)+1=6n+5$.   
$\,\bmod{17}\!:\ \ \ x\equiv 15\equiv -2\iff 6n+5\equiv -2\iff 6n\equiv -7\equiv -24$
$\stackrel{:6}\iff n\equiv -4\equiv 13\iff n=17m+13$ for some $m\in\Bbb Z$.    
$\iff x=6(17m+13)+5=102m+83$.    
We've used clever manipulations here. If you want to solve it algorithmically in a short time, the numbers are huge and you don't see a simple solution to $ax\equiv b\pmod{\! m}$ using manipulations like those above, then use either Extended Euclidean algorithm or what Bill Dubuque calls Gauss's algorithm. Here is how you apply EEA:
$$ax\equiv b\pmod{\! m}\iff ax+mk=b$$ for some $k\in\Bbb Z$. This has a solution $(x,k)$ iff $(a,m)\mid b=:(a,m)h$ (see here).   
Using EEA you find $x_1,k_1\in\Bbb Z$ such that $$ax_1+mk_1=(a,m)\iff a(x_1h)+m(k_1h)=b$$  
So $x\equiv x_1h\pmod{\! m}$ is your solution.
