Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 5 down vote accepted

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:


and $f(31)>500$.

share|cite|improve this answer
Thanks for the answer. So this might be an open problem, or at least difficult? – spin Feb 2 '13 at 8:22
There might be an easy solution lurking somewhere, but I doubt it. – Julián Aguirre Feb 2 '13 at 19:37

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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