Feit-Thompson Conjecture/Stronger

From ProofWiki
Jump to navigation Jump to search

Conjecture

There exist no distinct prime numbers $p$ and $q$ such that:

$\dfrac {p^q - 1} {p - 1}$ and $\dfrac {q^p - 1} {q - 1}$ are coprime.


Refutation

Let:

$A = \dfrac {p^q - 1} {p - 1}$
$B = \dfrac {q^p - 1} {q - 1}$

Suppose there exists a prime number $r$ such that:

$r \divides A$ and $r \divides B$

where $\divides$ denotes divisibility.

Aiming for a contradiction, suppose $p = 2$.

Then:

$2^q - 1 \equiv q + 1 \equiv 0 \pmod r$

leading to:

$q \divides r - 1$

and

$r \divides q + 1$

which is impossible.

Hence both $p$ and $q$ are odd primes.


Aiming for a contradiction, suppose:

$r \divides \paren {p - 1}$

By Sum of Geometric Sequence:

$A = 1 + p + p^2 + \cdots + p^{q - 1} \equiv q \pmod r$

and so $r = q$.

But $q \nmid B$.

Hence:

$r \nmid \paren {p - 1}$

Similarly:

$r \nmid \paren {q - 1}$

It follows that:

$p^q \equiv 1 \pmod r$

from which:

$q \divides \paren {r - 1}$

It follows then that:

$(1): \quad r = 2 \lambda p q + 1$

for some $\lambda \in \Z_{>0}$.


It then remains to test the residues of $p^q$ and $q^p$ modulo $r$ for all odd primes $p$ and $q$ for all $r$ of the form given in $1$ in a suitable range.

The counterexample $p = 17$, $q = 3313$ was discovered using the above technique in $1971$, using the ranges $p < 443$, $pq < 200 \, 000$ and $r < 400 \, 000$.

The common divisor was found to be $2 p q + 1 = 112 \, 643$.


It is believed that the exercise has not been reported on since, and that no other counterexamples to the conjecture are known.


Source of Name

This entry was named for Walter Feit and John Griggs Thompson.


Historical Note

The stronger form of the Feit-Thompson Conjecture was refuted by N.M. Stephens in $1971$, by means of a computer search.

Note that David Wells, in his Curious and Interesting Numbers, 2nd ed. of $1997$, misreports this result, stating it about the common divisor of $p^p - 1$ and $q^q - 1$.

This is obviously spurious, as, given odd primes $p$ and $q$, $p^p - 1$ and $q^q - 1$ are both even, and hence have a common divisor of $2$.


Sources