3
$\begingroup$

Three brothers A, B and C live together and they all love eating pizza. A has the habit of eating a pizza every 5 days, B every 7 days and C every 11 days. A and C both eat pizzas together on 3 January 2012 and B has a pizza the next day. When will they all three eat pizza together?

I want to solve this exercise using the Chinese Remainder Theorem. I also have the standard solution but I think I don't exactly understand the Chinese Remainder Theorem so far. In our Algebra lecture, we stated it as follows:

Let $a_1, \dots, a_n$ be pairwise relatively prime elements of a principle ideal domain $R$ (is this the correct english term for "Hauptidealring"?). Then, the homomorphism $$R / (a_1, \dots, a_n) \to R/(a_1) \times \dots R/(a_n), \;\;[x] \mapsto ([x], \dots, [x])$$ is an isomorphism.

The standard solution starts as follows: Let $x \in \mathbb{Z}_{\geq 0}$ be the amount of days that has passed since January 3rd. We are looking for the smallest non-negative number $x$ which solves the following system:

$$x \equiv 0 \; \text{mod} \; 5$$ $$x \equiv 0\; \text{mod} \; 11$$ $$x \equiv 1 \; \text{mod} \; 7$$

The numbers 5, 7 and 11 are pairwise coprime hence the Chinese Remainder Theorem tells us that there is a unique solution x mod 385 for this system. How does the Chinese Remainder Theorem tell us something about remainder systems like these? In our case, $R = \mathbb{Z}$ and therefore it gives us an explicit isomorphism $\mathbb{Z}/(5,7,11) \to \mathbb{Z}/(5) \times \mathbb{Z}/(7) \times \mathbb{Z}/(11)$. How can I use this isomorphism to get a unique solution mod 385?

I just don't really understand the Chinese Remainder Theorem and thought looking at applications and standard solutions might help me out but it didn't so far and I'd really appreciate any help.

Thanks in advance.

$\endgroup$
  • $\begingroup$ I'm pretty sure that hauptidealring translates directly to principal ideal ring. I've seen several papers in the 30's and 40's apply this to rings which are definitely not domains. I tried briefly to learn what "domain" is in German, but wiki didn't prove very helpful so I stopped :) $\endgroup$ – rschwieb Jun 27 '13 at 13:11
  • $\begingroup$ The most I found out is that it looks like integral ring is the right term, and so I guess you would call it an "integral hauptidealring," using whatever conventions for combining adjectives there are. $\endgroup$ – rschwieb Jun 27 '13 at 13:18
3
$\begingroup$

The CRT basically says says that the natural projection from $\Bbb Z$ onto that product is surjective.

Being surjective, $z\mapsto(0+5\Bbb Z,0+11\Bbb Z,1+7\Bbb Z)$ for some $z\in \Bbb Z$. By an isomorphism theorem, you turn this into a isomorphism from $\Bbb Z/(385)$ to the product. It is still surjective, and since it is injective, this says the answer $z$ is unique (mod $385$).

One naive way to solve this would be to look at multiples of $55$ and see which one is congruent to $1$ mod $7$.

There is a simple algorithm to compute more complex cases. Let's suppose you want a simultaneous solution to get $(a,b,c)$ instead of $(0,0,1)$. Since 77 is coprime to 5, you can find an inverse mod 5, which turns out to be 3. Then $77\cdot3\cdot a\cong a\pmod{5}$, but it is zero mod 7 and mod 11.

Since 35 is coprime with 11, we can find an inverse mod 7, which turns out to be 6.Then $35\cdot 6\cdot b\cong b\pmod{11}$, but it is zero mod 5 and mod 7.

Finally, 55 has an inverse mod 7, namely 6. Thus $6\cdot 55\cdot c\cong c\pmod{7}$, and zero mod 5 and mod 11.

Summing all of these, we get that $77\cdot 3\cdot a+35\cdot 6\cdot b+55\cdot 6\cdot c=z$ is a solution to the simultaneous modular equations. If you need it to be below 385 you can just reduce it mod 385, or if you need it to be some number you can just increase it mod 385 to get the desired number.

$\endgroup$
  • $\begingroup$ Sorry for my lack of vocabulary, but what do you mean by "it is still onto"? That it is surjective? $\endgroup$ – Huy Jun 26 '13 at 15:14
  • $\begingroup$ @Huy Yes, that's right. Tweaked it accordingly $\endgroup$ – rschwieb Jun 26 '13 at 15:22
  • $\begingroup$ What's the name of the simple algorithm you mention? $\endgroup$ – Huy Jun 26 '13 at 15:23
  • $\begingroup$ @Huy I don't know that it has a name. It's just the little solution algorithm given in basic number theory books when talking about the CRT. $\endgroup$ – rschwieb Jun 26 '13 at 15:26
  • $\begingroup$ Could you edit it into your original answer if it's not too much trouble? I'd appreciate that a lot. I'm not sure if I'm supposed to know it but it can't be any harm. $\endgroup$ – Huy Jun 26 '13 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.