$\omega(p^n - 1)$ as $n \rightarrow \infty$

Question

Although I am also interested in the number of distinct prime factors (not counting multiplicity), today I use $\omega(m)$ to denote the number of (positive) prime factors (with multiplicity) of the integer $m$. Thus $\omega(75)=3$ in this post. (I may switch to $\omega(75)$ being 2 in a different post.)

What is known about $\omega(p^n - 1)$ for fixed integer $p \gt 1$ and growing $n$? When $n$ is composite, algebraic factorization guarantees something like $\Omega(\omega(n))$ factors. I am especially interested in cases where $n\lt \omega(p^n - 1)$. I do not have a proof, but I think that for fixed $p$ one can show there are only finitely many such cases.

If something is known for $p$ prime, that would interest me greatly. I still think the general case is of note, and would appreciate a reference.

Answer 1

For fixed $p$ and any $d$, the prime divisors of $\Phi_d(p)$ (cyclotomic polynomial) either divide $d$ or are $1\pmod{d}$. So we have a constant $c_p$, that satisfies $$\omega(\Phi_d(p))\le c_p \frac{d}{\log d}$$ and so we get $$\omega(p^n-1)\le c_p \sum_{d|n} \frac{d}{\log d}.$$ This is always less than $n$ for large enough $n$, so your claim follows.

Answer 2

This is a complement to Gjergji's answer which seems to be basically OK, but there are some details that seems to be missing.

We first remark that $$ p^n-1= \prod_{d|n} \Phi_d(p), $$ where $\Phi_d(p)$ are the cyclotomic polynomials of degree $\phi(d) \leq d$.

The fact that the divisors of $\Phi_d(p)$ are either of form $kd+1$ or a divisor of $d$ (see e.g. http://number.subwiki.org/wiki/Congruence_condition_on_prime_divisor_of_cyclotomic_polynomial_evaluated_at_an_integer) is sufficient to yield

$$\omega(\Phi_d(p)) \leq c_p \frac {d} {\log d}$$

for the number of prime factors that are of form $kd+1$. This is because they must in particular be greater than $d$ and $d^{d \log p/\log d}=p^d \geq \Phi_d(p)$

So by Gjergji's answer it is sufficient to show that the number of prime factors (counted with multiplicity) $q$ such that $q|n$ that divides $p^n-1$ are not too many. Also it is sufficient to consider the primes $q$ say less than $p^2$ by a similar argument as above (we can have at most $n/2$ primefactors of size $p^n$ if all prime factors are greater than $p^2$).

It is clear that there exists some constant $m_0$ such that for all primes $q<p^2$ we have that $q^{m_0}$ does not divide $p^{q-1}-1$. It follows that if $n$ has prime factors of order at most $m_1$, then $q^{m_0+m_1}$ does not divide $p^n-1$. Thus the number of prime factors are at most $p^2 (m_0+m_1)$ where $n \geq 2^{m_1}$. This gives us that the number of prime factors that divides $n$ and are less than $p^2$ is $O(\log n)$ and that they are negligeble

Answer 3

Let's do some elementary math. olympiad style number theory. All we need to show is that for each fixed prime $q$, $v_q(p^n-1)=o(n)$. Since $gcd(p^n-1,p^m-1)=p^{gcd(n,m)}-1$, if $n=n_0$ is the least power such that $v_q(p^n-1)>v_q(p-1)$, then every $n$ satisfying this inequality should be divisible by $n_0$. Then the Lifting Exponent Lemma gives $v_q(p^n-1)\le C(p,q)+v_q(n)\le C(p,q)+\log n$. The end.