1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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