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.

I'm in 8th grade and my geometry teacher recommended that I read the art of problem solving. So I did and I have now read the chapter called "Integers". I am now doing some of the problems in the section and I came across this one which has stumped me. The question reads:

Find the smallest positive integer which when divided by 10 leaves a remainder of 9, when divided by 9 leaves a remainder of 8, by 8 leaves a remainder of 7, ect., down to where, when divided by 2, it leaves a remainder of 1.

I approached this problem by writing what the possible numbers could be. For when divided by 10 with a remainder of 9, I noticed that all the possible answers had to end in a 9 so I looked for numbers that ended in a 9 for the other conditions. For when it was divided by 2 with a remainder of 1 I concluded that it had to be the 5th, 10th, 15th, ect., term. and for when divided by 3 it had to be the 10th, 20th, ect., term. The problem is I have no idea on how I would find where all of these would fall on the same number? I am looking for a suggestion on how I would use the knowledge I already have to solve the problem.

share|improve this question
2  
One thing you might notice is that any number that ends in 9 leaves a remainder of 1 when you divide it by 2. So you can ignore that condition. –  MJD Nov 30 '12 at 2:25
2  
Let $M$ be the least common multiple of the numbers $2$ o $10$. It does not take long to compute $M$. Then you can observe that $a$ and $b$ have the same remaainders on division by $2$, $3$, and so on up to $10$ if and only if they have the same remainder on division by $M$. That should give a start. There is then a very cute trick that gives you the answer, in this case. –  André Nicolas Nov 30 '12 at 2:38
    
@MJD That is a good point, but the number still must end in a 9 –  Andrew Delgadillo Nov 30 '12 at 2:38

1 Answer 1

up vote 2 down vote accepted

You are stepping into modular arithmetic. Basically you work with the remainders after division by something. For example, if you work $\pmod 6$ the possible remainders are $0,1,2,3,4,5$. You can probably convince yourself that you can add, subtract, and multiply any example of numbers and take the remainder before or after the operation and get the same result. That is, if $k=6m+a, l=6n+b$, the remainder of $k+l$ on division by $6$ is the same as the remainder of $k+l$ on division by $6$ and similarly for the other operations. We write that $k+l \equiv a+b \pmod 6$

You are being asked to solve

$n \equiv 9 \pmod {10} \\ n\equiv 8 \pmod 9 \\ n \equiv 7 \pmod 8$

and so on. The Chinese remainder theorem (CRT) guarantees a solution when the moduli are coprime (which they are not here) and says the solutions (if they exist) recur at the least common multiple of the moduli. For this problem there is a trick. You could notice that the equations are the same as

$n \equiv -1 \pmod {10} \\ n\equiv -1 \pmod 9 \\ n \equiv -1 \pmod 8$

and so on. You might notice that one solution is $-1$, so you can find the least common multiple of $2,3,4,\ldots 10$, subtract $1,$ and there you are. This wouldn't work if the remainders didn't have this nice pattern. If they were "random numbers" and the moduli were large you would have to use the full power of the theorem to find the answer.

If the remainders were "random numbers" but the moduli were small, you could also use the CRT in the approach you describe. First find an answer for moduli $2$ and $3$. It isn't hard to see that $5$ is a solution. Then the solutions recur at LCM$(2,3)=6$ so your candidates are $5,11,17,\ldots$ Now look for a solution with modulo $4$ added in and find $11$. Now the solutions recur with period $12$, so they are $11,23,35,\ldots$ Add modulo $5$ into the mix and find $59$. Each time, you only have to look at the number of the modulus or less possibilities and you will get there pretty quickly.

share|improve this answer
    
Thank you! Modular arithmetic was mentioned in the book, but I didn't think to think of it that way. –  Andrew Delgadillo Nov 30 '12 at 3:16
    
@AndrewDelgadillo: It is quite useful for Diaphontine equations, as well. If you read and understand all the answers Bill Dubuque has written on this site, you will be an expert. –  Ross Millikan Nov 30 '12 at 3:34

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.