OCR MEI
Further Pure with Technology
2022
June
— Question 2
Exam Board
OCR MEI
Module
Further Pure with Technology (Further Pure with Technology)
Year
2022
Session
June
Topic
Number Theory
2
In this part of the question \(n\) is an integer greater than 1 .
An integer \(q\), where \(0 < q < n\) is said to be a quadratic residue modulo \(n\) if there exists an integer \(x\) such that \(\mathrm { x } ^ { 2 } \equiv \mathrm { q } ( \bmod n )\).
Note that under this definition 0 is not considered to be a quadratic residue modulo \(n\).
Find all the integers \(x\), where \(0 \leqslant x < 1000\) which satisfy \(x ^ { 2 } \equiv 481 ( \bmod 1000 )\).
Explain why 481 is a quadratic residue modulo 1000.
Determine the quadratic residues modulo 11.
Determine the quadratic residues modulo 13.
Show that, for any integer \(m , m ^ { 2 } \equiv ( n - m ) ^ { 2 } ( \bmod n )\).
Prove that if \(p\) is prime, where \(p > 2\), then the number of quadratic residues modulo \(p\) is \(\frac { p - 1 } { 2 }\).
Fermat's little theorem states that if \(p\) is prime and \(a\) is an integer which is co-prime to \(p\), then \(a ^ { p - 1 } \equiv 1 ( \bmod p )\).
Use Fermat's little theorem to show that 91 is not prime.
Create a program to find an integer \(n\) between 500 and 600 which is not prime and such that \(\mathrm { a } ^ { \mathrm { n } - 1 } \equiv 1 ( \bmod n )\) for all integers \(a\) which are co-prime to \(n\).
In the Printed Answer Booklet