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.
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.
No comments:
Post a Comment