[Solution] Achieving 1/lcm

Problem statement here.


We prove by induction.

First note that  $\text{lcm}[1, 2, \dots, n+1] = d_{n+1} = p d_n$ iff n+1 is a power of a prime number $p$ and $d_{n+1} = d_n$ otherwise. Also note that, if $n+1 = p^k$, then $p^{k-1}$ is the highest power of $p$ that divides $d_n$.


Now if $n+1$ is not a power of a prime, then we need to choose $A$ and $B$ such that

$$\frac{A}{d_n} + \frac{B}{n+1} = \frac{1}{d_n}$$

We can write $\frac{1}{n+1}$ as $\frac{Q}{d_n}$ where $Q = \frac{d_n}{n+1}$ which is an integer.

Choosing $A = Q+1$ and $B= -1$ will do the trick.

Now assume $n+1$ is the power of a prime $p$. We need to choose $A$ and $B$ such that

$$\frac{A}{p^{k-1}Q} + \frac{B}{p^k} = \frac{1}{p^kQ}$$

Note that we have $p$ and $Q$ are relative prime (more fomally, $(p,Q) = 1$) because that highest power of $p$ that divides $d_n$ is $p^{k-1}$.

i.e we need

$$pA + BQ = 1$$

Since $(p,Q) = 1$, by Bezout's Identity there exist $A, B$ such that $pA + BQ = 1$ and we are done.