3
$\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$
  • 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$ – Countingstuff May 1 '18 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 May 1 '18 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$ – Countingstuff May 1 '18 at 10:17
  • $\begingroup$ @Countingstuff I said if $n$ is prime then $lcm(1,2,3,4,5)\ne 5!$ Thats right . $\endgroup$ – Saradamani May 1 '18 at 10:18
  • $\begingroup$ Ok apologies, and sorry for filling up the comment space, $lcm(1,2,3,4,5) = 60 \neq 5!$ $\endgroup$ – Countingstuff May 1 '18 at 10:19
2
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.