# 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

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??

• This is the math problem hiding in the children's song "The Ants Go Marching." Feb 21 '12 at 7:39
• Solve the simultaneous congruences, $$x\equiv 1\pmod 2$$ $$x\equiv 2\pmod 3$$$$x\equiv 3\pmod 4$$$$x\equiv 4\pmod 5$$$$x\equiv 5\pmod 6$$$$x\equiv 6\pmod 7$$$$x\equiv 7\pmod 8$$$$x\equiv 8\pmod 9$$$$x\equiv 9\pmod {10}$$ using Chinese Remainder Theorem.
– user170039
Dec 9 '15 at 2:57

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$.

• wat do u mean by "−1 has the desired property. The numbers that have the desired property are akk numbers of the form −1+kM" hope u wont mind explaining in a bit details.
– Jay
Feb 21 '12 at 7:23
• @Jay: Sorry about the typo! The "akk" is all, my typing hand slipped. I hope the congruence stuff I added clarifies things. But for example, what is the remainder when $-1$ is divided by $6$? We express $-1$ in the form $-1=6q+r$, where $0\le r\le 5$. We have that $q$, the quotient) is $-1$, and therefore $r$, the remainder, is $5$. the same idea works for all the numbers $2$ to $10$. For the second part of your question, first suppose that $M$ is the least common multiple of $2$ up to $10$. Then when we divide $-1+kM$ by any $m$ from $2$ to $10$, we get the same remainder (continued) Feb 21 '12 at 7:43
• (cont) as when we divide $-1$ by $m$, since $m$ divides $M$. Finally, we must show that no positive integer $x<M-1$ works. If $x$ leaves the right remainders, then since $-1$ also leaves the right remainders, $x-(-1)$ must be divisible by all of $2$ up to $10$. So $x+1$ must be divisible by the $\lcm$ of the numbers $2$ to $10$. It follows that $M$ divides $x+1$. The smallest positive $x$ for which this is true is $x=M-1$. Feb 21 '12 at 7:48
• Just for completeness: the least common multiplier of $\{1,2,3,4,5,6,7,8,9,10\}$ is $2520$, so the smallest positive integer satisfying the requirement is $2519$. Feb 21 '12 at 8:20
• It might be easier to see if you just ask "what happens when you add $1$ to such a number?" Then it must be perfectly divisible by $2,3,\dots,10$. So you are trying to find a number $N$ such that $N+1$ is divisible by all these numbers, and the least such $N+1$ is the least common multiple. Apr 23 '13 at 14:41

The smallest such number is 2519. The next number can obtain by the equation 2519x+x-1. Where x can replaced by any whole number

• True, although wouldn't it be easier just to write $2520x-1$? Dec 9 '15 at 2:06