OCR Further Additional Pure 2022 June — Question 4 9 marks

Exam BoardOCR
ModuleFurther Additional Pure (Further Additional Pure)
Year2022
SessionJune
Marks9
PaperDownload PDF ↗
Mark schemeDownload PDF ↗
TopicNumber Theory
TypeDivisibility tests and proofs
DifficultyChallenging +1.2 This is a structured Further Maths question on divisibility and modular arithmetic. Part (a) involves standard divisibility tests and justifying a novel algorithm (requiring understanding of modular arithmetic), while part (b) requires modular arithmetic calculations and finding order. The concepts are A-level appropriate but the justification and order calculation require more mathematical maturity than typical pure maths questions, placing it moderately above average difficulty.
Spec8.02b Divisibility tests: standard tests for 2, 3, 4, 5, 8, 9, 118.02c Divisibility by primes: algorithmic tests for primes less than 508.02e Finite (modular) arithmetic: integers modulo n8.02l Fermat's little theorem: both forms

4 Let \(N\) be the number 15824578 .
    1. Use a standard divisibility test to show that \(N\) is a multiple of 11 .
    2. A student uses the following test for divisibility by 7 . \begin{displayquote} 'Throw away' multiples of 7 that appear either individually or within a pair of consecutive digits of the test number.
      Stop when the number obtained is \(0,1,2,3,4,5\) or 6 .
      The test number is only divisible by 7 if that obtained number is 0 . \end{displayquote} For example, for the number \(N\), they first 'throw away' the " 7 " in the tens column, leaving the number \(N _ { 1 } = 15824508\). At the second stage, they 'throw away' the " 14 " from the left-hand pair of digits of \(N _ { 1 }\), leaving \(N _ { 2 } = 01824508\); and so on, until a number is obtained which is \(0,1,2,3,4,5\) or 6 .
      • Justify the validity of this process.
      • Continue the student's test to show that \(7 \mid N\).
        (iii) Given that \(N = 11 \times 1438598\), explain why 7| 1438598 .
      • Let \(\mathrm { M } = \mathrm { N } ^ { 2 }\).
        1. Express \(N\) in the unique form 101a + b for positive integers \(a\) and \(b\), with \(0 \leqslant b < 101\).
        2. Hence write \(M\) in the form \(\mathrm { M } \equiv \mathrm { r } ( \bmod 101 )\), where \(0 < r < 101\).
        3. Deduce the order of \(N\) modulo 101.

Question 4:
AnswerMarks Guidance
4a i
Since result is a multiple of 11, so is NM1
A1
AnswerMarks
[2]1.1
2.4Shown (or via 1 – 5 + 8 – 2 + 4 – 5 + 7 – 8 = 0)
Explanation (not just “since answer = 0”)
AnswerMarks Guidance
iiIf 7 N and 7
N = 15 824 578
N = 15 824 508
1
N = 01 824 508 given to here
2
N = 01 124 501 (e.g. from here)
3
N = 01 103 0 11
4
N = 00 400 204
5
N = 00 050 064
6
N = 00 001 001 (may note here that 1001 = 71113)
7
N = 00 000 301
8
N = 00 000 021
9
N = 00 000 000
AnswerMarks
10B1
B1
AnswerMarks
[2]2.3
1.1or equivalent including in words only, e.g. “a sum of
multiples of 7 is a multiple of 7”
Convincingly showing that the process ultimately
yields a zero. Leading zeros not required, no specific
notation required.
Condone stopping at 𝑁 < 500, provided 𝑁 ≡ 0 (mod
𝑟 𝑟
7) shown
A minimalist approach might go from
N = 18 24 50 8 to (say)
2
N = 04 03 01 1 etc. (i.e. several steps at once)
3
AnswerMarks Guidance
iiiSince 7 111 438 598 and hcf(7, 11) = 1 then
71 438 598 B1
[1]1.2 i.e. by Euclid’s lemma
bi N
= 1 5 6 6 7 8 11 00 01
1 0 1
AnswerMarks
a = 156 678 and b = 100M1
A1
AnswerMarks Guidance
[2]1.1
1.1Division attempt (may be implied by correct answers)
iiM = N2  (−1)2  1 (mod 101) B1
[1]1.1 Must use their result in (b)(i)
iiiThe order of N mod 101 is 2 B1
[1]2.2a
Question 4:
4 | a | i | “odds – evens” = (1 + 8 + 4 + 7) – (5 + 2 + 5 + 8) = 0
Since result is a multiple of 11, so is N | M1
A1
[2] | 1.1
2.4 | Shown (or via 1 – 5 + 8 – 2 + 4 – 5 + 7 – 8 = 0)
Explanation (not just “since answer = 0”)
ii | If 7 | N and 7 | 70 (e.g.) then 7 | N – 70 etc.
N = 15 824 578
N = 15 824 508
1
N = 01 824 508 given to here
2
N = 01 124 501 (e.g. from here)
3
N = 01 103 0 11
4
N = 00 400 204
5
N = 00 050 064
6
N = 00 001 001 (may note here that 1001 = 71113)
7
N = 00 000 301
8
N = 00 000 021
9
N = 00 000 000
10 | B1
B1
[2] | 2.3
1.1 | or equivalent including in words only, e.g. “a sum of
multiples of 7 is a multiple of 7”
Convincingly showing that the process ultimately
yields a zero. Leading zeros not required, no specific
notation required.
Condone stopping at 𝑁 < 500, provided 𝑁 ≡ 0 (mod
𝑟 𝑟
7) shown
A minimalist approach might go from
N = 18 24 50 8 to (say)
2
N = 04 03 01 1 etc. (i.e. several steps at once)
3
iii | Since 7 | 111 438 598 and hcf(7, 11) = 1 then
7 | 1 438 598 | B1
[1] | 1.2 | i.e. by Euclid’s lemma
b | i | N
= 1 5 6 6 7 8 11 00 01
1 0 1
a = 156 678 and b = 100 | M1
A1
[2] | 1.1
1.1 | Division attempt (may be implied by correct answers)
ii | M = N2  (−1)2  1 (mod 101) | B1
[1] | 1.1 | Must use their result in (b)(i)
iii | The order of N mod 101 is 2 | B1
[1] | 2.2a
4 Let $N$ be the number 15824578 .
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item Use a standard divisibility test to show that $N$ is a multiple of 11 .
\item A student uses the following test for divisibility by 7 .

\begin{displayquote}
'Throw away' multiples of 7 that appear either individually or within a pair of consecutive digits of the test number.\\
Stop when the number obtained is $0,1,2,3,4,5$ or 6 .\\
The test number is only divisible by 7 if that obtained number is 0 .
\end{displayquote}

For example, for the number $N$, they first 'throw away' the " 7 " in the tens column, leaving the number $N _ { 1 } = 15824508$. At the second stage, they 'throw away' the " 14 " from the left-hand pair of digits of $N _ { 1 }$, leaving $N _ { 2 } = 01824508$; and so on, until a number is obtained which is $0,1,2,3,4,5$ or 6 .

\begin{itemize}
\end{enumerate}\item Justify the validity of this process.
  \item Continue the student's test to show that $7 \mid N$.\\
(iii) Given that $N = 11 \times 1438598$, explain why 7| 1438598 .
\item Let $\mathrm { M } = \mathrm { N } ^ { 2 }$.
\begin{enumerate}[label=(\roman*)]
\item Express $N$ in the unique form 101a + b for positive integers $a$ and $b$, with $0 \leqslant b < 101$.
\item Hence write $M$ in the form $\mathrm { M } \equiv \mathrm { r } ( \bmod 101 )$, where $0 < r < 101$.
\item Deduce the order of $N$ modulo 101.
\end{itemize}
\end{enumerate}\end{enumerate}

\hfill \mbox{\textit{OCR Further Additional Pure 2022 Q4 [9]}}