8.02l Fermat's little theorem: both forms

4 Let \(N\) be the number 15824578 .

1. 1. Use a standard divisibility test to show that \(N\) is a multiple of 11 .
   2. A student uses the following test for divisibility by 7 . \begin{displayquote} 'Throw away' multiples of 7 that appear either individually or within a pair of consecutive digits of the test number.
      Stop when the number obtained is \(0,1,2,3,4,5\) or 6 .
      The test number is only divisible by 7 if that obtained number is 0 . \end{displayquote} For example, for the number \(N\), they first 'throw away' the " 7 " in the tens column, leaving the number \(N _ { 1 } = 15824508\). At the second stage, they 'throw away' the " 14 " from the left-hand pair of digits of \(N _ { 1 }\), leaving \(N _ { 2 } = 01824508\); and so on, until a number is obtained which is \(0,1,2,3,4,5\) or 6 .
      • Justify the validity of this process.
      • Continue the student's test to show that \(7 \mid N\).
        (iii) Given that \(N = 11 \times 1438598\), explain why 7| 1438598 .
      • Let \(\mathrm { M } = \mathrm { N } ^ { 2 }\).
        1. Express \(N\) in the unique form 101a + b for positive integers \(a\) and \(b\), with \(0 \leqslant b < 101\).
        2. Hence write \(M\) in the form \(\mathrm { M } \equiv \mathrm { r } ( \bmod 101 )\), where \(0 < r < 101\).
        3. Deduce the order of \(N\) modulo 101.

5

1. The group \(G\) consists of the set \(S = \{ 1,9,17,25 \}\) under \(\times _ { 32 }\), the operation of multiplication modulo 32.
   1. Complete the Cayley table for \(G\) given in the Printed Answer Booklet.
   2. Up to isomorphisms, there are only two groups of order 4.
      • \(C _ { 4 }\), the cyclic group of order 4
      • \(K _ { 4 }\), the non-cyclic (Klein) group of order 4
      State, with justification, to which of these two groups \(G\) is isomorphic.
   3. 1. List the odd quadratic residues modulo 32.
      2. Given that \(n\) is an odd integer, prove that \(n ^ { 6 } + 3 n ^ { 4 } + 7 n ^ { 2 } \equiv 11 ( \bmod 32 )\).

7 Throughout this question, \(n\) is a positive integer.

1. Explain why \(n ^ { 5 } \equiv n ( \bmod 5 )\).
2. By proving that \(n ^ { 5 } \equiv n ( \bmod 2 )\), show that \(n ^ { 5 } \equiv n ( \bmod 10 )\).
3. 1. Prove that \(n ^ { 5 } - n\) is divisible by 30 for all positive integers \(n\).
   2. Is there an integer \(N\), greater than 30 , such that \(n ^ { 5 } - n\) is divisible by \(N\) for all positive integers \(n\) ? Justify your answer.

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

2 \begin{enumerate}[label=(\alph*)] \item 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\).

1. Find all the integers \(x\), where \(0 \leqslant x < 1000\) which satisfy \(x ^ { 2 } \equiv 481 ( \bmod 1000 )\).
2. Explain why 481 is a quadratic residue modulo 1000.
3. Determine the quadratic residues modulo 11.
4. Determine the quadratic residues modulo 13.
5. Show that, for any integer \(m , m ^ { 2 } \equiv ( n - m ) ^ { 2 } ( \bmod n )\).
6. Prove that if \(p\) is prime, where \(p > 2\), then the number of quadratic residues modulo \(p\) is \(\frac { p - 1 } { 2 }\).

\item 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 )\).

1. Use Fermat's little theorem to show that 91 is not prime.
2. 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

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.

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. 1. Calculate 136! (mod 137).
   2. Hence, determine if the integer 137 is prime.
2. 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\).
3. 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 )\).

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\).

1. (i) Determine all the possible integers \(a\), where \(a > 3\), such that

$$15 \equiv 3 \bmod a$$ (ii) Show that if \(p\) is prime, \(x\) is an integer and \(x ^ { 2 } \equiv 1 \bmod p\) then either $$x \equiv 1 \bmod p \quad \text { or } \quad x \equiv - 1 \bmod p$$ (iii) A company has \(\pounds 13940220\) to share between 11 charities. Without performing any division and showing all your working, decide if it is possible to share this money equally between the 11 charities.

1. Let \(G\) be a group of order \(46 ^ { 46 } + 47 ^ { 47 }\)

Using Fermat's Little Theorem and explaining your reasoning, determine which of the following are possible orders for a subgroup of \(G\)

1. 11
2. 21

1. In this question you must show detailed reasoning.

Use Fermat's Little Theorem to determine the least positive residue of \(21 { } ^ { 80 } ( \bmod 23 )\) (4)

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}

4

1. (a) Find all the quadratic residues modulo 11.
   (b) Prove that the equation \(y ^ { 5 } = x ^ { 2 } + 2017\) has no solution in integers \(x\) and \(y\).
2. In this question you must show detailed reasoning. The numbers \(M\) and \(N\) are given by $$M = 11 ^ { 12 } - 1 \text { and } N = 3 ^ { 2 } \times 5 \times 7 \times 13 \times 61$$ Prove that \(M\) is divisible by \(N\).

3

1. Show that \(10 ^ { 2 } \equiv 6 ( \bmod 47 )\).
2. Determine the integer \(r\), with \(0 < r < 47\), such that \(6 r \equiv 1 ( \bmod 47 )\).
3. Determine the least positive integer \(n\) for which \(10 ^ { n } \equiv 1\) or \(- 1 ( \bmod 47 )\).

6 For positive integers \(n\), let \(f ( n ) = 1 + 2 ^ { n } + 4 ^ { n }\).

1. 1. Given that \(n\) is a multiple of 3 , but not of 9 , use the division algorithm to write down the two possible forms that \(n\) can take.
   2. Show that when \(n\) is a multiple of 3 , but not of 9 , \(f ( n )\) is a multiple of 73 .
2. Determine the value of \(\mathrm { f } ( n )\), modulo 73 , in the case when \(n\) is a multiple of 9 .

Prove that \(n\) is a prime number greater than \(5 \Rightarrow n^4\) has final digit \(1\) [5 marks]