# Thread: Simple Single Unknown Word Problem

1. ## Simple Single Unknown Word Problem

Or at least I think it is, but this one is driving me crazy.

Hundreds of fruits are loaded into a truck. If divided between 7 people then 3 are left, if divided between 11 people then 7 are left, and if divided between 13 people then 1 is left. How many pieces of fruit are there?
No matter what I do here, I can't find any value where all of these are true. I've even plugged in the correct answer (612) into a few equations and none of them work.

This doesn't come from an actual mathematics textbook, so I'm wondering if maybe it's just a bad question.

Would appreciate any help, thanks.

2. This is not a regular type of problem where you have n equations and n unknowns and where there is a unique solution. You could write equations like x = 7 * k + 3 where x is the total number of fruit and k is what each of seven people gets, but then you get three equations with four unknowns. However, there is an additional restriction that k is an integer, which is not taken into account when systems of equations are solved in a regular way. Even with this restriction, there are infinitely many solutions.

The correct way to solve this type of problems is to use the Chinese remainder theorem. (See Dr. Math and Wikipedia.) Unfortunately, to understand the proof you probably need to know modular arithmetic.

The problem asks for an x such that

x leaves a remainder 3 when divided by 7
x leaves a remainder 7 when divided by 11
x leaves a remainder 1 when divided by 13

Chinese remainder theorem is applicable here because 7, 11 and 13 are pairwise coprime. Then one can show that there exist numbers r1, r2, r3 and p1, p2, p3 such that

r1 * 7 + p1 * 11 * 13 = 1
r2 * 11 + p2 * 7 * 13 = 1
r3 * 13 + p3 * 7 * 11 = 1

One set of solutions is

r1 = 41; p1 = -2
r2 = -33; p2 = 4
r3 = 6; p3 = -1

Let e1 = p1 * 11 * 13 = -286, e2 = p2 * 7 * 13 = 364, e3 = p3 * 7 * 11 = -77. Then

e1 leaves a remainder 1 when divided by 7 and a remainder 0 when divided by 11 and 13
e2 leaves a remainder 1 when divided by 11 and a remainder 0 when divided by 7 and 13
e3 leaves a remainder 1 when divided by 13 and a remainder 1 when divided by 7 and 11

So, one can take x = 3 * e1 + 7 * e2 + 1 * e3 = 1613. One can also add and subtract 7 * 11 * 13 = 1001 at will. In particular, 1613 - 1001 = 612 is another solution.

3. 612 / 7 = 87 ; r=3 : or 612 - 87*7 = 3
612/ 11 = 55 ; r=7 : or 612 - 55*11 = 7
612/ 13 = 47 ; r=1 : or 612 - 47*13 = 1

Perhaps you needed another coffee ?

4. Sure, if you provide a correct answer with it I was showing how to come up with an answer when one does not know it.

5. Originally Posted by emakarov
Sure, if you provide a correct answer with it I was showing how to come up with an answer when one does not know it.
I realise that; was unaware of your post when I posted mine; your "1001" is "shrewd" !

I really wasn't providing "the answer"; just showing him that his 612 was correct...

6. Ah, thanks you two.

Have never done anything with modular arithmetic, I was just really afraid I'd forgotten algebra or something.