Given the first $n$ primes, we can label the $k$th prime as $p_k$. So, what is the least common multiple(LCM) of {$p_1 - 1$, $p_2 - 1$, $p_3 - 1$, ..., $p_n-1$}? In other words, if we subtract $1$ from each of the first $n$ primes, and wish to find the LCM of these new values, can we find a lower bounds for this LCM?

  • 1
    $\begingroup$ Lower than what? $\endgroup$ – barak manos Dec 3 '14 at 14:28
  • $\begingroup$ @barakmanos: Sorry, I should explain. I'm searching for an asymptotic function/expansion that the LCM is greater than or equal to. Does this help? $\endgroup$ – Matt Groff Dec 3 '14 at 14:30
  • $\begingroup$ Your LCM is $\lambda(p_n\#)$. May be you get lower bounds from Carmichael/primorial formulas. $\endgroup$ – gammatester Dec 3 '14 at 14:32
  • 2
    $\begingroup$ This is sequence A058254 in OEIS. Unfortunately nothing is said about its asymptotic behavior. $\endgroup$ – Julián Aguirre Dec 3 '14 at 15:07
  • $\begingroup$ @gammatester: I don't think this would do very much; the bounds on $\lambda$ are very weak. $\lambda(48665323350093056511370687590824766511200)=2520,$ for example. $\endgroup$ – Charles Dec 3 '14 at 16:35

By the most recent bound on Linnik's Theorem, there is an absolute constant $c$ such that for every prime $q < cp_n^{1/5}$, there is a prime $p < p_n$ such that $p \equiv 1 \pmod{q}$. Your least common multiple is therefore divisible by all primes below $cp_n^{1/5}$. The prime number theorem implies that the product of all primes below $cp_n^{1/5}$ is $e^{(c + o(1))p_n^{1/5}}$, and it follows that this is a lower bound on your lcm as well.

Conjecturally there is a prime $p < p_n$ such that $p \equiv 1 \pmod{q}$ for every $q < cp_n^{1-\epsilon}$, and this would provide a lower bound of $e^{(c + o(1))p_n^{1-\epsilon}}$. On the other hand, your lcm is not divisible by any prime larger than $\frac{1}{2}p_n$ so, again using the prime number theorem, a straightforward upper bound is $e^{(\frac{1}{2} + o(1))p_n}$.

| cite | improve this answer | |

I believe there is a recursive formula for this:

Let L(k) = LCM({$p_1 - 1$, $p_2 - 1$, $p_3 - 1$, ..., $p_k$}

Then L(k+1) = L(k) ($p_{k+1}-1$) / GCD(L(k),$p_{k+1}-1$)

where GCD = greatest common divisor

| cite | improve this answer | |

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.