Exercise 3.3.24 ($\mathscr{H}$ is not a group)

Question

Let $m$ be an odd positive integer, and let $\mathscr{H}$ denote the set of reduced residue classes $a \pmod m$ such that $m$ is a strong probable prime base $a$ (i.e., if $m-1 = 2^k d$, $d$ odd, then $a^d \equiv 1 \pmod m$ or $a^{d2^j} \equiv -1$ for some $j$, $0 \leq j < k$). Show that if $m = 65$ then $8 \in \mathscr{H}$ and $18 \in \mathscr{H}$, but that $8 \cdot 18 \equiv 14 
ot \in \mathscr{H}$. (Thus $\mathscr{H}$ is not a group for this $m$.)

Richard Ganaye · Accepted Answer

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

\begin{proof} 
Let $m$ be an odd positive integer, where $m-1 = 2^k d,\ 2 
mid d$.
 
For every integer $a$, let $\alpha = \overline{a} \in \Z/m\Z$ denote the class of $a$ modulo $m$.

$$\mathscr{H} = \left\{\alpha \in (\Z/m\Z)^	imes \mid \alpha^d = 1  	ext{ or } \exists j \in [\![0, k [\![,\ \alpha^{d2^j}= -1 ight\}.$$

If $m = 65$, then $k = 6, d = 1$.

Since $\overline{8}^2 = -1$, $\alpha = \overline{8} \in \mathscr{H}$. Similarly $18^2 = 324 = 5\cdot 65 -1$, thus $\overline{18}^2 = -1$, and $\beta = \overline{18} \in \mathscr{H}$. But $\gamma = \alpha \beta = \overline{14}$, and $14^2 = 196 = 3 \cdot 65 + 1$, so $\gamma 
e 1, \gamma 
e -1, \gamma^2 =1$ (and consequently $\gamma^{2^k} = 1$ for every $k\geq 1$), therefore $\alpha \beta 
ot \in \mathscr{H}$.

$\mathscr{H}$ is not a group.

\end{proof}

Exercise 3.3.24 ($\mathscr{H}$ is not a group)

Answers

Comments

Exercise 3.3.24 ($\mathscr{H}$ is not a group)

Answers

Comments

Add answer