Return to Answer

Let me expand my earlier comment to a partial answer of "why sparsity?". It is impossible for $|{\rm PSL}(2,p^{m})|$ to have four or fewer different prime factors when $p$ is an odd prime which is neither Fermat nor Mersenne and $m > 1$ is an integer. In fact, if $m >1$ is not a power of $2$, we will see that whenever $p >3$ is prime, then $|{\rm PSL}(2,p^{m})|$ has at least $5$ different prime divisors.

(These two facts "explain" why the non-squarefree $q$ appearing in the OPs computer output are all either powers of $2$ or powers of Fermat or Mersenne primes, and why we only have $q$ of the form $p^{2n+1}$ ( for positive $n$) appearing for $p = 2$ or $p =3).$

If $m$ is itself even, then $p^{2m}-1$ is divisible by $p^{4}-1$. It is easy to check that $\frac{p-1}{2}, \frac{p+1}{2}$ and $\frac{p^{2}+1}{2}$ are pairwise coprime. Also $\frac{p^{2}+1}{2}$ is odd, while one of $\frac{p \pm 1}{2}$ is even, and the other is odd. Hence if the odd prime $p$ is neither a Fermat prime nor a Mersenne prime, then $p^{4}-1$ is even, and has at least three different odd prime factors, so has $4$ or more different prime factors (none of which is $p$). Thus $|{\rm PSL}(2,p^{2n})|$ has $5$ or more different prime factors whenever $p$ is an odd prime which is neither Fermat nor Mersenne, and $n$ is any positive integer.

If $m$ is not a power of $2$, then $m$ is divisible by some odd prime $r$. We note below that that $p^{2r}-1$ has four or more prime factors whenever $r$ is an odd prime and $p$ is a prime greater than $3$.

For of the four integers $\frac{p-1}{2}, \frac{p+1}{2}, \frac{p^{r}-1}{p-1}$ and $\frac{p^{r}+1}{p+1},$ exactly one is even. Since $p >3$, the product $\frac{p+1}{2}\frac{p-1}{2}$ has at least two prime factors, since $p-1$ and $p+1$ can't both be powers of $2$ for any prime $p$ greater than $3$.

Note that both of $\frac{p^{r} \pm 1}{p \pm 1}$ are odd, and that they are coprime to each other because ${\rm gcd}(p^{r}-1,p^{r}+1)$ divides $2$.

If $s$ is a prime which divides both $p-1$ and $\frac{p^{r}-1}{p-1}$, then we see easily that $\frac{p^{r}-1}{p-1}$ is congruent to $r$ mod $s$, so we must have $r = s.$ In that case, we have ${\rm gcd}(p-1, \frac{p^{r}-1}{p-1}) = r$, for if $p-1$ is divisible by $r^{2}$, we obtain $\frac{p^{r}-1}{p-1} \equiv r$ (mod $r^{2}).$

Since $\frac{p^{r}-1}{p-1}$ is certainly greater than $r$, we see that $\frac{p^{r}-1}{p-1}$ always has a (necessarily odd) prime factor $s$ which does not divide $p-1.$

Notice that $s$ does not divide $p^{r}+1$ either, for otherwise $s$ divides ${\rm gcd}(p^{r}-1,p^{r}+1) = 2,$ a contradiction.

Likewise, we find that $\frac{p^{r}+1}{p+1}$ has a (necessarily odd) prime factor $t$ which does not divide $p^{2}-1.$ We have to be a little more careful in noting that $1-p + p^{2} - \ldots - p^{r-2} + p^{r-1}$ is 1+ (a sum of $\frac{r-1}{2}$ pairs, each pair with sum at least $p^{2}-p \geq 4$), so that $\frac{p^{r}+1}{p+1} \neq r$.

In conclusion, we see that the odd prime $p$ is neither a Fermat nor a Mersenne prime, then $|{\rm PSL}(2,p^{2n})|$ has at least 5 prime divisors for each integer $n >0$, while if $p$ is any prime greater than $3$, then $|{\rm PSL}(2,p^{m})|$ has at least $5$ prime divisors whenever $m > 1$ is an odd integer.

Let me expand my earlier comment to a partial answer of "why sparsity?". It is impossible for $|{\rm PSL}(2,p^{m})|$ to have four or fewer different prime factors when $p$ is an odd prime which is neither Fermat nor Mersenne and $m > 1$ is an integer. In fact, if $m >1$ is not a power of $2$, we will see that whenever $p >3$ is prime, then $|{\rm PSL}(2,p^{m})|$ has at least $5$ different prime divisors.

(These two facts "explain" why the non-squarefree $q$ appearing in your Python output are all either powers of $2$ or powers of Fermat or Mersenne primes, and why we only have $q$ of the form $p^{2n+1}$ ( for positive $n$) appearing for $p = 2$ or $p =3).$

If $m$ is itself even, then $p^{2m}-1$ is divisible by $p^{4}-1$. It is easy to check that $\frac{p-1}{2}, \frac{p+1}{2}$ and $\frac{p^{2}+1}{2}$ are pairwise coprime. Also $\frac{p^{2}+1}{2}$ is odd, while one of $\frac{p \pm 1}{2}$ is even, and the other is odd. Hence if the odd prime $p$ is neither a Fermat prime nor a Mersenne prime, then $p^{4}-1$ is even, and has at least three different odd prime factors, so has $4$ or more different prime factors (none of which is $p$). Thus $|{\rm PSL}(2,p^{2n})|$ has $5$ or more different prime factors whenever $p$ is an odd prime which is neither Fermat nor Mersenne, and $n$ is any positive integer.

If $m$ is not a power of $2$, then $m$ is divisible by some odd prime $r$. We note below that that $p^{2r}-1$ has four or more prime factors whenever $r$ is an odd prime and $p$ is a prime greater than $3$.

For of the four integers $\frac{p-1}{2}, \frac{p+1}{2}, \frac{p^{r}-1}{p-1}$ and $\frac{p^{r}+1}{p+1},$ exactly one is even. Since $p >3$, the product $\frac{p+1}{2}\frac{p-1}{2}$ has at least two different prime factors, since $p-1$ and $p+1$ can't both be powers of $2$ for any prime $p$ greater than $3$.

Note also that Zsygmondy's Lemma tells us that there are primes $s$ and $t$ such that $p+s\mathbb{Z}$ has multiplicative order $r$ in the units of $(\mathbb{Z}/s\mathbb{Z})^{\times}$ and $p+t\mathbb{Z}$ has multiplicative order $2r$ in the units of $(\mathbb{Z}/t\mathbb{Z})^{\times}$. Then $s$ and $t$ are different (and both odd) and neither of them divides $p^{2}-1.$ Hence $p^{2r}-1$ has at least $4$ different prime divisors, and $|{\rm PSL}(2,p^{m})|$ has at least five prime divisors.

Let me expand my earlier comment to a partial answer of "why sparsity?". It is impossible for $|{\rm PSL}(2,p^{m})|$ to have four or fewer different prime factors when $p$ is an odd prime which is neither Fermat nor Mersenne and $m > 1$ is an integer. In fact, if $m$ is not a power of $2$, we will see that whenever $p >3$ is prime, then $|{\rm PSL}(2,p^{m})|$ has at least $5$ different prime divisors.

(These two facts "explain" why the non-squarefree $q$ appearing in the OPs computer output are all either powers of $2$ or powers of Fermat or Mersenne primes, and why we only have $q$ of the form $p^{2n+1}$ ( for positive $n$) appearing for $p = 2$ or $p =3).$

If $m$ is itself even, then $p^{2m}-1$ is divisible by $p^{4}-1$. It is easy to check that $\frac{p-1}{2}, \frac{p+1}{2}$ and $\frac{p^{2}+1}{2}$ are pairwise coprime. Also $\frac{p^{2}+1}{2}$ is odd, while one of $\frac{p \pm 1}{2}$ is even, and the other is odd. Hence if the odd prime $p$ is neither a Fermat prime nor a Mersenne prime, then $p^{4}-1$ is even, and has at least three different odd prime factors, so has $4$ or more different prime factors (none of which is $p$). Thus $|{\rm PSL}(2,p^{2n})|$ has $5$ or more different prime factors whenever $p$ is an odd prime which is neither Fermat nor Mersenne, and $n$ is any positive integer.

If $m$ is not a power of $2$, then $m$ is divisible by some odd prime $r$. We note below that that $p^{2r}-1$ has four or more prime factors whenever $r$ is an odd prime and $p$ is a prime greater than $3$.

For of the four integers $\frac{p-1}{2}, \frac{p+1}{2}, \frac{p^{r}-1}{p-1}$ and $\frac{p^{r}+1}{p+1},$ exactly one is even. Since $p >3$, the product $\frac{p+1}{2}\frac{p-1}{2}$ has at least two prime factors, since $p-1$ and $p+1$ can't both be powers of $2$ for any prime $p$ greater than $3$.

Note that both of $\frac{p^{r} \pm 1}{p \pm 1}$ are odd, and that they are coprime to each other because ${\rm gcd}(p^{r}-1,p^{r}+1)$ divides $2$.

If $s$ is a prime which divides both $p-1$ and $\frac{p^{r}-1}{p-1}$, then we see easily that $\frac{p^{r}-1}{p-1}$ is congruent to $r$ mod $s$, so we must have $r = s.$ In that case, we have ${\rm gcd}(p-1, \frac{p^{r}-1}{p-1}) = r$, for if $p-1$ is divisible by $r^{2}$, we obtain $\frac{p^{r}-1}{p-1} \equiv r$ (mod $r^{2}).$

Since $\frac{p^{r}-1}{p-1}$ is certainly greater than $r$, we see that $\frac{p^{r}-1}{p-1}$ always has a (necessarily odd) prime factor $s$ which does not divide $p-1.$

Notice that $s$ does not divide $p^{r}+1$ either, for otherwise $s$ divides ${\rm gcd}(p^{r}-1,p^{r}+1) = 2,$ a contradiction.

Likewise, we find that $\frac{p^{r}+1}{p+1}$ has a (necessarily odd) prime factor $t$ which does not divide $p^{2}-1.$ We have to be a little more careful in noting that $1-p + p^{2} - \ldots - p^{r-2} + p^{r-1}$ is 1+ (a sum of $\frac{r-1}{2}$ pairs, each pair with sum at least $p^{2}-p \geq 4$), so that $\frac{p^{r}+1}{p+1} \neq r$.

In conclusion, we see that the odd prime $p$ is neither a Fermat nor a Mersenne prime, then $|{\rm PSL}(2,p^{2n})|$ has at least 5 prime divisors for each integer $n >0$, while if $p$ is any prime greater than $3$, then $|{\rm PSL}(2,p^{m})|$ has at least $5$ prime divisors whenever $m > 1$ is an odd integer.

Let me expand my earlier comment to a partial answer of "why sparsity?". It is impossible for $|{\rm PSL}(2,p^{m})|$ to have four or fewer different prime factors when $p$ is an odd prime which is neither Fermat nor Mersenne and $m > 1$ is an integer. In fact, if $m >1$ is not a power of $2$, we will see that whenever $p >3$ is prime, then $|{\rm PSL}(2,p^{m})|$ has at least $5$ different prime divisors.

(These two facts "explain" why the non-squarefree $q$ appearing in the OPs computer output are all either powers of $2$ or powers of Fermat or Mersenne primes, and why we only have $q$ of the form $p^{2n+1}$ ( for positive $n$) appearing for $p = 2$ or $p =3).$

If $m$ is itself even, then $p^{2m}-1$ is divisible by $p^{4}-1$. It is easy to check that $\frac{p-1}{2}, \frac{p+1}{2}$ and $\frac{p^{2}+1}{2}$ are pairwise coprime. Also $\frac{p^{2}+1}{2}$ is odd, while one of $\frac{p \pm 1}{2}$ is even, and the other is odd. Hence if the odd prime $p$ is neither a Fermat prime nor a Mersenne prime, then $p^{4}-1$ is even, and has at least three different odd prime factors, so has $4$ or more different prime factors (none of which is $p$). Thus $|{\rm PSL}(2,p^{2n})|$ has $5$ or more different prime factors whenever $p$ is an odd prime which is neither Fermat nor Mersenne, and $n$ is any positive integer.

If $m$ is not a power of $2$, then $m$ is divisible by some odd prime $r$. We note below that that $p^{2r}-1$ has four or more prime factors whenever $r$ is an odd prime and $p$ is a prime greater than $3$.

For of the four integers $\frac{p-1}{2}, \frac{p+1}{2}, \frac{p^{r}-1}{p-1}$ and $\frac{p^{r}+1}{p+1},$ exactly one is even. Since $p >3$, the product $\frac{p+1}{2}\frac{p-1}{2}$ has at least two prime factors, since $p-1$ and $p+1$ can't both be powers of $2$ for any prime $p$ greater than $3$.

Note that both of $\frac{p^{r} \pm 1}{p \pm 1}$ are odd, and that they are coprime to each other because ${\rm gcd}(p^{r}-1,p^{r}+1)$ divides $2$.

If $s$ is a prime which divides both $p-1$ and $\frac{p^{r}-1}{p-1}$, then we see easily that $\frac{p^{r}-1}{p-1}$ is congruent to $r$ mod $s$, so we must have $r = s.$ In that case, we have ${\rm gcd}(p-1, \frac{p^{r}-1}{p-1}) = r$, for if $p-1$ is divisible by $r^{2}$, we obtain $\frac{p^{r}-1}{p-1} \equiv r$ (mod $r^{2}).$

Since $\frac{p^{r}-1}{p-1}$ is certainly greater than $r$, we see that $\frac{p^{r}-1}{p-1}$ always has a (necessarily odd) prime factor $s$ which does not divide $p-1.$

Notice that $s$ does not divide $p^{r}+1$ either, for otherwise $s$ divides ${\rm gcd}(p^{r}-1,p^{r}+1) = 2,$ a contradiction.

Likewise, we find that $\frac{p^{r}+1}{p+1}$ has a (necessarily odd) prime factor $t$ which does not divide $p^{2}-1.$ We have to be a little more careful in noting that $1-p + p^{2} - \ldots - p^{r-2} + p^{r-1}$ is 1+ (a sum of $\frac{r-1}{2}$ pairs, each pair with sum at least $p^{2}-p \geq 4$), so that $\frac{p^{r}+1}{p+1} \neq r$.

In conclusion, we see that the odd prime $p$ is neither a Fermat nor a Mersenne prime, then $|{\rm PSL}(2,p^{2n})|$ has at least 5 prime divisors for each integer $n >0$, while if $p$ is any prime greater than $3$, then $|{\rm PSL}(2,p^{m})|$ has at least $5$ prime divisors whenever $m > 1$ is an odd integer.

Let me expand my comment to a partial answer of "why sparsity?". It is impossible for $|{\rm PSL}(2,p^{m})|$ to have four or fewer prime factors when $p$ is an odd prime which is neither Fermat nor Mersenne and $m > 1$ is an integer. In fact, if $m$ is not a power of $2$, we can do somewhat better.

If $m$ is itself even, then $p^{2m}-1$ is divisible by $p^{4}-1$. It is easy to check that $\frac{p-1}{2}, \frac{p+1}{2}$ and $\frac{p^{2}+1}{2}$ are pairwise coprime. Also $\frac{p^{2}+1}{2}$ is odd, while one of $\frac{p \pm 1}{2}$ is even, and the other is odd. Hence if the odd prime $p$ is neither a Fermat prime nor a Mersenne prime, then $p^{4}-1$ is even, and has at least three different odd prime factors, so has $4$ or more different prime factors.

If $m$ is not a power of $2$, we claim that $p^{2r}-1$ has four or more prime factors whenever $r$ is an odd prime and $p >3$ is an odd prime.

For $\frac{p-1}{2}, \frac{p+1}{2}, \frac{p^{r}-1}{p-1}$ and $\frac{p^{r}+1}{p+1}$ are four integers, of which exactly one is even. If $p >3$ is a prime, then the product  $\frac{p+1}{2}\frac{p-1}{2}$ has at least two prime factors, since $p-1$ and $p+1$ can't both be powers of $2$ when $p>3$.

Note that both of $\frac{p^{r} \pm 1}{p \pm 1}$ are odd, and they are coprime to each other because ${\rm gcd}(p^{r}-1,p^{r}+1)$ divides $2$.

If $s$ is a prime which divides both $p-1$ and $\frac{p^{r}-1}{p-1}$, then we see easily that $\frac{p^{r}-1}{p-1}$ is congruent to $r$ mod $s$, so we must have $r = s.$ In that case, we have ${\rm gcd}(p-1, \frac{p^{r}-1}{p-1}) = r$, and since $\frac{p^{r}-1}{p-1}$ is certainly greater than $r$, we see that $\frac{p^{r}-1}{p-1}$ has a (necessarily odd) prime factor $s$ which does not divide $p-1.$

Notice that $s$ does not divide $p^{r}+1$, for otherwise  $s$ must divide $p+1$, and then $\frac{p^{r}-1}{p-1}$ is congruent to $-1$ (mod $s$, a contradiction.

Likewise, we find that $\frac{p^{r}+1}{p+1}$ has a (necessarily odd) prime factor $t$ which does not divide $p^{2}-1.$ We have to be a little more careful in noting that $1-p + p^{2} - \ldots - p^{r-2} + p^{r-1}$ is 1+ (a sum of $\frac{r-1}{2}$ pairs, each at least $p-1 \geq 4$), so that $\frac{p^{r}+1}{p+1} \neq r$.

In conclusion, we see that the odd prime $p$ is neither a Fermat nor a Mersenne prime, then $|{\rm PSL}(2,p^{2m})|$ has at least 5 prime divisors for each integer $m >0$, while if $p$ is any prime greater than $3$, then $|{\rm PSL}(2,p^{m})|$ has at least $5$ prime divisors whenever $m > 1$ is an odd integer.

Let me expand my earlier comment to a partial answer of "why sparsity?". It is impossible for $|{\rm PSL}(2,p^{m})|$ to have four or fewer different prime factors when $p$ is an odd prime which is neither Fermat nor Mersenne and $m > 1$ is an integer. In fact, if $m$ is not a power of $2$, we will see that whenever $p >3$ is prime, then $|{\rm PSL}(2,p^{m})|$ has at least $5$ different prime divisors.

(These two facts "explain" why the non-squarefree $q$ appearing in the OPs computer output are all either powers of $2$ or powers of Fermat or Mersenne primes, and why we only have $q$ of the form $p^{2n+1}$ ( for positive $n$) appearing for $p = 2$ or $p =3).$

If $m$ is itself even, then $p^{2m}-1$ is divisible by $p^{4}-1$. It is easy to check that $\frac{p-1}{2}, \frac{p+1}{2}$ and $\frac{p^{2}+1}{2}$ are pairwise coprime. Also $\frac{p^{2}+1}{2}$ is odd, while one of $\frac{p \pm 1}{2}$ is even, and the other is odd. Hence if the odd prime $p$ is neither a Fermat prime nor a Mersenne prime, then $p^{4}-1$ is even, and has at least three different odd prime factors, so has $4$ or more different prime factors (none of which is $p$). Thus $|{\rm PSL}(2,p^{2n})|$ has $5$ or more different prime factors whenever $p$ is an odd prime which is neither Fermat nor Mersenne, and $n$ is any positive integer.

If $m$ is not a power of $2$, then $m$ is divisible by some odd prime $r$. We note below that that $p^{2r}-1$ has four or more prime factors whenever $r$ is an odd prime and $p$ is a prime greater than $3$.

For of the four integers $\frac{p-1}{2}, \frac{p+1}{2}, \frac{p^{r}-1}{p-1}$ and $\frac{p^{r}+1}{p+1},$ exactly one is even. Since $p >3$, the product  $\frac{p+1}{2}\frac{p-1}{2}$ has at least two prime factors, since $p-1$ and $p+1$ can't both be powers of $2$ for any prime $p$ greater than $3$.

Note that both of $\frac{p^{r} \pm 1}{p \pm 1}$ are odd, and that they are coprime to each other because ${\rm gcd}(p^{r}-1,p^{r}+1)$ divides $2$.

If $s$ is a prime which divides both $p-1$ and $\frac{p^{r}-1}{p-1}$, then we see easily that $\frac{p^{r}-1}{p-1}$ is congruent to $r$ mod $s$, so we must have $r = s.$ In that case, we have ${\rm gcd}(p-1, \frac{p^{r}-1}{p-1}) = r$, for if $p-1$ is divisible by $r^{2}$, we obtain $\frac{p^{r}-1}{p-1} \equiv r$ (mod $r^{2}).$

Since $\frac{p^{r}-1}{p-1}$ is certainly greater than $r$, we see that $\frac{p^{r}-1}{p-1}$ always has a (necessarily odd) prime factor $s$ which does not divide $p-1.$

Notice that $s$ does not divide $p^{r}+1$ either, for otherwise  $s$ divides ${\rm gcd}(p^{r}-1,p^{r}+1) = 2,$ a contradiction.

Likewise, we find that $\frac{p^{r}+1}{p+1}$ has a (necessarily odd) prime factor $t$ which does not divide $p^{2}-1.$ We have to be a little more careful in noting that $1-p + p^{2} - \ldots - p^{r-2} + p^{r-1}$ is 1+ (a sum of $\frac{r-1}{2}$ pairs, each pair with sum at least $p^{2}-p \geq 4$), so that $\frac{p^{r}+1}{p+1} \neq r$.

In conclusion, we see that the odd prime $p$ is neither a Fermat nor a Mersenne prime, then $|{\rm PSL}(2,p^{2n})|$ has at least 5 prime divisors for each integer $n >0$, while if $p$ is any prime greater than $3$, then $|{\rm PSL}(2,p^{m})|$ has at least $5$ prime divisors whenever $m > 1$ is an odd integer.