I have already asked this question here. No answers despite the bounty (which has now ended)

Let $p$ be a prime number, $p > 3$.

Does there always exist $k \in \mathbb N_{\ge 1}$ such that the prime factors of $2^kp - 1$ are all less than $p$?


Well, we can easily see that if $2p - 1$ is not prime, then there are no primes bigger than $p$ which divide it (hence $k=1$ would work). But $2p-1$ being prime is pretty common when $p$ is prime; it happens with $p= 7,19, 37$ etc.

For those last values I looked at $k=2$, and they all work, but there is a prime less than $100$ (I don't remember which one) for which you have to use $k=3$.

Anyhow, it seems like a good bet, but is it actually true?

Note: It seems like an interesting question, but if it's not up to the standards of mathoverflow tell me and I'll remove it :-)

  • 2
    $\begingroup$ Nice question. Consider the expression modulo a small prime q, to find what k works for a given residue class mod q. My guess is there will be a k not much larger than log p (or smaller) which works (because 2^k will be smaller than the product of small primes q which it "hits"). Gerhard "Might Even Be True Unconditionally" Paseman, 2016.02.07. $\endgroup$ – Gerhard Paseman Feb 7 '16 at 17:14
  • 2
    $\begingroup$ How far up have you tested this, Ant? $\endgroup$ – Gerry Myerson Feb 7 '16 at 22:14
  • 1
    $\begingroup$ @GerryMyerson Personally, I haven't. But there is a comment under the linked question (the one I posted on math.stackexchange) by Peter that said that "for $p < 4 \cdot 10^8$, there is a $k \le 9$ doing the job" $\endgroup$ – Ant Feb 7 '16 at 22:28

Suppose we consider a more general problem: given an integer $n \gt 1$, is there an integer $k \gt 0$ so that $2^kn - 1$ is $n$-friable (has all its prime factors of size at most $n$)? I initially suspected the answer was no for small integers and yes for large integers. It turns out (that I have convinced myself that) the answer is yes for $5,7,8,9,11,13$ and no for $2,3,4,6,10,12$. I am looking at $14$, and suggest that this generalization is of interest. (I'll let someone else suggest replacing 2 or 1 or both by integer parameters.)

Gerhard "Is Amazed At Question Growth" Paseman, 2016.02.07.

  • $\begingroup$ nice! Can you sketch an outline on how you convinced yourself that it works for $5,7,8,9,11,13$ and that it does not for $2,3,4,6,10,12$? :-) $\endgroup$ – Ant Feb 8 '16 at 10:24
  • $\begingroup$ Sort of, but I don't call it a proof yet because I haven't written it down. In general, things look like 2^kr= 1 + stu, where r is a prime dividing n and s,t, and u are (possibly trivial) prime powers. s t and u aren't powers of 2 or r, and congruence conditions usually make t and u equal to 1. Now Zsigmondy limits how big s can be, and trial shows no solutions with k large and nonzero. For yes answers, a small amount of computation is enough.. Gerhard "It All Falls Into Place" Paseman, 2016.02.08. $\endgroup$ – Gerhard Paseman Feb 8 '16 at 15:39
  • $\begingroup$ I'm slow today. 2*14 - 1= 27. It seems best to compute for a few small k and then go for a proof of impossibility. Gerhard "And Not Other Way Around" Paseman, 2016.02.08. $\endgroup$ – Gerhard Paseman Feb 8 '16 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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