Patrick (patrickwonders) wrote in math_class,
Patrick
patrickwonders
math_class

  • Mood:

NumberTheory101 (#3a): Answers to problems with Chinese Remainder Theorem

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 == 26, 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). 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.

  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

  • 5 comments

number 2

Anonymous

December 16 2005, 22:29:23 UTC 11 years ago

I used a different method, and found the solution x=90t+39, which gives me solutions of 39 and 129, and I can't find a problem in my work. Where would this difference come from, short of human error?

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...

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.

1st-ly thanx for the explanation on CRT (best one thus far). I came to this problem and have a question abuot the way it is solved. the problem given:
x = 2 (mod 3)
x = 3 (mod 7)

the solution given uses an extra x = 0 (mod 2) and x = 0 (mod 5)why?
Thanks. I had read many poor descriptions of the CRT. I wanted to be much more explicit.

Anyhow, for this problem, I would just do this:

x = 2 (mod 3)
x = 3 (mod 7)

So, we've got N1 = 7 and N2 = 3. So, we want to solve the congruences:

7 * x1 = 1 * x1 = 1 (mod 3)
3 * x2 = 1 (mod 7)

So, x1 = 1 and x2 = 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.