OCR MEI Further Pure with Technology 2024 June — Question 2

Exam BoardOCR MEI
ModuleFurther Pure with Technology (Further Pure with Technology)
Year2024
SessionJune
TopicNumber Theory
2 Wilson's theorem states that a positive integer \(n > 1\) is prime if and only if \(( n - 1 ) ! \equiv n - 1 ( \bmod n )\).
    1. Calculate 136! (mod 137).
    2. Hence, determine if the integer 137 is prime.
    1. Create a program that uses Wilson's theorem to find all prime numbers less than or equal to \(n\).
      Write down your program in the Printed Answer Booklet.
    2. Using part (b)(i), write down all prime numbers \(x\), where \(260 \leqslant x \leqslant 300\).
    1. Explain why there is exactly one prime number congruent to \(2 ( \bmod 4 )\).
    2. Explain why no prime number is congruent to \(0 ( \bmod 4 )\).
    3. Using part (b)(ii), write down the three prime numbers \(y\), where \(260 \leqslant y \leqslant 300\), that are congruent to \(3 ( \bmod 4 )\). Label the three prime numbers in part (c)(iii) \(c _ { 1 } , c _ { 2 }\) and \(c _ { 3 }\). Define the integer \(N\) by \(N = 4 c _ { 1 } c _ { 2 } c _ { 3 } + 3\).
    4. Explain why \(N\) is not divisible by \(c _ { 1 } , c _ { 2 }\) or \(c _ { 3 }\).
    5. Write down the value of \(N ( \bmod 4 )\).
  4. The fundamental theorem of arithmetic states that every positive integer can be written uniquely as the product of powers of prime numbers. Suppose there are finitely many prime numbers congruent to \(3 ( \bmod 4 )\). Label these prime numbers \(p _ { 1 } , \ldots , \mathrm { p } _ { \mathrm { n } }\), where \(p _ { 1 } = 3\). Using the \(n - 1\) integers \(p _ { 2 } , \ldots , \mathrm { p } _ { \mathrm { n } }\), define the integer \(M\) by
    \(\mathrm { M } = 4 \mathrm { p } _ { 2 } \mathrm { p } _ { 3 } \ldots \mathrm { p } _ { \mathrm { n } } + 3\).
    1. Write down the value of \(M ( \bmod 4 )\).
    2. Explain why \(\mathrm { M } = \mathrm { q } _ { 1 } \mathrm { q } _ { 2 } \ldots \mathrm { q } _ { \mathrm { r } }\), where the integers \(q _ { 1 } , \ldots , \mathrm { q } _ { \mathrm { r } }\) are all prime.
    3. Prove that there is at least one integer \(i\), where \(1 \leqslant i \leqslant n\), such that \(q _ { i } \equiv 3 ( \bmod 4 )\).
    4. Hence, deduce that there are infinitely many prime numbers congruent to \(3 ( \bmod 4 )\).
This paper (3 questions)
View full paper
Q1 Q2 Q3