# How big are the prime factors of $2^kp - 1$?

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

## Thoughts

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 :-)

• 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. – Gerhard Paseman Feb 7 '16 at 17:14
• How far up have you tested this, Ant? – Gerry Myerson Feb 7 '16 at 22:14
• @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" – 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.)
• 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$? :-) – Ant Feb 8 '16 at 10:24