Unravelling the Mystery of a Party Trick

[Hyperreality]

I was reading In Code by Saray Flannery,one of the problem in the book bothered me, it is not the problem itself, it is the solution.

A Party Trick
If someone tells me 2, 2 and 3 are the remainders when she divides her age by 3, 5 and 7 respectively then I can work out her age.

Solution:
Let x = 2, y = 2, z = 3 and a = the age of the girl. Then she used this formula:

a = (70x + 21y + 15z)mod n
= (120 + 42 + 45)mod (3 x 5 x 7)
= 227mod105
= 17 years old

I have no idea of how this works. Where does this formula come from? There must be a logical way to explain this right? And are there any other ways of solving this kind of problem?

 

[selfAdjoint]

This is an example of a famous result in elementary number theory called the Chinese Remainder Theorem. The site does a better job of explaining what's involved than I can.

 

[HBar]

I've been playing around with this theorem, but for the life of me i can't get it to work. I've been reading the wikipedia articles on chinese remainder theorem and euclidean algorthim
http://www.wikipedia.org/wiki/Chinese_remainder_theorem
http://www.wikipedia.org/wiki/Extended_Euclidean_algorithm
but it's not working. I was trying to solve the sample problem. Here it is:

x=2(mod 3)
x=3(mod 4)
x=2(mod 5)
"syntax": x=a[sub]i[/sub](mod n[sub]i[/sub])

First i have tried finding the values that satify

n = n[sub]1[/sub],...,n[sub]k[/sub]
r*n[sub]i[/sub] + s*n/n[sub]i[/sub]=1

I've been using the extended euclidean algorithm for that. Here (color coded for readability):

20/3 = 6 r 1 => 2 = 20 - 6(3)
3/2 = 1 r 1 => [COLOR=red]1 = 3 - 1(2)[/COLOR]  => 1= 3 -1 (20 - 6(3)) => [COLOR=red]1 = -20 + 7(3)[/COLOR]

That was just for n₁ but the answer to the example says the equations should be

(-13)*3 + 2*20 =1
instead of
1 = -20 + 7(3)

The others (n_i) also come out wrong. What did i do to upset the math Gods so (or to get it wrong)?

-HBar

#EDIT: Added the links