Consider the expression $$P(x):=\text{lcm}_{\text{$p$ prime $\leq x$}} (p^2-1).$$ As the prime factors of $P(x)$ are $<x$, for every prime $q<x$ its highest power in $P(x)$ must also divide some $p^2-1$ and is therefore $\leq p^2-1 \leq x^2-1$. Thus we have an obvious upper bound of the form $P(x)<(x^2-1)^{\pi(x)}$, that is $\log P(x)=O(x)$.

Can one do better than this? What if instead of $p^2-1$ we had $p+1$ or $p-1$?

[I am thinking of substantial improvements, such as $O(x\log \log x /\log x)$ or $O(x/\log x)$. The above argument with more care leads to the upper bound $\prod_{p \leq x} (p^2-1)$, but its log is still an $O(x)$.]

  • $\begingroup$ I forgot to add that with some powerful tools such as Elliott-Halberstam one can do better than this, but I need unconditional answers. $\endgroup$
    – lookatthis
    Aug 2, 2014 at 10:42
  • $\begingroup$ LCM of $p-1$ is tabulated at oeis.org/A058254 (but with no links or information about bounds). Similarly, LCM for $p+1$ at oeis.org/A085272 $\endgroup$ Aug 3, 2014 at 0:18

1 Answer 1


You are probably aware of the following, but here are some heuristics that could be useful to someone. I am not entirely sure how much of it can be made formal.

If $q$ is a small prime, then $P(n)$ will be divisible by $q$ for large $n$, because for large $n$ you will always be able to find a prime $p \equiv \pm 1 \pmod{q}$, by Dirichlet's theorem. In other words, $P(n)$ must be divisible by lots of small primes. However, I claim that $P(n)$ will not be divisible by very many large primes.

More precisely, let $q$ be a prime number larger than $M := \frac{n}{\sqrt{\log(n)}}$. Then the probability that either $2q-1$ or $2q+1$ is prime is roughly $\frac{c}{\log(n)}$ for some small computable constant $c$. And the same holds true for $aq\pm1$ for any $a$ with $2 \le a \le \frac{n}{q} < \sqrt{\log(n)}$. So the probability that $q$ divides $P(n)$ is upper bounded by

$$1 - \left(1 - \frac{c}{\log(n)}\right)^{\sqrt{\log(n)}} \approx 1 - e^{\frac{-c}{\sqrt{\log(n)}}} \approx \frac{c}{\sqrt{\log(n)}}$$

Therefore, ignoring factors of $o(1)$ for convenience,

$$P(n) \le n^{\pi(M)} n^{\frac{c(\pi(n) - \pi(M))}{\sqrt{\log(n)}}} = e^{\frac{n}{\sqrt{\log(n)}}} e^{\frac{cn}{\sqrt{\log(n)}}} = e^{\frac{(c+1)n}{\sqrt{\log(n)}}} $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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