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.

There are $7$ thieves. They steal diamonds from a diamond merchant and run away into the jungle. Whilst they're running, night falls and they decided to rest in the jungle. When everybody is sleeping, two best friends get up and decided to split the diamonds between themselves and run away.

So they start splitting them, only to find that they are left with one extra diamond. So they decided to wake up a $3^{\mathrm{rd}}$ one divide the diamonds again....only to their surprise, they still find one extra diamond. So they decided to wake a $4^{\mathrm{th}}$, and again the same thing. The $5^{\mathrm{th}}$ is woken up... still one extra. $6^{\mathrm{th}}$, and still one extra. They then wake the $7^{\mathrm{th}}$ and all the diamonds are distributed equally.

How many diamonds did they steal in total?

Quite clearly, just by reading this, we know the number of diamonds (let's say $x$) has to be odd. It also has to end in $1$, otherwise we can't get the $1$ remainder with the $5$ robbers.

So we want to find a value that, $x$ that is:

$$x \equiv 1 \mod 2$$ $$\, \, \, \,\, \equiv 1 \mod 3$$ $$\, \, \, \,\, \equiv 1 \mod 4$$ $$\, \, \, \,\, \equiv 1 \mod 5$$ $$\, \, \, \,\, \equiv 1 \mod 6$$

and

$$x \equiv 0 \mod 7.$$

I thought it was a Chinese remainder theorem question but I can't seem work it out with $7$ equations. What I have said is that as they are all $1 \mod \mathrm{something}$, their modular inverses will all just be $1$. So the answer should be

$$x \equiv (2 \cdot 1 \cdot 1) + (3 \cdot 1 \cdot 1) + (4 \cdot 1 \cdot 1) + (5 \cdot 1 \cdot 1) + (6 \cdot 1 \cdot 1) + (7 \cdot 0) \mod 5040$$ $$ \equiv 2 + 3 + 4 + 5 + 6 \mod 5040 $$ $$ \equiv 20 \mod 5040, $$

but this gives me the wrong answer as quite clearly it's always going to be even.

What have I done wrong?

share|improve this question

2 Answers 2

up vote 3 down vote accepted

The Chinese remainder theorem works only if the numbers are pairwise coprime. So lets just apply the CRT to the following conditions (which imply the remaining conditions): $$x \equiv 1 \mod 3,4,5$$ and $$x \equiv 0 \mod 7.$$ From the first three we get $x \equiv 1 \mod 60$. Then the fourth condition impies $x \equiv 301 \mod 420$.

share|improve this answer

The part where you go wrong is when you apply the Chinese Remainder Theorem. To apply the Chinese Remainder theorem, we needed the numbers $2,3,4,5,6$ to be pairwise co-prime which is not the case. However, in this case observe that all of $2,3,4,5,6$ divides $x-1$ which happens iff their lcm divides $x-1$ and hence we obtain the equations $$x \equiv 1 \pmod {60} \space \space \space \space \space \space \space x \equiv 0 \pmod {7}.$$ Since ${\rm gcd}(60,7)=1$, you can now apply CRT.

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.