8.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

1 A family of curves has polar equation \(r = \cos n \left( \frac { \theta } { n } \right) , 0 \leq \theta < n \pi\), where \(n\) is a positive even integer.

1. (A) Sketch the curve for the cases \(n = 2\) and \(n = 4\).
   (B) State two points which lie on every curve in the family.
   (C) State one other feature common to all the curves.
2. (A) Write down an integral for the length of the curve for the case \(n = 4\).
   (B) Evaluate the integral.
3. (A) Using \(t = \theta\) as the parameter, find a parametric form of the equation of the family of curves.
   (B) Show that \(\frac { \mathrm { d } y } { \mathrm {~d} x } = \frac { \sin t \sin \left( \frac { t } { n } \right) - \cos t \cos \left( \frac { t } { n } \right) } { \sin t \cos \left( \frac { t } { n } \right) + \cos t \sin \left( \frac { t } { n } \right) }\).
4. Hence show that there are \(n + 1\) points where the tangent to the curve is parallel to the \(y\)-axis.
5. By referring to appropriate sketches, show that the result in part (iv) is true in the case \(n = 4\).
6. (A) Create a program to find all the solutions to \(x ^ { 2 } \equiv - 1 ( \bmod p )\) where \(0 \leq x < p\). Write out your program in full in the Printed Answer Booklet.
   (B) Use the program to find the solutions to \(x ^ { 2 } \equiv - 1 ( \bmod p )\) for the primes
   $$\begin{aligned} ( 4 k ) ! & \equiv 1 \times 2 \times 3 \times \ldots \times ( 2 k - 1 ) \times 2 k \times ( 2 k + 1 ) \times ( 2 k + 2 ) \times \ldots \times ( 4 k - 1 ) \times 4 k ( \bmod p ) \\ & \equiv 1 \times 2 \times 3 \times \ldots \times ( 2 k - 1 ) \times 2 k \times ( - 2 k ) \times ( - ( 2 k - 1 ) ) \times \ldots \times ( - 2 ) \times ( - 1 ) ( \bmod p ) \\ & \equiv ( ( 2 k ) ! ) ^ { 2 } ( \bmod p ) \end{aligned}$$ (A) Explain why ( \(2 k + 2\) ) can be written as ( \(- ( 2 k - 1 )\) ) in line ( 2 ).
   (B) Explain how line (3) has been obtained.
   (C) Explain why, if \(p\) is a prime of the form \(p = 4 k + 1\), then \(x ^ { 2 } \equiv - 1 ( \bmod p )\) will have at least one solution.
   (D) Hence find a solution of \(x ^ { 2 } \equiv - 1 ( \bmod 29 )\).
7. (A) Create a program that will find all the positive integers \(n\), where \(n < 1000\), such that \(( n - 1 ) ! \equiv - 1 \left( \bmod n ^ { 2 } \right)\). Write out your program in full.
   (B) State the values of \(n\) obtained.
   (C) A Wilson prime is a prime \(p\) such that \(( p - 1 ) ! \equiv - 1 \left( \bmod p ^ { 2 } \right)\). Write down all the Wilson primes \(p\) where \(p < 1000\).

8 In this question you must show detailed reasoning.

1. Prove that \(2 ( p - 2 ) ^ { p - 2 } \equiv - 1 ( \bmod p )\), where \(p\) is an odd prime.
2. Find two odd prime factors of the number \(N = 2 \times 34 ^ { 34 } - 2 ^ { 15 }\). \section*{END OF QUESTION PAPER} \section*{OCR
   Oxford Cambridge and RSA}