Why do put at $k$ only values from $0$ to $6$

Question

Find an integer $x$ whose remainder of the division with $10$ is $3$ and the remainder of the division with $7$ is $4$.

$$x-3=10k \text{ and } x-4=7l$$ From the first equation we get: $ x=10k+3$. Then we replace it at the second equation: $10k+3-4=7l \Rightarrow 10k-7l=1$. Then we solve for that which has the smaller coefficient: $7l=10k-1$ and then we put values at $k$ from $0$ to $6$. Exactly one of them will make $10k-1$ multiple of $7$. $$$$ My question is: Why do we put at $k$ only values from $0$ to $6$ ????

Answer 1

Suppose $10k-1$ is a multiple of $7$ and so $10k-1=7l$. Consider $10(k+7)-1$ which is equal to $(10k-1)+70$. As $10k-1$ is divisible by $7$, so then is $(10k-1)+70$ because $70$ is also divisible by $7$.

We can do the same trick by adding any multiple of $7$ to $k$, so once we have any solution for $k$, we also have a family of solutions that are all within $7$ of each other (we say the solutions are all congruent modulo $7$). It follows that we only need to check in intervals that are $7$ natural numbers long, so we could check $0$ to $6$, or $1$ to $7$, or even $1000$ to $1007$ (although I know which set of values for $k$ I'd rather choose out of that selection).

Answer 2

Hint $\ {\rm mod}\ 7\!:\ 10 k\equiv 1\,$ has a unique solution $\,k\equiv 10^{-1}$ since $\,10\,$ is coprime to $\,7\,$ (recall that, by Bezout, $\,a\,$ is invertible mod $\,m\,$ iff $\,a\,$ is coprime to $\,m).\,$ Since $\ 0,1,\ldots,6\,$ is a complete system of remainders mod $\,7,\,$ the solution $\,k\,$ must be congruent mod $\,7\,$ to one element of this system.

Remark $\ $ The suggested method is essentially a brute force search for the inverse. It can be done more quickly, e.g. $\,{\rm mod}\ 7\!:\ k\equiv \dfrac{1}{10}\equiv \dfrac{-6}{3}\equiv -2\equiv 5.$

Answer 3

You have simplified the problem to finding $k$ such that $10k-1$ is a multiple of $7$.

Simple explanation: If $10n-1$ is a multiple of $7$ such that $n>6$, then also $10(n-7)-1$ is a multiple of $7$. Therefore, if you found a value of $k$ larger than $6$ that is a solution, you could always find a smaller positive value that is a solution. Therefore, if there is a solution, then there is a solution $k\in\{0,1,\dots,,6\}$.

A more interesting explanation: I recommend that you learn some modular arithmetic, which is a powerful tool in number theory. The problem is solving the equation $10k-1\equiv 0 \,(\text{mod }7)$. A brute force way to solve it is to try values $k=0,1,\dots,6$ and see which one works.