Sequence of LCM of consecutive integers

For discussing Olympiad Level Number Theory problems
rah4927
Posts:110
Joined:Sat Feb 07, 2015 9:47 pm
Sequence of LCM of consecutive integers

Unread post by rah4927 » Wed Aug 03, 2016 10:16 pm

If $k$ and $n$ are positive integers and $k\le n$ , then let $M(n,K)$ denote the lcm of the numbers $n,n+1,\cdots , n+k-1$ . Let $f(n)$ be the largest positive integer $k\le n$ such that $M(n,1)<M(n,2)<\cdots < M(n,k)$ .
Prove that :

(a) $f(n)<3\sqrt n$ for all positive integers $n$ .

(b) For any positive integer $N$ , we have $f(n) > N$ for all but finitely many positive integers $n$ .

rah4927
Posts:110
Joined:Sat Feb 07, 2015 9:47 pm

Re: Sequence of LCM of consecutive integers

Unread post by rah4927 » Mon Aug 15, 2016 5:36 pm

I will only provide a sketch of part(b) .

Note that the problem requires us to prove that for sufficiently large $n$, $f(n)$ is always greater than $N$ . Then it suffices to construct such an $n$. So intuitively, it makes sense that we want to make $n$ as large as possible. My gut reaction after that was to let $n=N^N$. Indeed, that works.

Since $M(n,k)\ge M(n,k-1)$ , it suffices to show that for $n\ge N^N$, $n+i$ ($i<N$) has a prime power that has not appeared in $n,n+1,\cdots n+i-1$ . Suppose that this is not true - then let $n+i =p_1^{e_1}\cdots p_k^{e_k}$ . Note that if $k\ge N$, then $p_k\ge N$ and by hypothesis, $p_k|n+s$ and $n+i$ for some $s<i$, we have $p_k|i-s<n$n which is clearly an impossibility.

So assume $k<N$, but since $n+i$ only has only $k$ prime powers in its factorization, we must have $p_s^{e_s}>N$ for some $s$, and by a similar reasoning, we obtain another contradiction. We are done.

Post Reply