MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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$.

share|cite|improve this answer
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.

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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