$B$-powersmooth number divides $\mathrm{lcm}(1,2,3,\ldots B)$

230 Views Asked by At

Let $M$ be $B$-powersmooth (ie. all prime powers in $M$'s factorization are $\le B$). I want to prove that $M \mid \mathrm{lcm}(1,2,3,\ldots, B)$.

I thought it would be easy to prove this using induction on $B$:

It clearly holds for $B = 2$, since having $M$ 2-powersmooth means $M=2$ and on the otherhand we have $\mathrm{lcm}(1,2)=2$.

Let $B=n+1$ and suppose the statement holds for $B=n$. Let $M$ be $n+1$-powersmooth. If it is also $n$-powersmooth we're done, so suppose that $M$ isn't $n$-powersmooth. This means that $n+1$ has to be equal to a primepower, let's say $p^a$ for some $a\in\mathbb{N}$ and $p \in \mathbb{P}$.

Now let $M^{\prime}=\frac{M}{p^a}$ which is now $n$-powersmooth so it divides $\mathrm{lcm}(1,2,3,\ldots, n)$ so suppose we have some $k$ such that $M^{\prime}k=\mathrm{lcm}(1,2,3,\ldots, n)$.

\begin{align*} M \mid \mathrm{lcm}(1,2,3,\ldots n+1) &\iff M^{\prime}p^a \mid \mathrm{lcm}(\mathrm{lcm}(1,2,3,\ldots, n), p^a) \\ &\iff M^{\prime}p^a \mid \frac{kM^{\prime}p^a}{\mathrm{gcd}(kM^{\prime},p^a)} \end{align*}

Here Im stuck: it seems I need to show that the value of GCD in the denominator doesn't clear something from the numerator so RHS would become indivisible by $M^{\prime}p^a$.

Any hints how to finish this up? I would also appreciate if maybe someone comes with a simpler way how to prove this! Thanks for any tips!

1

There are 1 best solutions below

2
On BEST ANSWER

Induction doesn't work easily, but you can do it directly.

Hint: If $ p ^ k || M $, then $p^k \leq B$.