Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
This is the math problem hiding in the children's song "The Ants Go Marching." –  Sammy Black Feb 21 '12 at 7:39

3 Answers 3

up vote 11 down vote accepted

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

share|improve this answer
    
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) –  André Nicolas 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$. –  André Nicolas Feb 21 '12 at 7:48
1  
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$. –  yohBS 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. –  Thomas Andrews Apr 23 '13 at 14:41

first you will divide 3/2 and you will get 1 . then you wll divide 8/3 you get 2 . then you divide 15/4 you get 3 . divide 24/5 you get 4 . you will do this process and you will get reminder.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.