Use the Euclidean algorithm to express gcd (123, 2347) in the form 123p + 2347q, where \(p,{\text{ }}q \in \mathbb{Z}\).

Find the least positive solution of \(123x \equiv 1(\bmod 2347)\) .

Find the general solution of \(123z \equiv 5(\bmod 2347)\) .

State the solution set of \(123y \equiv 1(\bmod 2346)\) .

\(2347 = 19 \times 123 + 10\)     M1A1

\((123 = 12 \times 10 + 3)\)

\(10 = 3 \times 3 + 1\)     A1

\(1(\gcd ) = 10 - 3 \times 3 = 10 - 3 \times (123 - 12 \times 10)\)     M1A1

\( = 37 \times 10 - 3 \times 123\)     A1

\( = 37 \times (2347 - 19 \times 123) - 3 \times 123\) (for continuation)     M1

\( = 37 \times 2347 - 706 \times 123\)     A1

[8 marks]

EITHER

\(1(\bmod 2347) = ( - 706 \times 123)(\bmod 2347)\)     M1A1

OR

\(x = - 706 + 2347n\)     M1A1

solution: 1641     A1

[3 marks]

\(5(\bmod 2347) = ( - 3530 \times 123)(\bmod 2347)\)     (M1)

\({\text{GS}}:z = - 3530 + k2347\)     A1A1 

Note: Other common possibilities include \(1164 + k2347\) and \(8205 + k2347\) .

[3 marks]

empty set (123 and 2346 both divisible by 3)     A1

[1 mark]

The majority of candidates were successful in parts (a) and (b). In part (c), some candidates failed to understand the distinction between a particular solution and a general solution. Part (d) was a 1 mark question that defeated all but the few who noticed that the gcd of the numbers concerned was 3.

The majority of candidates were successful in parts (a) and (b). In part (c), some candidates failed to understand the distinction between a particular solution and a general solution. Part (d) was a 1 mark question that defeated all but the few who noticed that the gcd of the numbers concerned was 3.

The majority of candidates were successful in parts (a) and (b). In part (c), some candidates failed to understand the distinction between a particular solution and a general solution. Part (d) was a 1 mark question that defeated all but the few who noticed that the gcd of the numbers concerned was 3.

The majority of candidates were successful in parts (a) and (b). In part (c), some candidates failed to understand the distinction between a particular solution and a general solution. Part (d) was a 1 mark question that defeated all but the few who noticed that the gcd of the numbers concerned was 3.