# Miller-Rabin Primality Testing failure and a subgroup

Let $n$ be composite. I'm trying to figure out if the set $H$ of $a$ such that 1) $a$ is relatively prime to $n$ and 2) the Miller-Rabin test fails to show compositeness of $n$ with $a$ is a subgroup of the multiplicative group mod $n$.

My instinct is no: I am trying to show that the set is not closed. But then again we won't get any factors of $n$ by multiplication because of condition 1).

Update: I've run some experiments and it seems that the number of strong liars relatively prime to n divides the order of the multiplicative group. I wanted to get a contradiction with Lagrange's theorem.

-
Have you tried just working out examples with a few small n? – Qiaochu Yuan Dec 3 '10 at 14:45
I checked out 9 as it seemed like the smallest non-trivial example and it did wind up being a subgroup. 1, 2, 4, 5, 7 and 8 are all 'strong liars'. But this is a bad example. – Abelsh Dec 3 '10 at 17:16
closure under multiplication will suffice (since this is a finite group); the only possible problem is if $n-1 = 2^rd$, $d$ odd, $a^d\not\equiv 1$, $b^d\not\equiv 1$, and for the same $s$, $0\lt s\lt r$, $a^{2^sd}\equiv b^{2^sd}\equiv -1$. – Arturo Magidin Dec 3 '10 at 19:06

The strong liars form a subgroup of $(\mathbb{Z}/n\mathbb{Z})^{\times}$ iff $n$ isn't of the form $n=\prod_{j=1}^{k}{p_{j}}^{\alpha_{j}}$, where $k\geq2$, $p_{1},\ldots,p_{j}$ are pairwise different primes such that $p_{j}\equiv 1\pmod4$ and $\alpha_{j}\in\mathbb{N}$, $j\in\{1,\ldots,k\}$. Here's the proof:

For $n=1$ everything's trivial so let's assume $n>1$ and set $n-1=2^{x}y$, where $x,y\in\mathbb{Z}$ and $2\nmid y$. Also let $L(n)$ denote the set of strong liars $\bmod n$, ie $$L(n)=\big\{a\in(\mathbb{Z}/n\mathbb{Z})^{\times}\colon(\exists t\in\mathbb{Z},0\leq t<x:a^{2^{t}y}=-1)\vee a^y=1\big\}.$$

If $2\mid n$, then $$L(n)=\big\{a\in(\mathbb{Z}/n\mathbb{Z})^{\times}\colon a^{n-1}=1\big\},$$ which is obviously a subgroup of $(\mathbb{Z}/n\mathbb{Z})^{\times}$.

If $q\mid n$ for some prime $q$ such that $q\equiv3\pmod4$, then $-1$ is quadratic nonresidue $\bmod{q}$, hence also $\bmod{n}$, so it can't be $a^{2^{t}y}=-1$ for $t>0$ and $$L(n)=\big\{a\in(\mathbb{Z}/n\mathbb{Z})^{\times}\colon a^y=\pm1\big\},$$ which is again a subgroup of $(\mathbb{Z}/n\mathbb{Z})^{\times}$.

If $n=p^\alpha$, where $p$ is a prime such that $p\equiv1\bmod4$ and $\alpha\in\mathbb{N}$ then we have $a^{n-1}-1=(a^{y}-1)\prod_{j=0}^{x-1}(a^{2^{j}y}+1)$, and since at most one of the factors on the RHS of this equation can be $0\bmod p$, we have $$L(n)=\big\{a\in(\mathbb{Z}/n\mathbb{Z})^{\times}\colon a^{n-1}=1\big\},$$ which is once again a subgroup of $(\mathbb{Z}/n\mathbb{Z})^{\times}$.

Now let $n=\prod_{j=1}^{k}{p_{j}}^{\alpha_{j}}$, where $k\geq2$, $p_{1},\ldots,p_{j}$ are pairwise different primes such that $p_{j}\equiv 1\pmod4$ and $\alpha_{j}\in\mathbb{N}$, $j\in\{1,\ldots,k\}$. Let $G_{j}=(\mathbb{Z}/{p_{j}}^{\alpha_{j}}\mathbb{Z})^{\times}$, $H_{j}={G_{j}}^y$ be the subgroup of $y$-th powers in $G_{j}$ and $K_{j}=\{a\in G_{j}\colon a^{y}=1\}$ be the $y$-torsion subgroup of $G_{j}$. Then $|G_{j}|=\varphi({p_{j}}^{\alpha_{j}})=(p_{j}-1){p_{j}}^{\alpha_{j}-1}$, $|K_{j}|=\gcd(\varphi({p_{j}}^{\alpha_{j}}),y)$ (because $G_{j}$ is cyclic) and $H_{j}\cong G_{j}/K_{j}$, from which it follows that $4\mid|H_{j}|$. $H_{j}$ is cyclic (it's a subgroup of $G_{j})$, so it contains an unique cyclic subgroup of order $4$. For every $j\in\{1,\ldots,k\}$ let's fix $r_{j}\in G_{j}$ such that ${r_{j}}^{y}$ has order $4$ (such elements exist by the above reasoning). By CRT we have $(\mathbb{Z}/n\mathbb{Z})^{\times}\cong\prod_{j=1}^{k}G_{j}$, let $f_{j}\colon(\mathbb{Z}/n\mathbb{Z})^{\times}\to G_{j}$ be the natural projection. Then there exist $a,b\in(\mathbb{Z}/n\mathbb{Z})^{\times}$ such that $f_{1}(a)=r_1$, $f_{1}(b)=-r_1$ and $f_{j}(a)=f_{j}(b)=r_j$ for $j\geq2$. Then for every $j$ it's $f_{j}(a^{2y})=f_{j}(b^{2y})=-1$, hence $a^{2y}=b^{2y}=-1$ and $a,b\in L(n)$ (because $x\geq2$). But $(ab)^{2y}=1$ so it can't be $(ab)^{2^{t}y}=-1$ for $t\geq1$, and also $f_{1}((ab)^{y})=-{r_{1}}^{2y}=1$, $f_{2}((ab)^{y})={r_{2}}^{2y}=-1$, so it's $(ab)^{y}\neq\pm1$, hence $ab\notin L(n)$, which means that $L(n)$ isn't a subgroup of $(\mathbb{Z}/n\mathbb{Z})^{\times}$ in this case.

Concerning the previous post: If $q\mid n$ for some prime $q$ such that $q\equiv 2\text{ or }3\pmod4$ then it's easy to see that there are no primitive Pythagorean triangles with hypotenuse $n$, and if $n=\prod_{j=1}^{k}{p_{j}}^{\alpha_{j}}$, where $p_{1},\ldots,p_{j}$ are pairwise different primes such that $p_{j}\equiv 1\pmod4$ and $\alpha_{j}\in\mathbb{N}$, then it's not difficult to show that there are $2^{k-1}$ different (up to isomorphism) primitive Pythagorean triangles with hypotenuse $n$, so the "bad" $n$'s are really exactly the ones for which there's more than one such triangle. :)

-
For what it's worth, this result is stated as Exercise 3.17 in Crandall and Pomerance's book on primes. – KCd Jul 20 '15 at 9:33
@KCd Thanks, that gives (together with the previous Exercise 3.16) a little bit different perspective. Btw that book looks really interesting :). – Jarek Kuben Jul 21 '15 at 20:02

For $n=221$ (this is the example in Wikipedia), the liars are 21, 47, 174 and 200. Now, 21*47 mod 221 gives 103, which is not in that list.

The sequence of those composite $n$ for which the liars don't form a group seems to be 65, 85, 145, 185, 205, 221, 265, 305, 325, 365, 377, ... which seems to coincide with "A024409 Hypotenuses of more than one primitive Pythagorean triangle" on OEIS (testet up to 629).

Edit: Of course, I included 1 and -1 before checking for being a group.

-
@Arturo: In addition, we need $a b\ne 1$. Id tried this explicitely: For $n=221$, we have $d=55,r=2$ and $s=1$ for all four liars, and $21\cdot47\ne1$. For $n=49,d=3,r=4$, the liars are (18,19,30,31) where $a^d=1$ for 18,30 and $s=1$ for 19,31. But $19\cdot31=1$, so the group property is not violated. – Ralf Muschall Jan 13 '11 at 21:30
Pinging does not work unless I had participated in this particular answer; but thanks for the note and heads up. – Arturo Magidin Jan 14 '11 at 5:37