A Party Trick

202
0
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

Staff Emeritus
Gold Member
Dearly Missed
6,764
5
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.
 
67
0
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:
Code:
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:
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:
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:
(-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)?

-HBar

#EDIT: Added the links
 
Last edited:

Related Threads for: A Party Trick

  • Posted
Replies
8
Views
2K
  • Posted
Replies
3
Views
4K
  • Posted
Replies
11
Views
3K
  • Posted
Replies
11
Views
3K
  • Posted
Replies
7
Views
2K
  • Posted
Replies
2
Views
1K
  • Posted
Replies
3
Views
2K
  • Posted
Replies
9
Views
7K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top