Find smallest number when divided by $2,3,4,5,6,7,8,9,10$ leaves $1,2,3,4,5,6,7,8,9$ remainder.How to go about solving this problem??
[Math] Find smallest number when divided by $2,3,4,5,6,7,8,9,10$ leaves $1,2,3,4,5,6,7,8,9$ remainder
elementary-number-theory
Best Answer
There is no smallest such number. But there is a smallest positive integer.
Note that $-1$ has the desired property. The integers that have the desired property are all the integers of the form $-1+kM$, where $M$ is the least common multiple of the integers $2,3,4,\dots, 10$ and $k$ ranges over the integers. So the smallest positive integer that works is $M-1$. It is not difficult to find $M$.
Remark: This type of problem is in general much more messy to solve. A specified sequence of remainders may not be achievable, and even when it is, efficiently finding an integer that works involves using the Chinese Remainder Theorem, or some equivalent procedure. In our particular case, finding an integer that works was easy, since $-1$ is clearly a solution. Its only flaw is that it is not positive, but that flaw can be dealt with.
What's going on is easier to see if we use congruence notation. We are told that a certain integer $x$ is congruent to $1$ modulo $2$, congruent to $2$ modulo $3$, congruent to $3$ modulo $4$, and so on up to congruent to $9$ modulo $10$. We can restate these congruences in the form $x$ is congruent to $-1$ modulo $2$, $x$ is congruent to $-1$ modulo $3$, $x$ is congruent to $-1$ modulo $4$, and so on up to $x$ is congruent to $-1$ modulo $10$. So $x=-1$ works for every one of our moduli.
Added details: There is something not very intuitive about the remainder when a negative integer like $-1$ is divided by, say, $6$. The congruence notation is quite helpful here, but we will try to do without. The remainder when the number $a$ is divided by $6$ is the integer $r$ such that $0\le r\le 5$, and there is some integer $q$ such that $a=6q+r$.
Apply this definition to $a=-1$. Note that $-1=6q+r$, where $q=-1$ and $r=5$. So the remainder when $-1$ is divided by $6$ is $5$. The same sort of argument works for all the numbers $2$ to $10$.
To show that all the numbers that satisfy our property have the shape $-1+kM$, we must check (i) All the numbers of this form do satisfy our property, and (ii) Nothing else does.
For (i), suppose that $M$ is the least common multiple of the numbers from $2$ to $10$. Then when we divide $-1+kM$ by any $m$ from $2$ to $10$, we get the same remainder as when we divide $-1$ by $m$, because $m$ divides $M$. Since the remainder when $-1$ is divided by $m$ is $m-1$, the remainder when $-1+kM$ is divided by $m$ is also $m-1$, and therefore $-1+kM$ "works."
To prove (ii), suppose that $x$ has the same remainder as $-1$ when $x$ is divided by any of the numbers from $2$ to $10$. Then $x-(-1)$ has remainder $0$ when it is divided by any one of the numbers from $2$ to $10$. It follows that $x+1$ is divisible by the least common multiple of the numbers from $2$ to $10$. Thus $M$ divides $x+1$, which means that $x$ has the shape $kM-1$.