8.02g Quadratic residues: calculate and solve equations involving them

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

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

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