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]