What is the total amount of rice taken to the market by three farmers?

[Chris L T521]

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:

Spoiler

Use the Chinese Remainder Theorem.

Remark:

Spoiler

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.

Spoiler

\[\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)\]

 

[Chris L T521]

Again, sorry for posting these late!

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

Spoiler

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)}\]