smallest prime factors of $2^k+1$ and $2^m-1$ appear disjoint except for $3$ .

Question

The set of smallest prime factors of numbers of the form $2^k+1$ and the set of smallest prime factors of numbers of the form $2^k-1$ appear to be nearly disjoint, except for $3$ which appears in both sets.

Let $p(x)$ denote the smallest prime factor of the natural number $x$ . $p(0)=0$ and $p(1)$ is undefined.

I've checked that $\{ p(2^k+1) \mathop| k \ge 1 \}$ and $\{ p(2^k-1) \mathop| k \ge 1 \}$ are disjoint-except-for-$3$ for small values of $k$, up to 30.

I've also picked a few non-3 primes that are in $\{ p(2^k-1) \mathop| k \ge 1 \}$, in particular, $7, 23, 31$ and none of them even divide the first $10^6$ values of $\{ 2^k+1 \mathop| k \ge 1 \}$. Therefore, $7,23,31$ aren't among the smallest factors of that subset of numbers of the form $2^k+1$ .

So, I guess my question(s) is (are)

• Are $\{ p(2^k-1) | k \ge 1 \} \setminus \{3\} $ and $\{ p(2^k+1) | k \ge 1 \} \setminus \{3\} $ really disjoint?
• If they are, how do you prove it?
• If they are disjoint, how are non-3 primes divided between the two groups?

---

Appendix 0 -- table of small values of $p(2^n-1)$ and $p(2^n+1)$

n     2**n - 1     p(2**n - 1)       2**n + 1     p(2**n + 1)
2            3              3               5              5
3            7              7               9              3
4           15              3              17             17
5           31             31              33              3
6           63              3              65              5
7          127            127             129              3
8          255              3             257            257
9          511              7             513              3
10        1023              3            1025              5

Appendix I -- check first 29 elements are disjoint except for 3 naively.

def p(n):
    if n == 0:
        return 0
    if n == 1:
        return None
    else:
        for i in range(2, n+1):
            if n % i == 0:
                return i
    assert False

def f(x):
    return 2**x - 1

def g(x):
    return 2**x + 1

F = set(p(f(x)) for x in range(2, 30))
G = set(p(g(x)) for x in range(2, 30))

print(F)
print(G)

Appendix II -- check that 7,23,31 do not divide any of the first $10^6$ elements of the form $2^k+1$. (Therefore they are not the smallest factors a fortiori.)

g :: (Num a, Integral a) => a -> a
g x = 2 ^ x + 1

main = putStrLn $ show [(x, g x) | x <- [ 2.. 100000] , or [g x `mod` 7 == 0, g x `mod` 23 == 0, g x `mod` 31 == 0]]

Answer 1

For any prime $p$ let $k_p$ be the smallest (nonzero) value such that $p | 2^{k_p} -1$. Then the set of values $k$ such that $p|2^k-1$ is just $\{k_p n \ | \ n\in \mathbb{Z}\}$.

Similarly for any prime $p$ let $m_p$ be the smallest value such that $p | 2^{m_p} +1$ if such a value exists. The set of values $m$ such that $p|2^m+1$ is either empty or $\{m_p(2n+1)\ | \ n\in \mathbb{Z}\}$.

Moreover note that if $m_p$ exists then $k_p = 2m_p$.

As a consequence if $p$ is the smallest prime dividing $2^k-1$ for some $k$ then it must also be the smallest prime dividing $2^{k_p}-1$. Since if $q<p$ divided $2^{k_p}-1$ it would also divide $2^k-1$.

Similarly $p$ is the smallest prime dividing $2^m+1$ for some $m$ it must also be the smallest prime dividing $2^{m_p}+1$. Since if $q<p$ divided $2^{m_p}+1$ it would also divide $2^m+1$.

Now if $p$ is the smallest prime dividing $2^k-1$ and the smallest prime dividing $2^m+1$ it must also be the smallest prime dividing $2^{k_p}-1$ and the smallest prime dividing $2^{m_p}+1$. But $k_p = 2m_p$ so $3$ divides $2^{k_p}-1$. Hence $p$ must be 3.