11
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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