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

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.

• Assuming the abc conjecture, $p^n-1$ would have radical $p^{n-o(n)}$ for fixed p and $n \to \infty$, which would imply at least $(\log p - o(1)) n / \log n$ distinct prime factors, and thus also at least this many if one counts multiplicity. Even without Mochizuki's claimed proof of the abc conjecture, the previously known partial results (see en.wikipedia.org/wiki/Abc_conjecture ) should still give something non-trivial here. Jun 25 '13 at 20:56
• Do you have examples with $n\lt\omega(p^n-1)$? Jun 26 '13 at 1:33
• Yes, take p to be one more than a highly composite number. However, a later post will show I am really interested in $\omega(\sigma(p^n))$. Even then I have examples only for n small. Jun 26 '13 at 1:49
• For the prime $p=2^{16}+1$ we have $n<\Omega(p^n-1)$ for $n=1,\cdots ,18$, but $\Omega(p^{19}-1)=18$. Jun 26 '13 at 9:14

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.

• I see that your first inequality follows if "enough" factors of the cyclotomic polynomial are greater than $d$. While I believe the inequality, can you provide more justification for the denominator $\log d?$ Jun 26 '13 at 4:15

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

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.

• Thank you for looking at this. For sake of clarity, please confirm or deny the statement "C(p,q) is a value that depends only on p and q, and is just a uniformly effectively computable constant in p and q." (I've seen stuff where C returns a function and not a number.) Also, I am not finding a link to the PDF in the first post of your linked thread. Do you have a URL for the PDF? Aug 27 '13 at 16:31
• Also, I would appreciate your take on my linked question on counting factors (see sidebar). Are there AoPS problems which take (something like) the approach suggested there? Aug 27 '13 at 16:38
• Can we say further that $n_0 \lt q$ and also from LTE one has $v_q(p^n - 1) \leq C(p,q) + v_q(n/n_0)$? Also, can one do better upper bounds with $C(p,q)$ than $C(p,q) \lt n_0 \log(p)/\log(q)$? Aug 27 '13 at 16:46
• Yes to "effectively computable". The pdf link is in one of the last posts in the linked thread (the most recent version). As to better bounds and factors, I have to think a bit :). Aug 27 '13 at 21:38