# Problem of the Week #22 - August 27th, 2012

Status
Not open for further replies.

#### Chris L T521

##### Well-known member
Staff member
Thanks to those who participated in last week's POTW!! Here's this week's problem!

-----

Problem: Three farmers divide equally the rice that they have grown. One goes to a market where an 83-pound weight is used, another to a market that uses a 110-pound weight, and the third to a market using a 135-pound weight. Each farmer sells as many full measures as possible, and when the three return home, the first had 32 pounds of rice left, the second 70 pounds, and the third 30 pounds. Find the total amount of rice they took to the market.

-----

Hint:
Use the Chinese Remainder Theorem.

Remark:
From the description of the problem, one sets up the following system of congruences:

\begin{aligned}x &\equiv 32 \pmod{83}\\ x & \equiv 70\pmod{110}\\ x & \equiv 30 \pmod{135}\end{aligned}\qquad\qquad(1)

However, 83, 110, and 135 are not pairwise co-prime since $(110,135)\neq 1$, so one can't apply the CRT...yet. However, we can rewrite (1) as the following system of congruences:

\begin{aligned}x & \equiv 32 \pmod{83}\\ x & \equiv 70 \pmod{2} \\ x & \equiv 70 \pmod{5}\\ x & \equiv 70 \pmod{11}\\ x & \equiv 30 \pmod{27} \\ x & \equiv 30 \pmod{5}\end{aligned}\qquad\qquad (2)

The idea now is to remove the redundancies in the system (2). In the end, one should end up with a system of congruences (see spoiler if you want) in which one satisfies the pairwise co-prime condition in order to use the Chinese Remainder Theorem.

\begin{aligned}x & \equiv 32 \pmod{83}\\ x & \equiv 0 \pmod{10}\\ x & \equiv 4 \pmod{11}\\ x & \equiv 3 \pmod{27}\end{aligned}\qquad\qquad (3)

Remember to read the POTW submission guidelines to find out how to submit your answers!

Last edited:

#### Chris L T521

##### Well-known member
Staff member
Again, sorry for posting these late!

This week's question was correctly answered by Sudharaka. You can find his solution below.

Chinese Remainder Theorem:

Let $$m_1,m_2,\cdots,m_r$$ be pairwise relatively prime positive integers. Then the system of congruences $$x\equiv a_1\mbox{ (mod }m_{1}),\,x\equiv a_2\mbox{ (mod }m_{2}),\cdots,\,x\equiv a_r\mbox{ (mod }m_{r})$$ has a unique solution modulo $$M=m_{1}m_{2}\cdots m_{r}$$.

(Reference: Elementary Number Theory and its Applications by K.H. Rosen)

For the given system, $$a_{1}=32,\,a_{2}=0,\,a_{3}=4,\,a_{4}=3,\,m_{1}=83,\,m_{2}=10,\,m_{3}=11,\,m_{4}=27$$. Then,

$M=m_{1}m_{2}m_{3}m_{4}=246510$

$M_{1}=m_{2}m_{3}m_{4}=2970$

$M_{2}=m_{1}m_{3}m_{4}=24651$

$M_{3}=m_{1}m_{2}m_{4}=22410$

$M_{4}=m_{1}m_{2}m_{3}=9130$

Now we have to find $$b_{1},\,b_{2},\,b_{3}\mbox{ and }b_{4}$$ of the following congruences.

$2970\,b_{1}\equiv 1\mbox{ (mod 83)}\Rightarrow b_{1}\equiv 23\mbox{ (mod 83)}$

$24651\,b_{2}\equiv 1\mbox{ (mod 10)}\Rightarrow b_{2}\equiv 1\mbox{ (mod 10)}$

$22410\,b_{3}\equiv 1\mbox{ (mod 11)}\Rightarrow b_{3}\equiv 4\mbox{ (mod 11)}$

$9130\,b_{4}\equiv 1\mbox{ (mod 27)}\Rightarrow b_{4}\equiv 7\mbox{ (mod 27)}$

Therefore the solution of the system can be written as,

$U\equiv a_{1}M_{1}b_{1}+a_{2}M_{2}b_{2}+a_{3}M_{3}b_{3}+a_{4}M_{4}b_{4}\mbox{ (mod M)}$

$U\equiv 2736210\mbox{ (mod 246510)}$

$\Rightarrow U\equiv 24600\mbox{ (mod 246510)}$

Therefore the total amount of rice $$(T)$$ should be,

$T\equiv 3\times 24600\mbox{ (mod }3\times 246510)$

$\Rightarrow T\equiv 73800\mbox{ (mod 739530)}$

Status
Not open for further replies.