Exercise 3.3.22 (Find the set $\mathscr{G}$ if $m = 21$)

sage: m = 21
sage: inv = [Mod(a,m) for a in range(m) if gcd(a,m) == 1]; inv
[1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20]
sage: [a for a in inv if a^((m-1) // 2)  == Mod(kronecker(a,m),m)]
[1, 20]

Note : For $m=7\cdot 13=91$, the same instructions give a greater subgroup $𝒢$ with order $18$, which is a divisor of $\varphi (m)=72$, as expected. Of course, if $m$ is prime, $𝒢={(\mathbb{Z}∕\mathit{m\mathbb{Z}})}^{\text{×}}$ has order $m-1=\varphi (m)$. Testing all odd composite numbers $m$ up to $2000$, we observe that the order of $𝒢$ is at most $\varphi (m)∕2$, which is expected, since the index of $𝒢$ satisfies ${(\mathbb{Z}∕\mathit{m\mathbb{Z}})}^{\text{×}}:𝒢)\ge 2$ for composite numbers, if we can prove that $𝒢\ne {(\mathbb{Z}∕\mathit{m\mathbb{Z}})}^{\text{×}}$ is always true (see Problem 23). This threshold is reached for $1729$, for which $|𝒢|=\varphi (m)∕2=648$. Every element $a$ in the complement of $𝒢$ give a proof that $m$ is not a prime, since $a^{(p-1)∕2}\ne \left(\frac{a}{p}\right)$. For instance, for $a=11$, $\left(\frac{11}{1729}\right)=-1$, but $11^{(1729-1)∕2}\equiv 1(\mathit{mod}1729)$. So the witness $11$ shows that $1729$ is composite, and the number of such witnesses is at least $\varphi (m)∕2$ (and if $a\wedge m\ne 1,a\wedge m$ is a non trivial divisor of $m$). This is the idea for the Solovay-Strassen test for prime numbers.