Answers
 1. Find the unique (uptomoduloequivalence) solutions to:

 1. 2 * x == 1 (mod 9)

 5 * 2 * x == 5 * 1 (mod 9)
 1 * x == 5 (mod 9)
 2. 5 * x == 3 (mod 7)

 3 * 5 * x == 3 * 3 (mod 7)
 1 * x == 2 (mod 7)
 3. 9 * x == 6 (mod 12)

 3 * x == 2 (mod 4)
 3 * 3 * x == 3 * 2 (mod 4)
 1 * x == 2 (mod 4)
 x == 2, 6, or 10 (mod 12)
 4. 9 * x == 4 (mod 12)

This was a trick question. There is no solution because 4 is not divisble by gcd(9,12) = 3.
 2. I sent out 150 invitations to a singles mixer. I participated in all of the activities. We did a little mixer game where we paired off into groups of 5, but one group only had 4. Then, we had a sit down dinner with 9 to a table, but three tables ended up with 10. At the end of the evening, everyone left in pairs, except for me. How many people (including me) attended the event (assuming no uninvited guests showed up)?

There must have been at least 30 people because there were three tables of 10. There could not have been more than 151 (assuming I didn't send an invitation to myself).
Because of the mixer game, we know x == 4 (mod 5).
Because of the dinner tables, we know x == 3 (mod 9).
Because of the pairing at the end, we know x == 1 (mod 2).
This gives us that n = 5 * 9 * 2 = 90. We then have:
 N_{1} = 18
 N_{2} = 10
 N_{3} = 45
And:
 a_{1} = 4
 a_{2} = 3
 a_{3} = 1
We have to solve the following linear congruences:
 N_{1} * x_{1} == 1 (mod 5)
 N_{2} * x_{2} == 1 (mod 9)
 N_{3} * x_{3} == 1 (mod 2)
Which are:
 18 * x_{1} == 3 * x_{1} == 1 (mod 5)
 10 * x_{2} == 1 * x_{3} == 1 (mod 9)
 45 * x_{3} == 1 * x_{3} == 1 (mod 2)
These come out to be x_{1} = 2, x_{2} = 1, and x_{3} = 1.
This means that s = 4 * 18 * 2 + 3 * 10 * 1 + 1 * 45 * 1
= 219 . But, this number is only correct modulo n and 219 == 39 (mod 90). So, I must have had 39 or 129 people at my party.Note: I had the math screwed up on this before. My original intent was to a make a problem where the smaller answer was impossible because we knew we had three tables of ten. Oops.
number 2
Anonymous
December 16 2005, 22:29:23 UTC 12 years ago
Re: number 2
patrickwonders
December 19 2005, 03:10:58 UTC 12 years ago
I don't think there's anywhere except human error, yours or mine.
But, mine is blatantly wrong. I'll have to look into why. But, 81 == 4 (mod 5) is clearly false, as is 81 == 3 (mod 9).
I'll fix this entry tomorrow...
Re: number 2
patrickwonders
December 19 2005, 04:30:49 UTC 12 years ago
It turns out, I had just blatantly messed up the Chinese Remainder Theorem and not noticed before.
I corrected both the lesson and the answer. Mine now, coincidentally, agrees with your answer. And, oddly enough, the example that I gave in the text worked out to the same answer even when I did it a blatantly wrong way. Oops.
I am confused about this question
Anonymous
September 30 2006, 05:28:19 UTC 11 years ago
x = 2 (mod 3)
x = 3 (mod 7)
the solution given uses an extra x = 0 (mod 2) and x = 0 (mod 5)why?
Re: I am confused about this question
patrickwonders
September 30 2006, 18:48:20 UTC 11 years ago
Anyhow, for this problem, I would just do this:
x = 2 (mod 3)
x = 3 (mod 7)
So, we've got N_{1} = 7 and N_{2} = 3. So, we want to solve the congruences:
7 * x_{1} = 1 * x_{1} = 1 (mod 3)
3 * x_{2} = 1 (mod 7)
So, x_{1} = 1 and x_{2} = 5.
So, s = 2 * 7 * 1 + 3 * 3 * 5 = 59 == 17 (mod 3*7).
I would stop there, unless there's some extra reason to believe that the answer must be a multiple of 2 and 5. If so, then the answer must be 2 * 5 * 17 = 170.