Determine all natural numbers which
- when divided by 17 leave the remainder 3
- when divided by 6 leave the remainder 1.
Do I have to use Diophantine equations? Could you please help me with this? I don't even know where I should start.
I appreciate all help. Thanks in advance.
On
17 and 6 are relatively prime, so by the Chinese remainder theorem there is a unique solution $N$ modulo $17×6=102$: $$\begin{align}N&\equiv3\bmod17\\ N&\equiv1\bmod6\end{align}$$ Since we only have two congruences to deal with, just guessing a solution is viable, and we see that $N=37$ works. The natural numbers that satisfy the two conditions are therefore $$N=37+102k,\ k\in\Bbb N_0$$
We have two Diophantine equations in $3$ unknowns
$$n = 17 q_1 + 3 \qquad \qquad \qquad n = 6 q_2 + 1$$
Doing (integer) Gaussian elimination,
$$\left[\begin{array}{ccc|c} 1 & -17 & 0 & 3\\ 1 & 0 & -6 & 1\end{array}\right]$$
$$\left[\begin{array}{ccc|c} 1 & -17 & 0 & 3\\ 0 & 17 & -6 & -2\end{array}\right]$$
$$\left[\begin{array}{ccc|c} 1 & 0 & -6 & 1\\ 0 & 17 & -6 & -2\end{array}\right]$$
The solution set in $\mathbb R^3$ is a line parametrized as follows
$$n = 6 m + 1 \qquad \qquad \qquad 17 q_1 = 6 m - 2 \qquad \qquad \qquad q_2 = m$$
However, we are interested in integer solutions only. Hence, $6 m - 2$ must be divisible by $17$. Note that if $m = 6$, then $6 m - 2 = 36 - 2 = 34 = 2 \cdot 17$. If $m = 6 + 17 k$, where $k \in \mathbb N$, then
$$6 m - 2 = 6 (6 + 17 k) - 2 = 17 \cdot (2 + 6 k) = 34 + 102 k$$
Thus, the values of $n$ that satisfy the constraints are given by
$$n \in \color{blue}{\{ 37 + 102 k \mid k \in \mathbb N\}}$$