For each $n$, does there exist a prime $p$ and integer $k$ such that $p^k - 1$ has exactly $n$ prime divisors?

Question

Let $n \geq 1$ be some integer. Can we always find a prime power $p^k$ such that $p^k - 1$ has exactly $n$ distinct prime divisors?

For example:

• $n = 1$ example: $2^2 - 1 = 3$
• $n = 2$ example: $5^2 - 1 = 2^2 \cdot 3$
• $n = 3$ example: $7^3 - 1 = 2 \cdot 3^2 \cdot 19$
• $n = 4$ example: $5^6 - 1 = 2^3 \cdot 3^2 \cdot 7 \cdot 31$

We can always find a prime power $p^k$ with $\geq n$ prime divisors. Let $p_1, p_2, \ldots, p_n$ be distinct primes, $p_i \neq p$ for each $i$. Then $p^k \equiv 1 \mod{p_1p_2 \ldots p_n}$ for some positive $k$, for example we can choose $$k = (p_1 - 1)(p_2 - 1)\ldots(p_n - 1)$$

Answer 1

You might be interested in the Cunningham Project, about the factorization of numbers of the form $b^n\pm1$ and sequence A046800 in OEIS. According to the existing data, the following conjecture seems plausible: for every $n\in\mathbb{N}$ there exists $k\in\mathbb{N}$ such that $2^k-1$ has exactly $n$ distinct prime factors.

Define $f(n)$ as the smallest $k$ such that $2^k-1$ has exactly $n$ distinct prime factors. The values of $f(n)$ for $1\le n\le30$ are:

2,4,8,12,20,24,40,36,48,88,60,72,150,132,120,156,144,200,204,210,180,
324,476,288,300,432,396,480,360,468

and $f(31)>500$.