Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
2  
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. –  Terry Tao Jun 25 '13 at 20:56
    
Do you have examples with $n\lt\omega(p^n-1)$? –  Gerry Myerson 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. –  The Masked Avenger 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$. –  Dietrich Burde Jun 26 '13 at 9:14
add comment

3 Answers

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.

share|improve this answer
1  
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?$ –  The Masked Avenger Jun 26 '13 at 4:15
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
    
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? –  The Masked Avenger 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? –  The Masked Avenger 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)$? –  The Masked Avenger 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 :). –  fedja Aug 27 '13 at 21:38
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.