\section{Primes, twice primes, three times primes, and prime powers}\label{b7:sec} In this section $n\ge 109$, and $K$, $M$, $\Bad(n)$ are those of Definition~\ref{b3:def}. This section gives the moduli $n$ for which Corollary~\ref{b6:criteria} holds without a table. \begin{remark}[The index of $M$]\label{b7:index} By Remark~\ref{b3:sym}, $|M|\ge|K|=\varphi(n)-\Bad(n)$. The set $M$ is a subgroup of $\units{n}$, so $|M|$ divides $\varphi(n)$. The integer $\iota=\varphi(n)/|M|$ is the \emph{index} of $M$. The next three lemmas use that $\iota$ is an integer. \end{remark} \begin{lemma}[Primes]\label{b7:P} Let $p\ge 3999$ be a prime and $n=p$. Then $|M|\ge 486$. So $\Fl(G,\Z_p\times A')$ is connected for every finite abelian group $A'$ and every finite bridgeless multigraph $G$. \end{lemma} \begin{proof} Here $\varphi(n)=p-1\ge 3998$. By Lemma~\ref{b3:bad}~(b), $\Bad(n)\le 3598$; so $|M|\ge|K|\ge\varphi(n)-3598\ge 400$. Suppose that $|M|\le 485$. Then $\iota\ge 3998/485>8$, because $8\cdot 485=3880$; so $\iota\ge 9$. And \[ \iota\ \le\ \frac{\varphi(n)}{\varphi(n)-3598}\ <\ 10, \] because $9\,\varphi(n)\ge 9\cdot 3998=35982>35980$. So $\iota=9$. Then $\varphi(n)/9=|M|\ge\varphi(n)-3598$ gives $8\,\varphi(n)\le 9\cdot 3598=32382$, so $\varphi(n)\le 4047$. The number $\varphi(n)=p-1$ is even, and $9$ divides it; so $18$ divides it. The multiples of $18$ from $3998$ to $4047$ are $4014=18\cdot 223$ and $4032=18\cdot 224$. So $p=4015=5\cdot 803$ or $p=4033=37\cdot 109$. Neither is a prime, a contradiction. So $|M|\ge 486$, and Corollary~\ref{b6:criteria}~(i) gives the second sentence. \end{proof} \begin{lemma}[Twice a prime]\label{b7:D} Let $p\ge 2000$ be a prime and $n=2p$. Then $|M|\ge 252$. So $\Fl(G,\Z_{2p}\times A')$ is connected for every finite abelian group $A'$ and every finite bridgeless multigraph $G$. \end{lemma} \begin{proof} Here $\varphi(n)=p-1\ge 1999$. By Lemma~\ref{b3:bad}~(c), $\Bad(n)\le 1798$; so $|M|\ge|K|\ge\varphi(n)-1798\ge 201$. Suppose that $|M|\le 251$. Then $\iota\ge 1999/251>7$, because $7\cdot 251=1757$; so $\iota\ge 8$. And \[ \iota\ \le\ \frac{\varphi(n)}{\varphi(n)-1798}\ <\ 10, \] because $9\,\varphi(n)\ge 9\cdot 1999=17991>17980$. So $\iota$ is $8$ or $9$. \emph{Let $\iota=8$.} Then $\varphi(n)=8\,|M|\le 2008$. The multiples of $8$ from $1999$ to $2008$ are $2000$ and $2008$. So $p=2001=3\cdot 667$ or $p=2009=7^2\cdot 41$. Neither is a prime. \emph{Let $\iota=9$.} Then $\varphi(n)/9=|M|\ge\varphi(n)-1798$ gives $8\,\varphi(n)\le 9\cdot 1798=16182$, so $\varphi(n)\le 2022$. The number $\varphi(n)=p-1$ is even, and $9$ divides it; so $18$ divides it. The only multiple of $18$ from $1999$ to $2022$ is $2016=18\cdot 112$. So $p=2017$, $n=4034$ and $|M|=224$. In $\Z_{4034}$ the class of $55$ is a good unit, by Lemma~\ref{b3:G5}: $55=5\cdot 11$ is coprime to $4034=2\cdot 2017$, and $4034>54\cdot 55+54=3024$. So $55$ is in $K$, a subset of $M$. The order of $55$ divides $|M|=224$. So $55^{224}=1$ in $\Z_{4034}$, and also modulo $2017$. But $55^{224}=294$ modulo $2017$. Here is the computation; every line is an equation of integers, and $224=128+64+32$. \begin{align*} 55^{2}&=3025=1\cdot 2017+1008, & 1757^{2}&=1530\cdot 2017+1039,\\ 1008^{2}&=503\cdot 2017+1513, & 1039^{2}&=535\cdot 2017+426,\\ 1513^{2}&=1134\cdot 2017+1891, & 426^{2}&=89\cdot 2017+1963,\\ 1891^{2}&=1772\cdot 2017+1757, & & \end{align*} So modulo $2017$: $55^{2}=1008$, $55^{4}=1513$, $55^{8}=1891$, $55^{16}=1757$, $55^{32}=1039$, $55^{64}=426$ and $55^{128}=1963$. And \[ 1963\cdot 426=414\cdot 2017+1200,\qquad 1200\cdot 1039=618\cdot 2017+294 . \] So $55^{192}=1200$ and $55^{224}=294\ne 1$ modulo $2017$. This is a contradiction. So $|M|\ge 252$, and Corollary~\ref{b6:criteria}~(ii) gives the second sentence. \end{proof} \begin{lemma}[Three times a prime]\label{b7:T} Let $p\ge 1333$ be a prime and $n=3p$. Then $|M|\ge 324$. So $\Fl(G,\Z_{3p}\times A')$ is connected for every finite abelian group $A'$ and every finite bridgeless multigraph $G$. \end{lemma} \begin{proof} Here $\varphi(n)=2\,(p-1)\ge 2664$. By Lemma~\ref{b3:bad}~(d), $\Bad(n)\le 2400$; so $|M|\ge|K|\ge\varphi(n)-2400\ge 264$. Suppose that $|M|\le 323$. Then $\iota\ge 2664/323>8$, because $8\cdot 323=2584$; so $\iota\ge 9$. And \[ \iota\ \le\ \frac{\varphi(n)}{\varphi(n)-2400}\ <\ 11, \] because $10\,\varphi(n)\ge 26640>26400$. So $\iota$ is $9$ or $10$. \emph{Let $\iota=10$.} Then $\varphi(n)/10=|M|\ge\varphi(n)-2400$ gives $9\,\varphi(n)\le 24000$, so $\varphi(n)\le 2666$. No multiple of $10$ is in the interval from $2664$ to $2666$. \emph{Let $\iota=9$.} Then $\varphi(n)/9\ge\varphi(n)-2400$ gives $8\,\varphi(n)\le 21600$, so $\varphi(n)\le 2700$. The number $9$ divides $\varphi(n)$. The prime $p$ is odd, so $p-1$ is even and $4$ divides $\varphi(n)=2\,(p-1)$. So $36$ divides $\varphi(n)$. The multiples of $36$ from $2664$ to $2700$ are $2664=36\cdot 74$ and $2700=36\cdot 75$. So $p=1333=31\cdot 43$ or $p=1351=7\cdot 193$. Neither is a prime. This is a contradiction. So $|M|\ge 324$, and Corollary~\ref{b6:criteria}~(iii) gives the second sentence. \end{proof} In the three lemmas $K$ is not empty: it has at least $400$, $201$ and $264$ elements. \smallskip Now we come to the prime powers. For a unit $c$ of $\Z_n$, $\ord_n(c)$ is its order in the group $\units{n}$. The subgroup $M$ contains every good unit $c$, and so it contains the cyclic group that $c$ generates: $|M|\ge\ord_n(c)$. \begin{lemma}[Four prime powers]\label{b7:G6} For each of the four rows of Table~\textup{\ref{b7:tab:pp}}, the class of $c$ is a good unit of $\Z_n$, and its order is the number $\ord_n(c)$ of the row. So $|M|\ge 486$ for $n=4096$, $4913$, $6561$, $8192$. \end{lemma} \begin{table}[H] \centering \small \begin{tabular}{@{}r@{\qquad}c@{\qquad}r@{\qquad}r@{\qquad}l@{\qquad}l@{}} \hline $n$ & type & $c$ & $\ord_n(c)$ & prime factorization & $q$: $c^{\ord_n(c)/q}$ modulo $n$\\ \hline $4096$ & Q & $55$ & $512$ & $2^{9}$ & $2{:}\,2049$\\ $4913$ & Q & $55$ & $1156$ & $2^{2}\cdot 17^{2}$ & $2{:}\,4912,\ 17{:}\,290$\\ $6561$ & Q & $56$ & $4374$ & $2\cdot 3^{7}$ & $2{:}\,6560,\ 3{:}\,2188$\\ $8192$ & Q & $55$ & $1024$ & $2^{10}$ & $2{:}\,4097$\\ \hline \end{tabular} \vspace{4pt} \caption{Four prime powers, in the format of the certificate \textup{(}Table~\textup{\ref{bapp:table})}.}\label{b7:tab:pp} \end{table} \begin{proof} \emph{Good units.} The numbers $4096=2^{12}$, $8192=2^{13}$ and $4913=17^{3}$ are coprime to $55=5\cdot 11$, and they are greater than $54\cdot 55+54=3024$. The number $6561=3^{8}$ is coprime to $56=2^{3}\cdot 7$, and it is greater than $54\cdot 56+54=3078$. So Lemma~\ref{b3:G5} applies in the four rows. \emph{The orders.} Let $\omega$ be the number $\ord_n(c)$ of a row. We show that $c^{\omega}=1$ in $\Z_n$ and that $c^{\omega/q}\ne 1$ for every prime divisor $q$ of $\omega$. Then the order of $c$ is $\omega$: the order divides $\omega$, and a proper divisor of $\omega$ divides $\omega/q$ for some prime divisor $q$ of $\omega$. We use this fact. \begin{equation}\label{b7:eq:E}\tag{$\ast\ast$} \parbox{0.86\textwidth}{Let $p$ be a prime and $x=1+p^{a}y$ with integers $a\ge 1$ and $y$; let $a\ge 2$ if $p=2$. Then $x^{p}=1+p^{a+1}y'$ with an integer $y'$ that is equal to $y$ modulo $p$. Hence $x^{p^{i}}=1+p^{a+i}y_i$ with $y_i=y$ modulo $p$, for every $i\ge 0$.} \end{equation} Proof of~\eqref{b7:eq:E}: by the binomial theorem, $x^{p}=1+p^{a+1}y+\sum_{j=2}^{p}\binom{p}{j}p^{aj}y^{j}$. Every term of the sum is divisible by $p^{a+2}$. For $2\le j