9
$\begingroup$

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?

$\endgroup$
11
  • $\begingroup$ Quick search came up with $41^4-1=2825760 = 2^5×3×5×7×29^2 $ $\endgroup$
    – lulu
    Commented Jan 19, 2017 at 14:45
  • $\begingroup$ @lulu thank you very much. It is so large that it escapes my notice. Are these counterexamples finite or infinite? Can some of them be constructed in a general way? $\endgroup$
    – apprenant
    Commented Jan 19, 2017 at 14:48
  • 2
    $\begingroup$ To elaborate: $p^4-1=(p^2-1)(p^2+1)=(p-1)(p+1)(p^2+1)$. Since $p-1<p$ and $p+1$ is even you just need $p^2+1$ to break up a bit. That's all I searched for. $\endgroup$
    – lulu
    Commented Jan 19, 2017 at 14:56
  • 2
    $\begingroup$ oeis.org/A073501 (Primes $p$ such that the largest prime factor of $p^2+1$ is less than $p$) $\endgroup$
    – mathlove
    Commented Jan 19, 2017 at 15:00
  • 4
    $\begingroup$ By the way: congrats to your friend for experimenting a bit and making this conjecture, and to you for following up. That's part of how math happens: someone notices a pattern, someone else refines it, someone else doubts it, and so on. And eventually, there's a proof or counterexample... $\endgroup$
    – John Hughes
    Commented Jan 19, 2017 at 16:23

2 Answers 2

Reset to default
5
$\begingroup$

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*}$$

$\endgroup$
6
  • $\begingroup$ The first counterexample for the 7th power is $493397^7-1 = 2^2\times23\times29^2\times31\times127\times173\times1163\times2129\times4229\times26041\times50177\times71359\times138349$ $\endgroup$
    – Michael Stocker
    Commented Jan 19, 2017 at 16:47
  • $\begingroup$ @MichaelStocker Thanks. Added. $\endgroup$
    – Ian Miller
    Commented Jan 20, 2017 at 4:47
  • $\begingroup$ It seems that this sequence hasn't appeared in an entry of the On-Line Encyclopedia of Integer Sequences. $\endgroup$
    – apprenant
    Commented Jan 20, 2017 at 6:15
  • $\begingroup$ We haven't yet proved there is always a term in this sequence. The 9th term is at least $p_{100000}$ as I've checked that far. $\endgroup$
    – Ian Miller
    Commented Jan 20, 2017 at 6:41
  • $\begingroup$ There are other sequences on OEIS that are not proven to be infinite. $\endgroup$
    – Michael Stocker
    Commented Jan 20, 2017 at 8:10
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .