Exercises

4..

1. Calculate the following by hand: $\left(\frac{3}{97}\right)$ , $\left(\frac{3}{389}\right)$ , $\left(\frac{22}{11}\right)$ , and $\left(\frac{5!}{7}\right)$ .

2. Let $G$ be an abelian group and let $n$ be a positive integer.
   1. Prove that the map $\varphi :G\to G$ given by $\varphi (x) = x^n$ is a group homomorphism.
   2. Prove that the subset $H$ of $G$ of squares of elements of $G$ is a subgroup.

3. Use Theorem 4.1.7 to show that for $p\geq 5$ prime,
   $$\left(\frac{3}{p}\right) = \begin{cases}\hfill 1 & \text{ if }p\equiv 1, 11\pmod{12},\\ -1 & \text{ if }p\equiv 5, 7\pmod{12}. \end{cases}$$

4. (*) Use that $(\mathbb{Z}/p\mathbb{Z}{})^*$ is cyclic to give a direct proof that $\left(\frac{-3}{p}\right)=1$ when $p\equiv 1\pmod{3}$ . (Hint: There is an $c\in (\mathbb{Z}/p\mathbb{Z}{})^*$ of order $3$ . Show that $(2c+1)^2=-3$ .)

5. (*) If $p\equiv 1\pmod{5}$ , show directly that $\left(\frac{5}{p}\right)=1$ by the method of Exercise 4.4. (Hint: Let $c\in (\mathbb{Z}/p\mathbb{Z}{})^*$ be an element of order $5$ . Show that $(c+c^4)^2+(c+c^4)-1=0$ , etc.)

6. (*) Let $p$ be an odd prime. In this exercise you will prove that $\left(\frac{2}{p}\right)=1$ if and only if $p\equiv \pm 1\pmod{8}$ .
   1. Prove that
      $$x = \frac{1-t^2}{1+t^2}, \qquad y = \frac{2t}{1+t^2}$$
      is a parameterization of the set of solutions to $x^2+y^2\equiv 1\pmod{p}$ , in the sense that the solutions $(x,y)\in\mathbb{Z}/p\mathbb{Z}{}$ are in bijection with the $t\in \mathbb{Z}/p\mathbb{Z}{} \cup \{\infty\}$ such that $1+t^2\not\equiv 0\pmod{p}$ . Here $t=\infty$ corresponds to the point $(-1,0)$ . (Hint: if $(x_1,y_1)$ is a solution, consider the line $y=t(x+1)$ through $(x_1,y_1)$ and $(-1,0)$ , and solve for $x_1, y_1$ in terms of $t$ .)
   2. Prove that the number of solutions to $x^2+y^2\equiv 1\pmod{p}$ is $p+1$ if $p\equiv 3 \pmod{4}$ and $p-1$ if $p\equiv 1\pmod{4}$ .
   3. Consider the set $S$ of pairs $(a,b)\in (\mathbb{Z}/p\mathbb{Z}{})^*\times (\mathbb{Z}/p\mathbb{Z}{})^*$ such that $a+b=1$ and $\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)=1$ . Prove that $\char93 S=(p+1-4)/4$ if $p\equiv 3 \pmod{4}$ and $\char93 S = (p-1-4)/4$ if $p\equiv 1\pmod{4}$ . Conclude that $\char93 S$ is odd if and only if $p\equiv \pm 1\pmod{8}$
   4. The map $\sigma(a,b)=(b,a)$ that swaps coordinates is a bijection of the set $S$ . It has exactly one fixed point if and only if there is an $a\in\mathbb{Z}/p\mathbb{Z}{}$ such that $2a=1$ and $\left(\frac{a}{p}\right)=1$ . Also, prove that $2a=1$ has a solution $a\in\mathbb{Z}/p\mathbb{Z}{}$ with $\left(\frac{a}{p}\right)=1$ if and only if $\left(\frac{2}{p}\right)=1$ .
   5. Finish by showing that $\sigma$ has exactly one fixed point if and only if $\char93 S$ is odd, i.e., if and only if $p\equiv \pm 1\pmod{8}$ .
   Remark: The method of proof of this exercise can be generalized to give a proof of the full quadratic reciprocity law.

7. How many natural numbers $x < 2^{13}$ satisfy the equation
   $$x^2\equiv 5\pmod{2^{13}-1}?$$
   You may assume that $2^{13}-1$ is prime.

8. Find the natural number $x<97$ such that $x\equiv 4^{48}\pmod{97}$ . Note that $97$ is prime.

9. In this problem we will formulate an analogue of quadratic reciprocity for a symbol like $\left(\frac{a}{q}\right)$ , but without the restriction that $q$ be a prime. Suppose $n$ is a positive integer, which we factor as $\prod_{i=1}^k p_i^{e_i}$ . We define the Jacobi symbol $\left(\frac{a}{n}\right)$ as follows:
   $$\left(\frac{a}{n}\right) = \prod_{i=1}^k \left(\frac{a}{p_i}\right)^{e_i}.$$
   1. Give an example to show that $\left(\frac{a}{n}\right)=1$ need not imply that $a$ is a perfect square modulo $n$ .
   2. (*) Let $n$ be odd and $a$ and $b$ be integers. Prove that the following holds:
      1. $\left(\frac{a}{n}\right)\left(\frac{b}{n}\right) = \left(\frac{ab}{n}\right)$ . (Thus $a\mapsto \left(\frac{a}{n}\right)$ induces a homomorphism from $(\mathbb{Z}/n\mathbb{Z}{})^*$ to $\{\pm 1\}$ .)
      2. $\left(\frac{-1}{n}\right) \equiv n \pmod{4}$ .
      3. $\left(\frac{2}{n}\right)=1$ if $n\equiv \pm 1\pmod{8}$ and $-1$ otherwise.
      4. $\left(\frac{a}{n}\right) = (-1)^{\frac{a-1}{2} \cdot \frac{n-1}{2}} \left(\frac{n}{a}\right)$

10. (*) Prove that for any $n\in\mathbb{Z}$ the integer $n^2+n+1$ does not have any divisors of the form $6k-1$ .