1
$\begingroup$

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$?

$\endgroup$
3
  • $\begingroup$ Yes, for $p=2$ and $n=4$ we have $\phi(2^4-1)/2=4$. $\endgroup$ Mar 27, 2014 at 12:27
  • $\begingroup$ Thank you for your comment, it was indeed a simple oversight. $\endgroup$ Mar 27, 2014 at 12:31
  • 3
    $\begingroup$ 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$. $\endgroup$ Mar 27, 2014 at 13:06

3 Answers 3

3
$\begingroup$

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$.

$\endgroup$
1
  • 1
    $\begingroup$ By the way, $p=1093$ is the first Wieferich prime, and $3^{1093}\equiv 3\mod 1093^2+1093+1$. $\endgroup$ Mar 27, 2014 at 19:35
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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$.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.