#3 (Chinese Remainder Theorem)
#3 (Answers)

math_class: Number Theory 101 (Answers for Class #3)

Answers

1. Find the unique (up-to-modulo-equivalence) 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:

  • N1 = 18
  • N2 = 10
  • N3 = 45

And:

  • a1 = 4
  • a2 = 3
  • a3 = 1

We have to solve the following linear congruences:

  • N1 * x1 == 1  (mod 5)
  • N2 * x2 == 1  (mod 9)
  • N3 * x3 == 1  (mod 2)

Which are:

  • 18 * x1 == 3 * x1 == 1  (mod 5)
  • 10 * x2 == 1 * x3 == 1  (mod 9)
  • 45 * x3 == 1 * x3 == 1  (mod 2)

These come out to be x1 = 2, x2 = 1, and x3 = 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). I couldn't have had more than 151 people. So, I must have had 39 or 129 people.

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.