# On a conjecture related to the classification of finite simple groups

I was told that the proof of the Feit-Thompson theorem, which asserts that all non-abelian finite simple groups must have even order, can be greatly simplified if the following seemingly innocent number theoretic conjecture can be proved:

Conjecture: For all primes $p,q$, we have $p^q - 1 \nmid q^p - 1$.

If we suppose that there exists a counterexample, say a pair of primes $p,q$ such that $p^q - 1 | q^p - 1$, then $q^p \equiv 1 \pmod{p^q - 1}$ implies that $p | \phi(p^q - 1)$ (since by looking at the size, one can conclude that $q \not\equiv 1 \pmod{p^q - 1}$). This seems like an implausible situation by itself.

So my question is, does there exist any known examples of a prime $p$ and a positive integer $n$ (not necessarily prime) such that $\phi(p^n - 1)/p$ is an integer?

Edit: It seems that I neglected to consider the $p = 2$ case, where then the condition is trivial since $2^n - 1$ is always odd, so $\phi(2^n - 1)$ is always even. Are counterexamples easy to construct for odd $p$?

-
Yes, for $p=2$ and $n=4$ we have $\phi(2^4-1)/2=4$. –  Dietrich Burde Mar 27 '14 at 12:27
Thank you for your comment, it was indeed a simple oversight. –  Stanley Yao Xiao Mar 27 '14 at 12:31
A partial solution to the Feit-Thopson conjecture is given here. But it refers to $(q^p-1)/q-1)$ does not divide $(p^q-1)/p-1)$ for $p<q$. –  Dietrich Burde Mar 27 '14 at 13:06

Yes, counterexamples are easy to construct. Take $p=3$ and $n=7$. Then $3^7-1=2186=2\cdot 1093$ with the prime $1093$. Hence $\phi(3^7-1)=\phi(1093)=1092=2\cdot 3\cdot 7\cdot 13$ is divisible by $3$. This example shows that $p^n-1$ may have prime factors $q$ with $\phi(q)=q-1$ divisible by $p$.

-
By the way, $p=1093$ is the first Wieferich prime, and $3^{1093}\equiv 3\mod 1093^2+1093+1$. –  Dietrich Burde Mar 27 '14 at 19:35

Fix $p$, and let $q$ be a prime with $q\equiv1\pmod{p}$. There are infinitely many such primes $q$ (by the easy case of Dirichlet's Theorem). As $q$ divides $p^{q-1}-1$, we get that $q-1$ divides $\phi(p^{q-1}-1)$, so $p$ divides $\phi(p^{q-1}-1)$ even more.

-

There are lots of examples; for instance, $n=p$, i.e. $p | \phi(p^p - 1)$ for all values of $p$.

You can decompose $p^n-1$ to the product of the respective cyclotomic polynomials. (Notational remark: capital $\Phi_d$ is the cyclotomic polynomial, small $\phi(d) = \deg \Phi_d$ is Euler's $\phi$ function). $$p^n - 1 = \prod_{0<d|n}{\Phi_d(p)},$$ and we know that if $q|\Phi_d(n)$ is a prime divisor, then either $q|d$ or $q \equiv 1 \mod d$.

If you put in $n=p$, then $$p^p - 1 = (p-1)(p^{p-1}+p^{p-2}+\dots+1) = \Phi_1(p)\cdot \Phi_p(p),$$ and since $\Phi_p(p)>1$ and $p \nmid \Phi_p(p)$, $p^p-1$ must have a prime factor $q \equiv 1 \mod p$.

Then of course $p|\phi(p^p - 1)$, or more generally, $p|\phi(p^n - 1)$ if $p|n$.

(Edit: changed sign convention, $1-p^n$ to $p^n-1$.)

-