A2 June 2022 Q4

EdexcelCurrent spec7 marksNumber Theory

(a) Use the Euclidean algorithm to show that 124 and 17 are relatively prime (coprime). (2)

(b) Hence solve the equation\[124x + 17y = 10\] (3)

Mark scheme (a)

Scheme	Marks	AO
\(124 = 17 \times 7 + 5\) \(17 = 3 \times 5 + 2\) \(5 = 2 \times 2 + 1\) \(\{2 = 2 \times 1\}\)	M1	2.1
Since the gcd is 1, 124 and 17 are relatively prime (coprime)	A1	2.4
	(2)

Notes

M1: Complete attempt at the Euclidean algorithm to find the gcd (hcf) of 124 and 17, condone a numerical slip.

A1: A fully correct application of the Euclidean algorithm and draws the conclusion that since the gcd/hcf = 1 therefore 124 and 17 are relatively prime (coprime).

Mark scheme (b)

Scheme	Marks	AO
\(1 = 5 - 2 \times 2\) \(1 = 5 - 2(17 - 3 \times 5) \Rightarrow 1 = 7 \times 5 - 2 \times 17\) \(1 = 7(124 - 17 \times 7) - 2 \times 17\) \(\Rightarrow 1 = 7 \times 124 - 51 \times 17\)	M1 A1	2.1 1.1b
\(\Rightarrow 10 = 70 \times 124 - 510 \times 17\) \(x = 70,\ y = -510\)	A1	2.2a
	(3)

Notes

M1: Attempts to find the Bezout’s identity, condone sign slips

A1: Correct Bezout’s identity.

A1: Deduces a set of correct values of \(x\) and \(y\).

Alternatively

M1: Uses the solution to (a) to find an identity of the form \(a \times 124 + b \times 17 = c\)

A1: Correct identity

A1: Deduces a set of correct values of \(x\) and \(y\).

Alternative

Scheme	Marks	AO
For example \(124 = 17 \times 7 + 5\) \(5 = 124 - 7 \times 17\)	M1 A1	2.1 1.1b
\(\Rightarrow 10 = 2 \times 124 - 14 \times 17\) \(x = 2,\ y = -14\)	A1	2.2a

Alternative

Scheme	Marks	AO
\(1 = 5 - 2 \times 2\) \(1 = 5 - 2(17 - 3 \times 5) \Rightarrow 4 = 2 \times 17 - 6 \times 5\) \(4 = 2 \times 17 - 6(124 - 17 \times 7)\) \(\Rightarrow 4 = 44 \times 17 - 6 \times 124\)	M1 A1	2.1 1.1b
\(\Rightarrow 10 = 110 \times 17 - 15 \times 124\) \(x = -15,\ y = 110\)	A1	2.2a

Mark scheme (c)

Scheme	Marks	AO
A complete method using modulo arithmetic to achieve \(x \equiv \ldots \bmod 17\) For example \(7 \times 124x \equiv 7 \times 6 \bmod 17 \Rightarrow x \equiv \ldots \bmod 17\)	M1	2.1
\(x \equiv 8 \bmod 17\) o.e.	A1	1.1b
	(2)
	(7 marks)

Notes

M1: A complete method to reach using modulo arithmetic to achieve \(x \equiv \ldots \bmod 17\)

For example

Multiplies through by their multiplicative inverse of 124 and reaches \(x \equiv \ldots \bmod 17\). Bezout’s identity used in part (b) follow through on their multiple of 124

A1: \(x \equiv 8 \bmod 17\) o.e.