Exercise 3.3.23* (Solovay-Strassen test)

Question

Show that if $m$ is an odd composite number then the set $\mathscr{G}$ defined in Problem 21 is a proper subset of the collection of reduced residue classes $\pmod m$.

\bigskip
Hint. Show that if $a \in \mathscr{G}$, then $a^{m-1} \equiv 1 \pmod m$, and recall Problem 26 in Section 2.8.

Richard Ganaye · Accepted Answer

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

ewcommand{\R}{\mathbb{R}}

ewcommand{\C}{\mathbb{C}}

ewcommand{\F}{\mathbb{F}}

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

\begin{proof} 
Assume, for the sake of contradiction, that $\mathscr{G} = (\Z/m\Z)^	imes$, where $(\Z/m\Z)^	imes$ is the group of reduced residue classes modulo $m$, and as in Problem 21,
$$\mathscr{G} = \left\{ a \in (\Z/m\Z)^	imes  \mid a^{(m-1)/2} = \legendre{a}{m}  ight\}.$$

Consider any class $\alpha = [a]_m \in (\Z/m\Z)^	imes$. If $\alpha \in \mathscr{G}$, then by definition, $\alpha^{(m-1)/2} = \legendre{\alpha}{p}$ which gives by squaring $\alpha^{m-1} = \legendre{\alpha}{p}^2 = 1 \pmod p$. So, for every integer $a$ such that $p 
mid a$,
$$a^{m-1} \equiv 1 \pmod p.$$
Since $m$ is composite, this shows that $m$ is a Carmichael number. By Problem 2.8.26, $m$ is square-free, so $m = p_1p_2\ldots p_l$, where $p_1,p_2,\ldots,p_l$ are distinct odd primes. Note that $l \geq 2$, otherwise $m$ would be a prime number.

Let $c$ be a quadratic nonresidue modulo $p_1$ (such a $c$ exists, because there are $(p_1 - 1)/2$ nonresidues in $[\![1, p_1-1]\!]$). By the Chinese remainder Theorem, there is some integer $b$ such that
\begin{align*}
b &\equiv c \pmod {p_1},\
b &\equiv 1 \pmod {p_2},\
&\vdots\
b&\equiv 1 \pmod {p_l}.
\end{align*}

Then 
$$\legendre{b}{p_1} = -1,\qquad \legendre{b}{p_2} = \cdots = \legendre{b}{p_l} = 1,$$
therefore the Jacobi symbol $\legendre{b}{m}$ is given by
$$\legendre{b}{m} = \prod_{i=1}^l \legendre{b}{p_i} = -1.$$

The definition of $b$ shows that $b \wedge p_i = 1$ for every $i = 1,2,\ldots,l$, thus $b \wedge m = 1$, so $[b]_p \in (\Z/m\Z)^	imes$. Our hypothesis $\mathscr{G} = (\Z/m\Z)^	imes$ shows that $[b]_p \in \mathscr{G}$ so that
$$b^{(m-1)/2} \equiv \legendre{b}{m} = -1 \pmod m.$$
Since $p_2 \mid m$, 
$$b^{(m-1)/2} \equiv -1 \pmod{p_2},$$
but this is impossible, because $b \equiv 1 \pmod {p_2}$, thus $b^{(m-1)/2} \equiv 1 \pmod {p_2}$, so $1 \equiv -1 \pmod{p_2}$, where $p_2$ is odd. This contradiction shows that
$$\mathscr{G} \subsetneq (\Z/m\Z)^	imes.$$
So $\mathscr{G}$ is a proper subgroup of the group of reduced residue classes modulo $m$.

\end{proof}

Note: Since the index of $\mathscr{G}$ satisfies  $((\Z/m\Z)^	imes : \mathscr{G}) \geq 2$, 
$$|\mathscr{G}| \leq |\Z/m\Z)^	imes| / 2= \phi(m) /2.$$
If we draw at random an integer $a$ between $1$ and $m-1$, if $a \wedge m 
e 1$, then $m$ is composite, otherwise there is a probability $p >1/2$ that $\legendre{a}{m} 
e a^{(m-1)/2} \pmod m$. With $k$ independent draws, if one of these draws gives $\legendre{a}{m} 
e a^{(m-1)/2} \pmod m$ (or $a\wedge m 
e 1$), then $m$ is composite, and if all give the result $\legendre{a}{m} = a^{(m-1)/2} \pmod m$, then $m$ is probably prime, with a probability of error less that $(1/2)^k$.

Exercise 3.3.23* (Solovay-Strassen test)

Answers

Comments

Exercise 3.3.23* (Solovay-Strassen test)

Answers

Comments

Add answer