Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A Party Trick

  1. Sep 10, 2003 #1
    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.

    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?
  2. jcsd
  3. Sep 11, 2003 #2


    User Avatar
    Staff Emeritus
    Gold Member
    Dearly Missed

    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.
  4. Sep 12, 2003 #3
    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
    but it's not working. I was trying to solve the sample problem. Here it is:
    Code (Text):
    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
    Code (Text):
    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):
    Code (Text):
    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 n1 but the answer to the example says the equations should be
    Code (Text):
    (-13)*3 + 2*20 =1
    instead of
    1 = -20 + 7(3)
    The others (ni) also come out wrong. What did i do to upset the math Gods so (or to get it wrong)?


    #EDIT: Added the links
    Last edited: Sep 12, 2003
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook