Get the minimum number which can be divided by 63 and modulus 40 equals 1 I have got a puzzle to find out the smallest n (natural number) that:
n modulus 2 is 1.
n modulus 3 is 0.
n modulus 4 is 1.
n modulus 5 is 1.
n modulus 6 is 3.
n modulus 7 is 0.
n modulus 8 is 1.
n modulus 9 is 0.   
It is not hard to find out that n % 63 == 0 and n % 40 == 1. Then I wrote a small program to find out the smallest n is 441. 
But my question is, is there any mathematical way in finding out the smallest number in the last part, rather than using a program to traverse? Or is traverse the only approach in this situation? 
 A: One way to solve this problem is by using the Euclidean Algorithm. You know $n=63k$ and $n=40j+1$ for some $j,k\in\mathbb{N}$. Setting these equal to each other, you find $63k-40j=1$. If you continually divide and keep track of remainders using the Euclidean Algorithm, you find:
\begin{align*}
63&=1\cdot40&+23\\
40&=1\cdot23&+17\\
23&=1\cdot17&+6\\
17&=2\cdot6&+5\\
6&=1\cdot5&+1\\
\end{align*}
With this system of equations, you can now start from the bottom and work your way to the top to express $1$ as a linear combination of $63$ and $40$:
\begin{align*}
1&=6-1\cdot5\\
&=6-1\cdot(17-2\cdot6)\\
&=3\cdot6-1\cdot17\\
&\dots\\
&=7\cdot63-11\cdot40\\
\end{align*}
Since $7$ and $11$ are relatively prime, there is no smaller multiple of $63$ than $7\cdot63=441$ which satisfies the original problem.
A: Your preliminary results capture all the prime powers in the given modulus values, so those two statements allow a complete solution through the Chinese Remainder theorem. 
Since the inverse of $63\equiv 23 \bmod 40$ is $7$, we find that $7\times 63 = 441$ gives us the combination we require, $441\equiv 0 \bmod 63$ and $441\equiv 1 \bmod 40$. There will be further solutions every $40\times 63=2520$, eg at $2961$
