OCR MEI Further Pure with Technology 2023 June — Question 3 10 marks

Exam BoardOCR MEI
ModuleFurther Pure with Technology (Further Pure with Technology)
Year2023
SessionJune
Marks10
PaperDownload PDF ↗
Mark schemeDownload PDF ↗
TopicNumber Theory
TypeProgramming tasks
DifficultyChallenging +1.2 Part (a) is a straightforward application of Wilson's theorem requiring simple modular arithmetic manipulation. Parts (b)(i-ii) involve writing a basic programming loop to test small primes—computationally simple for primes under 1000. Part (b)(iii) requires a short algebraic proof connecting the equation to the definition, but the insight is relatively direct. While this combines number theory with programming, the conceptual demands are modest and the programming task is routine, placing it slightly above average difficulty.
Spec8.02l Fermat's little theorem: both forms
3 Wilson's theorem states that an integer \(p > 1\) is prime if and only if \(( p - 1 ) ! \equiv - 1 ( \bmod p )\).
  1. Use Wilson's theorem to show that \(17 ! \equiv 1 ( \bmod 19 )\).
  2. A prime number \(p\) is called a Wilson prime if \(( p - 1 ) ! \equiv - 1 \left( \bmod p ^ { 2 } \right)\). For example, 5 is a Wilson prime because \(( 5 - 1 ) ! \equiv 24 \equiv - 1 ( \bmod 25 )\). At the time of writing all known Wilson primes are less than 1000.
    1. Create a program to find all the known Wilson primes. Write out your program in full in the Printed Answer Booklet.
    2. Use your program to find and write down all the known Wilson primes.
    3. Prove that if there is an integer solution \(m\) to the equation \(( p - 1 ) ! + 1 = m ^ { 2 }\) where \(p\) is prime, then \(p\) is a Wilson prime.
Question 3:
AnswerMarks Guidance
3(a) By Wilson’s theorem we have that
1 8 !  − 1 ( m o d 1 9 ) since 19 is prime.
18−1 (mod 19) and so 1 8 2  1 ( m o d 1 9 )
Multiplying both sides by 18 to get
18×18×17! ≡ (−1)×(−1)(mod 19).
AnswerMarks
giving the stated result since 182 1 (mod 19)M1
A1
AnswerMarks
[2]1.1a
2.2aCould be implied.
Alternative method
AnswerMarks Guidance
19 is prime.M1 1.1a
By Wilson’s theorem
18! ≡ −1 (mod 19) ≡ 18 (mod 19).
AnswerMarks Guidance
Since 18! = 18×17! and 18 and 19 areA1 2.2a
statement that 19 is prime to justify the conclusion.
coprime 18! ≡ 18 (mod 19) implies 17! ≡
1 (mod 19).
[2]
Coprime requirement can be implied from a
statement that 19 is prime to justify the conclusion.
AnswerMarks Guidance
(b)(i) Appropriate structure program
Loops with suitable range with starting value of
2.
Check required condition on 𝑛 with if
statement.
AnswerMarks
Fully correct programM1
M1
M1
AnswerMarks
A13.3
3.4
2.1
AnswerMarks
2.3Pseudo code accepted, condone lack of syntax, give
reasonable BOD on possible transcription errors.
For example, use of loops, if statement(s) to check
condition(s) and print final output.
Starting value must be such that there are no
additional values produced.
Example programe
def Factorial(n):
if n == 1:
return 1
else:
return(Factorial(n-1)*n)
def IsPrime(n):
prime = True
for i in range(2,n):
if n % i == 0:
prime = False
return prime
def WilsonPrime(n):
if IsPrime(n):
if ((Factorial(n-1))%(n2))==n2-1:
return True
else:
return False
else:
AnswerMarks
return FalseNote that
the prime
check is not
essential
here
(satisfying
the required
equation
implies that
n is prime)
Routines
for
Factorial
and Prime
functions
can be
called.
AnswerMarks
[4]for i in range(2,1001):
if WilsonPrime(i):
print(i)
AnswerMarks Guidance
(ii)5, 13, 563 B1
[1]1.1 Need to see 13, 563 and no other values except 5.
Condone missing 5.
AnswerMarks
(iii)Suppose that m is an integer solution to
the equation (p – 1)! + 1 = m2 where p is
prime.
By Wilson’s theorem (p – 1)! + 1is
a multiple of p.
Therefore, m2 is a multiple of p.
Since m2 is a square each prime occurs in its
prime factorisation an even number of times.
Therefore 𝑚2is a multiple of p2.
This means that (p−1)!−1 (mod p2) and
AnswerMarks
p is a Wilson primeM1
M1
A1
AnswerMarks
[3]1.1a
2.2a
AnswerMarks
3.2aMust include reasoning from the fact that 𝑝 is prime.
Special case. Give SC1 for correct working from
𝑚2 is a multiple of 𝑝2 if insufficient reasoning to
award previous M1.
Question 3:
3 | (a) | By Wilson’s theorem we have that
1 8 !  − 1 ( m o d 1 9 ) since 19 is prime.
18−1 (mod 19) and so 1 8 2  1 ( m o d 1 9 )
Multiplying both sides by 18 to get
18×18×17! ≡ (−1)×(−1)(mod 19).
giving the stated result since 182 1 (mod 19) | M1
A1
[2] | 1.1a
2.2a | Could be implied.
Alternative method
19 is prime. | M1 | 1.1a | 19 is prime can be implied.
By Wilson’s theorem
18! ≡ −1 (mod 19) ≡ 18 (mod 19).
Since 18! = 18×17! and 18 and 19 are | A1 | 2.2a | Coprime requirement can be implied from a
statement that 19 is prime to justify the conclusion.
coprime 18! ≡ 18 (mod 19) implies 17! ≡
1 (mod 19).
[2]
Coprime requirement can be implied from a
statement that 19 is prime to justify the conclusion.
(b) | (i) | Appropriate structure program
Loops with suitable range with starting value of
2.
Check required condition on 𝑛 with if
statement.
Fully correct program | M1
M1
M1
A1 | 3.3
3.4
2.1
2.3 | Pseudo code accepted, condone lack of syntax, give
reasonable BOD on possible transcription errors.
For example, use of loops, if statement(s) to check
condition(s) and print final output.
Starting value must be such that there are no
additional values produced.
Example programe
def Factorial(n):
if n == 1:
return 1
else:
return(Factorial(n-1)*n)
def IsPrime(n):
prime = True
for i in range(2,n):
if n % i == 0:
prime = False
return prime
def WilsonPrime(n):
if IsPrime(n):
if ((Factorial(n-1))%(n**2))==n**2-1:
return True
else:
return False
else:
return False | Note that
the prime
check is not
essential
here
(satisfying
the required
equation
implies that
n is prime)
Routines
for
Factorial
and Prime
functions
can be
called.
[4] | for i in range(2,1001):
if WilsonPrime(i):
print(i)
(ii) | 5, 13, 563 | B1
[1] | 1.1 | Need to see 13, 563 and no other values except 5.
Condone missing 5.
(iii) | Suppose that m is an integer solution to
the equation (p – 1)! + 1 = m2 where p is
prime.
By Wilson’s theorem (p – 1)! + 1is
a multiple of p.
Therefore, m2 is a multiple of p.
Since m2 is a square each prime occurs in its
prime factorisation an even number of times.
Therefore 𝑚2is a multiple of p2.
This means that (p−1)!−1 (mod p2) and
p is a Wilson prime | M1
M1
A1
[3] | 1.1a
2.2a
3.2a | Must include reasoning from the fact that 𝑝 is prime.
Special case. Give SC1 for correct working from
𝑚2 is a multiple of 𝑝2 if insufficient reasoning to
award previous M1.
3 Wilson's theorem states that an integer $p > 1$ is prime if and only if $( p - 1 ) ! \equiv - 1 ( \bmod p )$.
\begin{enumerate}[label=(\alph*)]
\item Use Wilson's theorem to show that $17 ! \equiv 1 ( \bmod 19 )$.
\item A prime number $p$ is called a Wilson prime if $( p - 1 ) ! \equiv - 1 \left( \bmod p ^ { 2 } \right)$. For example, 5 is a Wilson prime because $( 5 - 1 ) ! \equiv 24 \equiv - 1 ( \bmod 25 )$. At the time of writing all known Wilson primes are less than 1000.
\begin{enumerate}[label=(\roman*)]
\item Create a program to find all the known Wilson primes. Write out your program in full in the Printed Answer Booklet.
\item Use your program to find and write down all the known Wilson primes.
\item Prove that if there is an integer solution $m$ to the equation $( p - 1 ) ! + 1 = m ^ { 2 }$ where $p$ is prime, then $p$ is a Wilson prime.
\end{enumerate}\end{enumerate}

\hfill \mbox{\textit{OCR MEI Further Pure with Technology 2023 Q3 [10]}}
This paper (4 questions)
View full paper
Q1 21 Q2 11 Q3 10 Q4 18