9
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ 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. $\endgroup$
    – Terry Tao
    Jun 25, 2013 at 20:56
  • $\begingroup$ Do you have examples with $n\lt\omega(p^n-1)$? $\endgroup$ Jun 26, 2013 at 1:33
  • $\begingroup$ 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. $\endgroup$ Jun 26, 2013 at 1:49
  • $\begingroup$ 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$. $\endgroup$ Jun 26, 2013 at 9:14

3 Answers 3

3
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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?$ $\endgroup$ Jun 26, 2013 at 4:15
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ Aug 27, 2013 at 16:31
  • $\begingroup$ 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? $\endgroup$ Aug 27, 2013 at 16:38
  • $\begingroup$ 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)$? $\endgroup$ Aug 27, 2013 at 16:46
  • $\begingroup$ 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 :). $\endgroup$
    – fedja
    Aug 27, 2013 at 21:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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