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