Take the 2-minute tour ×
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.

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|improve this question
add comment

1 Answer 1

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:

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

share|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
add comment

Your Answer

 
discard

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.