Let $\alpha$ be a primitive root for the prime $p$. This means that the numbers $1\text{,}\alpha \text{,}{\alpha }^2\text{,}{\alpha }^3\text{,}\dots \text{,}{\alpha }^{p-2}(\text{mod}p)$ yield all of the nonzero congruence classes mod $p$.

1. Let $i$ be fixed and suppose $x^2\equiv {\alpha }^i(\text{mod}p)$ has a solution $x$. Show that $i$ must be even. (Hint: Write $x\equiv {\alpha }^j$ for some $j$. Now use the fact that ${\alpha }^k\equiv {\alpha }^l(\text{mod}p)$ if and only if $k\equiv l(\text{mod}p-1)$.) This shows that the nonzero squares mod $p$ are exactly $1\text{,}{\alpha }^2\text{,}{\alpha }^4\text{,}{\alpha }^6\text{,}\dots (\mathrm{m}\mathrm{o}\mathrm{d}p)$, and therefore $\alpha \text{,}{\alpha }^3\text{,}{\alpha }^5\text{,}\dots$ are the quadratic nonresidues mod $p$.

2. Using the definition of primitive root, show that ${\alpha }^{(p-1)/2}\cancel{\equiv }1(\text{mod}p)$.

3. Use Exercise 15 in Chapter 3 to show that ${\alpha }^{(p-1)/2}\equiv -1(\text{mod}p)$.

4. Let $x\cancel{\equiv }0(\text{mod}p)$. Show that $x^{(p-1)/2}\equiv 1(\text{mod}p)$ if $x$ is a quadratic residue and $x^{(p-1)/2}\equiv -1(\text{mod}p)$ if $x$ is a quadratic nonresidue mod $p$.

In the coin flipping protocol with $n=pq$, suppose Bob sends a number $y$ such that neither $y$ nor $-y$ has a square root mod $n$.

1. Show that $y$ cannot be a square both mod $p$ and mod $q$. Similarly, $-y$ cannot be a square mod both primes.

2. Suppose $y$ is not a square mod $q$. Show that $-y$ is a square mod $q$.

3. Show that $y$ is a square mod one of the primes and $-y$ is a square mod the other.

4. Benevolent Alice decides to correct Bob’s “mistake.” Suppose $y$ is a square mod $p$ and $-y$ is a square mod $q$. Alice calculates a number $b$ such that $b^2\equiv y(\text{mod}p)$ and $b^2\equiv -y(\text{mod}q)$ and sends $b$ to Bob (there are two pairs of choices for $b$). Show how Bob can use this information to factor $n$ and hence claim victory.

1. Let $p$ be an odd prime. Show that if $x\equiv -x(\text{mod}p)$, then $x\equiv 0(\text{mod}p)$.

2. Let $p$ be an odd prime. Suppose $x\text{,}y\cancel{\equiv }0(\text{mod}p)$ and $x^2\equiv y^2(\text{mod}{p}^2)$. Show that $x\equiv \pm y(\text{mod}{p}^2)$ (Hint: Look at the proof of the Basic Principle in Section 9.3.)

3. Suppose Alice cheats when flipping coins by choosing $p=q$. Show that Bob always loses in the sense that Alice always returns $\pm x$. Therefore, it is wise for Bob to ask for the two primes at the end of the game.