Given the first $n$ primes, find the least common multiple of $p_1 - 1$, $p_2 - 1$, ..., $p_n - 1$

367 Views Asked by At

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

There are 1 best solutions below

0
On

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