If I'm given a prime number $p$: is there an upper bound to the number of prime factors of $p−1$? Alternatively, is there a way to calculate the number of prime factors of $p−1$ without actually calculating the factors?
$\begingroup$
$\endgroup$
3
-
9$\begingroup$ One cannot expect a bound better than a typical integer. Indeed, there is nothing preventing $p-1$ from having as many prime factors as is allowed for a number that size. $\endgroup$– Stanley Yao XiaoCommented Apr 21, 2023 at 14:23
-
2$\begingroup$ So far the largest prime found which is one more than the product of the first $n$ primes has $n=392113$ and so $p-1$ has that many distinct prime factors. $\endgroup$– HenryCommented Apr 21, 2023 at 15:13
-
1$\begingroup$ While the Proth prime $10223 \times 2^{31172165} + 1$ clearly is one more than a number with $31172166$ prime factors counted with repetition $\endgroup$– HenryCommented Apr 21, 2023 at 15:15
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
To reiterate Stanley Yao Xiao's comment, one should not expect that $p-1$ has any more or less prime factors than a typical integer of size $p$. For an arbitrary integer $n$, the bound $$ \omega(n) \ll \frac{\log n}{\log\log n} $$ is standard (see Hardy and Wright's "An Introduction to the Theory of Numbers" for a proof of this). Here $\omega(n)$ denotes the number of distinct prime factors of $n$.
It is known that integers of the form $p-1$ have about the same number of divisors as typical integers $n$ on average. The Titchmarsh divisor problem states that $$ \sum_{p\leq x} \tau(p-1) \sim C x $$ for some explicit constant $C$, where $\tau(n)$ denotes the number of positive divisors of $n$. Stated differently, we may write $$ \frac{1}{\pi(x)} \sum_{p\leq x} \tau(p-1) \sim C \log x $$ by the Prime Number Theorem, and so $p-1$ has $\asymp \log x$ divisors on average for $p\leq x$, the same as for all integers up to $x$ (up to a constant factor).
-
1$\begingroup$ It's worth probably pointing out that @OfirGorodetsky's previous answer here ( mathoverflow.net/a/436137 ) is also relevant, especially the remarks about the central limit theorem. $\endgroup$ Commented Apr 22, 2023 at 5:20
-
$\begingroup$ @JoshuaStucky I deleted my first comment because it was not actually accurate in terms of describing the papers I mentioned (feel free to delete yours as well). I wrote it because the last line of the answer mentions "prime factors" where I think it should be "divisors". $\endgroup$ Commented Apr 22, 2023 at 10:48
-
$\begingroup$ @OfirGorodetsky Ahh, didn't see that typo. Corrected! $\endgroup$ Commented Apr 22, 2023 at 16:00
-
5$\begingroup$ Also, since one has $\omega(m) \gg \frac{\log m}{\log \log m}$ for infinitely many $m$ (in particular, primorials), it follows from Linnik's theorem that one also has $\omega(n) \gg \frac{\log n}{\log \log n}$ for any infinitely many $n$ of the form $p-1$ (take $p$ to be the first prime in the progression $1 \hbox{ mod } m$ for $m$ a primorial; Linnik's theorem tells us that $\log (p-1) \asymp \log n$). en.wikipedia.org/wiki/Linnik%27s_theorem . So the upper bound $\omega(n) \ll \frac{\log n}{\log\log n}$ is sharp up to constants for $n=p-1$. $\endgroup$ Commented Apr 22, 2023 at 21:08