AS June 2022 Q4

EdexcelCurrent spec11 marksNumber Theory

In this question you must show all stages of your working.

Solutions relying on calculator technology are not acceptable.

(i)

(a) Use the Euclidean algorithm to find the highest common factor \(h\) of 416 and 72 (3)

(b) Hence determine integers \(a\) and \(b\) such that\[416a + 72b = h\] (3)

(ii) Evaluate \(5^{10} \pmod{13}\) giving your answer as the smallest positive integer solution. (3)

Mark scheme (i)(a)

Scheme	Marks	AO
\(416 = 5 \times 72 + 56\)	M1	1.1b
\(72 = 1 \times 56 + 16;\ 56 = 3 \times 16 + 8;\ 16 = 2 \times 8\,(+0)\)	M1	1.1b
Hence \(h = 8\)	A1	2.2a
	(3)

Notes

M1: Starts the process of using the algorithm, with attempt at \(416 = p \times 72 + q\).

M1: Continues the process until remainder zero is reached.

A1: Deduces the correct highest common factor from correct work.

Mark scheme (i)(b)

Scheme	Marks	AO
Using back substitution \(8 = 56 - 3 \times 16\)	M1	1.1b
\(= 56 - 3(72 - 1 \times 56) = 4 \times 56 - 3 \times 72\) \(= 4 \times (416 - 5 \times 72) - 3 \times 72\)	M1	1.1b
\(= 4 \times 416 - 23 \times 72\) (so \(a = 4\) and \(b = -23\))	A1	1.1b
	(3)

Notes

M1: Begins the process of back substitution by rearranging their equation with least positive remainder.

M1: Completes the process.

A1: Correct expression or values of \(a\) and \(b\) identified.

Mark scheme (i)(c)

Scheme	Marks	AO
\(23 \times 72 = 4 \times 416 - 8 \equiv -8 \pmod{416}\) Or \(23 \times 72 = 1656 \Rightarrow 1656 - k416 = \ldots\)	M1	3.1a
\(c = 416 - 8 = 408\)	A1	1.1b
	(2)

Notes

M1: Uses the answer to (b) and reduces modulo 416 to reach −8 as a congruent number. Or a full process to multiply \(23 \times 72 = 1656\) and reduce by subtracting multiples of 416

A1: For 408.

Mark scheme (ii)

Scheme	Marks	AO
E.g. \(5^{10} \equiv (5^2)^5 \equiv 25^5 \equiv (-1)^5 \pmod{13}\)	M1	1.1b
\(\equiv -1 \pmod{13}\)	dM1	1.1b
\(\equiv 12 \pmod{13}\)	A1	2.2a
	(3)
	(11 marks)

Notes

M1: Uses modulo 13 to reduce the equation in some way to reduce a power of 5, e.g. using \(5^2 = 25 \equiv -1\) or 12. There will be lots of approaches that can be used here (e.g. \(5^3 \equiv 125 \equiv -5 \pmod{13}\) is another possibility.

Note the question instructs calculator solutions are not acceptable so finding \(5^{10}\) itself is not acceptable.

dM1: Completes to a smallest (positive or negative) residue – allow if slips, but look for reducing to a number in \(\{-6, \ldots 6\}\). Again other routes than the one shown are possible. E.g.
\(5^{10} \equiv (5^3)^3 \times 5 \equiv (-5)^3 \times 5 \equiv -125 \times 5 \equiv 5 \times 5 \equiv 25 \equiv 12 \pmod{13}\)

A1: For 12.