4
$\begingroup$

Let $m$ be the largest integer $\le n$ which is a power of 2.Put $l_n=LCM(1,2,3...n).$Show that $l_n/m$ is odd and that for every integer $k\le n,k\ne m,l_n/k$ is even. Hence prove that $\displaystyle \sum_{i=1}^n \dfrac{1}{i}$ is not an integer

I tried this argument that if $n\in \mathbb{P}$, then $n!=LCM(1,2,3,...n)$

But this argument is wrong since $LCM(1,2,3,4,5)\ne 5!$. Here $5$ is a prime

But observe that $LCM(1,2,3,...n)$ for $n\in \mathbb{P}$ is the product of all prime numbers $\le n$ but $\ge 1$ and power of $2's$

Then $m=2^x(say)\le n$

Then we know $\#$ of $2's$ is $\le 2^{\left \lfloor{\dfrac{n}{2}}\right \rfloor }$

Note as $n$ is prime and $n>2(say)$, we have $n$ is odd and $\therefore \space (n-1)$ is even

Thus $l_n/m=\dfrac{2^{\left \lfloor{\dfrac{n}{2}}\right \rfloor }\cdot (\text{1.3.5.7....(2n-2)} )}{2^x}=2^{\big(\left \lfloor{\dfrac{n}{2}}\right \rfloor -x \big)}\cdot \text{1.3.5.7....(2n-2)} $

Now if $\left \lfloor{\dfrac{n}{2}}\right \rfloor=x$, we are done $l_n/m$ is indeed odd.

I also know what @Jeff Snider proved in an earlier answer long back something like this:

Let $p_k$ be the $k$-th prime. Let $n$ be the largest natural number such that $p_n\le N$. Then the LCM of the first $N$ natural numbers is given by $$\prod_{k=1}^n p_k^{\,\lfloor \ln N / \ln p_k\rfloor}.$$

Does this help me anyhow?

How do I arrive at a definitive proof of all the three sections of the problem?

$\endgroup$
7
  • 1
    $\begingroup$ Consider how the prime factorisations of all the numbers smaller than $n$ look, in particular consider the multiplicity of $2$ in these factorisations, and deduce what the multiplicity of $2$ in the lcm must be. For the final part I guess the idea is to put the sum over a common denominator and see what you get. $\endgroup$ Commented May 1, 2018 at 10:13
  • $\begingroup$ @Countingstuff "deduce what the multiplicity of 2 in the lcm must be"-I have already done so. Please see my OP. $\endgroup$
    – Saradamani
    Commented May 1, 2018 at 10:14
  • $\begingroup$ OK perhaps, but I disagree with the first line, so I don't see it, for example $lcm(1,2,3,4) = 12 \neq 4!$ $\endgroup$ Commented May 1, 2018 at 10:17
  • 1
    $\begingroup$ @Countingstuff I said if $n$ is prime then $lcm(1,2,3,4,5)\ne 5!$ Thats right . $\endgroup$
    – Saradamani
    Commented May 1, 2018 at 10:18
  • $\begingroup$ Ok apologies, and sorry for filling up the comment space, $lcm(1,2,3,4,5) = 60 \neq 5!$ $\endgroup$ Commented May 1, 2018 at 10:19

1 Answer 1

3
$\begingroup$

Given positive integers $n$ and $m$ we can write $n=p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r}$ and $m=p_1^{b_1}p_2^{b_2}\cdots p_r^{b_r}$, where $p_1,\ldots,p_r$ are the primes dividing $m$ or $n$ (and some of the exponents may be $0$). Then $$\text{lcm}(n,m)=p_1^{\max(a_1,b_1)}p_2^{\max(a_2,b_2)}\cdots p_r^{\max(a_r,b_r)}.$$ (This is clearly a multiple of both, and any multiple of both must be divisible by $p_i^{\max(a_i,b_i)}$ for each $i$.)

So what is the power of $p$ in $\text{lcm}(1,\ldots,n)$, where $p$ is a prime $\leq n$?

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .