Is $7^4-1=2^5 \times 3 \times 5^2$ the only counterexample?

Question

My friend once told me his conjecture:

For every prime $p$ and every integer $n$ which is greater than $2$, $p^n-1$ must have prime factor greater than $p$.

A few minutes later I found a counterexample:

$7^4-1=2^5 \times 3 \times 5^2$

However, is there any other counterexample? Could you help me?

Answer 1

matlab code:

function pt(m, k)
% test all up to  k prime, all powers from 2 to m. 
% fuind factors of p^n - 1, and see whether all are less than p

ps = primes(k);

for p=ps
    disp(p)
    for n = 3:m
        f = factor(p^n - 1);
        b = (f <= p);
        if (all(b))
            'found'
            disp(p)
            disp(n)
            disp(factor(p^n - 1))
        end
    end
end

Results (abbreviated):

> pt(7, 500)
     7     4
    41     4
    43     4
    47     4
    67     3
    73     4
    79     3
    83     4
   137     3
   149     3
   157     4
   163     3
   173     4
   181     3
   191     3
   191     4

Notice that I only tested up to 7th powers. "191" is an interesting failure case, because it fails twice. Also note that this list provides examples with $n = 3$ as well as $n = 4$, so $n = 4$ isn't the only possibility.

Answer 2

Searching for the smallest counterexample for each power gives the following:

$$\begin{gather*} 67^3-1=300762=2\times3\times7^2\times11\times31\\ 7^4-1=2400=2^5\times3\times5^2\\ 7307^5-1=20830300574702353306=2\times11\times13\times151\times191\times281\times911\times1481\times6661\\ 263^6-1=330928743953808=2^4\times3^2\times7^2\times11\times13\times103\times109\times131\times223\\ 493397^7-1=7128392726072389152475777731457041578312=2^2\times23\times29^2\times31\times127\times173\times1163\times2129\times4229\times26041\times50177\times71359\times138349\\ 10181^8-1=115431276825545828982660756380640=2^5\times3\times5\times17\times37\times509\times677\times1657\times1697\times2069\times4657\times5113\times8009\\ 734197^{10}-1=45512014174960703207280356067658088285424423446151729273048=2^3\times3\times11\times17\times19\times41\times59\times61\times71\times131\times139\times191\times761\times2161\times9871\times10301\times12391\times14341\times27901\times181711\times699511\\ \end{gather*}$$