OCR Further Additional Pure Specimen — Question 9 14 marks

Exam BoardOCR
ModuleFurther Additional Pure (Further Additional Pure)
SessionSpecimen
Marks14
PaperDownload PDF ↗
Mark schemeDownload PDF ↗
TopicNumber Theory
TypeFermat's Little Theorem
DifficultyHard +2.3 This is a Further Maths number theory question requiring multiple proofs using modular arithmetic and Fermat's Little Theorem. Part (i) requires understanding divisibility arguments, part (ii) applies FLT with careful case analysis, and part (iii) demands synthesis of these ideas across two primes simultaneously. The multi-layered proof structure and need for mathematical maturity place this well above typical A-level questions.
Spec8.02e Finite (modular) arithmetic: integers modulo n8.02f Single linear congruences: solve ax = b (mod n)8.02k Euclid's lemma: if a|rs and hcf(r,a)=1 then a|s8.02l Fermat's little theorem: both forms8.02m Order of a modulo p: p-1 not necessarily least such n
9
  1. (a) Prove that \(p \equiv \pm 1 ( \bmod 6 )\) for all primes \(p > 3\).
    (b) Hence or otherwise prove that \(p ^ { 2 } - 1 \equiv 0 ( \bmod 24 )\) for all primes \(p > 3\).
  2. Given that \(p\) is an odd prime, determine the residue of \(2 ^ { p ^ { 2 } - 1 }\) modulo \(p\).
  3. Let \(p\) and \(q\) be distinct primes greater than 3 . Prove that \(p ^ { q - 1 } + q ^ { p - 1 } \equiv 1 ( \bmod p q )\). \section*{END OF QUESTION PAPER} www.ocr.org.uk after the live examination series.
    If OCR has unwittingly failed to correctly acknowledge or clear any third-party content in this assessment material, OCR will be happy to correct its mistake at the earliest possible opportunity. For queries or further information please contact the Copyright Team, First Floor, 9 Hills Road, Cambridge CB2 1GE.
    OCR is part of the
Question 9:
AnswerMarks Guidance
9(i) (a)
S
If p(cid:123)0 or 3 (mod 6) then it is a multiple of 3
If p(cid:123)0, 2 or 4 (mod 6) then it is even
AnswerMarks
Hence p(cid:123)(cid:114)1 (mod 6)B1
E1
AnswerMarks
[2]2.1
1.1The case p(cid:123)0 needs only be dealt
with onceMay be in the form
p(cid:32)6k(cid:14)r (r(cid:32)0 to 5)
AnswerMarks Guidance
9(i) (b)
(cid:32)12k(cid:11)3k(cid:114)1(cid:12)
If k is even then 24 12k
If k is odd then 3k(cid:114)1 is even and
AnswerMarks
24 12k(cid:11)3k(cid:114)1(cid:12)M1
A1
E1
AnswerMarks
[3]2.1
1.1
AnswerMarks
2.4Must be in a suitable form to make
following deductions
n
AnswerMarks
All fully explainedOR
M1A1 Calculate all squares mod 24
(M1 if no more than 2 independent
errors)
E1 Explain that those congruent to 1
are (cid:114)1, (cid:114)5, (cid:114)7, (cid:114)11 i.e. all those
(cid:123)(cid:114)1(cid:11)mod6(cid:12), of which the primes
are a subset
AnswerMarks Guidance
9(ii) 2p2(cid:16)1(cid:32)2 (cid:11)p(cid:16)1(cid:12)(cid:11)p(cid:14)1(cid:12)
(cid:11) 2p(cid:16)1(cid:12)p(cid:14)1
(cid:32)
(cid:123)(cid:11)1(cid:12)p(cid:14)1 (cid:11)modp(cid:12)
AnswerMarks
(cid:32)1M1
M1
E1
A1
AnswerMarks
[4]3.1a
3.1a
i
c2.1
AnswerMarks
3.2ae
m
By Fermat’s little theorem, since hcf
(cid:11)2, p(cid:12)(cid:32)1
AnswerMarks Guidance
9(iii) p
pq(cid:16)1(cid:123)1 (mod q)
qp(cid:16)1(cid:123)0 (mod q) S
(cid:159) pq(cid:16)1(cid:14)qp(cid:16)1(cid:123)1 (mod q)
Similarly,
pq(cid:16)1(cid:14)qp(cid:16)1(cid:123)1 (mod p)
Together,
AnswerMarks
pq(cid:16)1(cid:14)qp(cid:16)1(cid:123)1 (mod pq)e
B1
B1
B1
B1
E1
AnswerMarks
[5]1.1
1.1
3.1a
3.1a
AnswerMarks
2.2aBy FLT (first result, either way round)
Second result
AnswerMarks
Since hcf(cid:11)p, q(cid:12)(cid:32)1Must be justified
PMT
Y545 Mark Scheme June 20XX
Assessment Objectives (AO) Grid
n
e
m
i
c
e
p
S
PS = Problem Solving
M = Modelling
13
PMT
Y545 Mark Scheme June 20XX
BLANK PAGE
n
e
m
i
c
e
p
S
14
PMT
Y545 Mark Scheme June 20XX
BLANK PAGE
n
e
m
i
c
e
p
S
15
PMT
Y545 Mark Scheme June 20XX
BLANK PAGE
n
e
m
i
c
e
p
S
16
Question 9:
9 | (i) | (a) | p
S
If p(cid:123)0 or 3 (mod 6) then it is a multiple of 3
If p(cid:123)0, 2 or 4 (mod 6) then it is even
Hence p(cid:123)(cid:114)1 (mod 6) | B1
E1
[2] | 2.1
1.1 | The case p(cid:123)0 needs only be dealt
with once | May be in the form
p(cid:32)6k(cid:14)r (r(cid:32)0 to 5)
9 | (i) | (b) | p2(cid:16)1(cid:32)(cid:11)6k(cid:114)1(cid:12)2 (cid:16)1(cid:32)36k2(cid:114)12k
(cid:32)12k(cid:11)3k(cid:114)1(cid:12)
If k is even then 24 12k
If k is odd then 3k(cid:114)1 is even and
24 12k(cid:11)3k(cid:114)1(cid:12) | M1
A1
E1
[3] | 2.1
1.1
2.4 | Must be in a suitable form to make
following deductions
n
All fully explained | OR
M1A1 Calculate all squares mod 24
(M1 if no more than 2 independent
errors)
E1 Explain that those congruent to 1
are (cid:114)1, (cid:114)5, (cid:114)7, (cid:114)11 i.e. all those
(cid:123)(cid:114)1(cid:11)mod6(cid:12), of which the primes
are a subset
9 | (ii) | 2p2(cid:16)1(cid:32)2 (cid:11)p(cid:16)1(cid:12)(cid:11)p(cid:14)1(cid:12)
(cid:11) 2p(cid:16)1(cid:12)p(cid:14)1
(cid:32)
(cid:123)(cid:11)1(cid:12)p(cid:14)1 (cid:11)modp(cid:12)
(cid:32)1 | M1
M1
E1
A1
[4] | 3.1a
3.1a
i
c2.1
3.2a | e
m
By Fermat’s little theorem, since hcf
(cid:11)2, p(cid:12)(cid:32)1
9 | (iii) | p
pq(cid:16)1(cid:123)1 (mod q)
qp(cid:16)1(cid:123)0 (mod q) S
(cid:159) pq(cid:16)1(cid:14)qp(cid:16)1(cid:123)1 (mod q)
Similarly,
pq(cid:16)1(cid:14)qp(cid:16)1(cid:123)1 (mod p)
Together,
pq(cid:16)1(cid:14)qp(cid:16)1(cid:123)1 (mod pq) | e
B1
B1
B1
B1
E1
[5] | 1.1
1.1
3.1a
3.1a
2.2a | By FLT (first result, either way round)
Second result
Since hcf(cid:11)p, q(cid:12)(cid:32)1 | Must be justified
PMT
Y545 Mark Scheme June 20XX
Assessment Objectives (AO) Grid
n
e
m
i
c
e
p
S
PS = Problem Solving
M = Modelling
13
PMT
Y545 Mark Scheme June 20XX
BLANK PAGE
n
e
m
i
c
e
p
S
14
PMT
Y545 Mark Scheme June 20XX
BLANK PAGE
n
e
m
i
c
e
p
S
15
PMT
Y545 Mark Scheme June 20XX
BLANK PAGE
n
e
m
i
c
e
p
S
16
9
\begin{enumerate}[label=(\roman*)]
\item (a) Prove that $p \equiv \pm 1 ( \bmod 6 )$ for all primes $p > 3$.\\
(b) Hence or otherwise prove that $p ^ { 2 } - 1 \equiv 0 ( \bmod 24 )$ for all primes $p > 3$.
\item Given that $p$ is an odd prime, determine the residue of $2 ^ { p ^ { 2 } - 1 }$ modulo $p$.
\item Let $p$ and $q$ be distinct primes greater than 3 . Prove that $p ^ { q - 1 } + q ^ { p - 1 } \equiv 1 ( \bmod p q )$.

\section*{END OF QUESTION PAPER}
www.ocr.org.uk after the live examination series.\\
If OCR has unwittingly failed to correctly acknowledge or clear any third-party content in this assessment material, OCR will be happy to correct its mistake at the earliest possible opportunity.

For queries or further information please contact the Copyright Team, First Floor, 9 Hills Road, Cambridge CB2 1GE.\\
OCR is part of the 
\end{enumerate}

\hfill \mbox{\textit{OCR Further Additional Pure  Q9 [14]}}
This paper (9 questions)
View full paper
Q1 4 Q2 3 Q3 5 Q4 6 Q5 9 Q6 10 Q7 11 Q8 13 Q9 14