With reference to the integers 5, 8 and 3, state why the Chinese remainder theorem guarantees a unique solution modulo 120 to this system of linear congruences.

Hence or otherwise, find the general solution to the above system of linear congruences.

5, 8 and 3 are pairwise relatively prime (or equivalent)     R1

120 is the product of 5, 8 and 3     R1

[2 marks]

METHOD 1

\(x = 2 + 5t,{\text{ }}t \in \mathbb{Z}\) and \(2 + 5t \equiv 5(\bmod 8)\)     M1

\(5t \equiv 3(\bmod 8) \Rightarrow 5t \equiv 35(\bmod 8)\)     (M1)

\(t = 7 + 8u,{\text{ }}u \in \mathbb{Z}\)     (A1)

\(x = 2 + 5(7 + 8u) \Rightarrow x = 37 + 40u\)     (A1)

\(37 + 40u \equiv 1(\bmod 3) \Rightarrow u \equiv 0(\bmod 3)\)     (A1)

\(u = 3v,{\text{ }}v \in \mathbb{Z}\)     (A1)

\(x = 37 + 40(3v)\)

\(x = 37 + 120v{\text{ }}\left( {x \equiv 37(\bmod 120)} \right)\)     A1

 

METHOD 2

attempting systematic listing of possibilities     M1

solutions to \(x \equiv 2(\bmod 5)\) are \(x = 2,{\text{ }}7,{\text{ }}12,{\text{ }} \ldots ,{\text{ }}37,{\text{ }} \ldots \)     (A1)

solutions to \(x \equiv 5(\bmod 8)\) are \(x = 5,{\text{ }}13,{\text{ }}21,{\text{ }} \ldots ,{\text{ }}37,{\text{ }} \ldots \)     (A1)

solutions to \(x \equiv 1(\bmod 3)\) are \(x = 1,{\text{ }}4,{\text{ }}7,{\text{ }} \ldots ,{\text{ }}37,{\text{ }} \ldots \)     (A1)

a solution is \(x = 37\)     (A1)

using the Chinese remainder theorem     (M1)

\(x = 37 + 120v{\text{ }}\left( {x \equiv 37(\bmod 120)} \right)\)     A1

 

METHOD 3

attempting to find \({M_i},{\text{ }}i = 1,{\text{ }}2,{\text{ 3}}\)

\({M_1} = 8 \times 3 = 24,{\text{ }}{M_2} = 5 \times 3 = 15\) and \({M_3} = 5 \times 8 = 40\)     M1

using \({M_i}{x_i} \equiv 1(\bmod {m_i}),{\text{ }}i = 1,{\text{ }}2,{\text{ }}3\) to obtain

\(24{x_1} \equiv 1(\bmod 5),{\text{ }}15{x_2} \equiv 1(\bmod 8)\) and \(40{x_3} \equiv 1(\bmod 3)\)     M1

\({x_1} \equiv 4(\bmod 5),{\text{ }}{x_2} \equiv 7(\bmod 8)\) and \({x_3} \equiv 1(\bmod 3)\)     (A1)(A1)(A1)

use of \(x \equiv {a_1}{x_1}{M_1} + {a_2}{x_2}{M_2} + {a_3}{x_3}{M_3}(\bmod M)\) gives

\(x = (2 \times 4 \times 24 + 5 \times 7 \times 15 + 1 \times 1 \times 40)(\bmod 120)\)     (M1)

\(x \equiv 757(\bmod 120){\text{ }}\left( { \equiv 37(\bmod 120)} \right){\text{ }}(x = 37 + 120v,{\text{ }}v \in \mathbb{Z})\)     A1

 

[7 marks]

[N/A]

[N/A]