For each positive integer $n$ let $a_n$ be the largest positive integer satisfying \[(a_n)!\left| \prod_{k=1}^n \left\lfloor \frac{n}{k}\right\rfloor\right.\]Show that there are infinitely many positive integers $m$ for which $a_{m+1}<a_m$.
Problem
Source: 2024 Israel TST Test 8 P1
Tags: factorial, number theory, floor function
10.05.2024 13:02
My problem First, we will prove the following lemma: for all $m$ such that $n \geq m^2$ there exists a positive integer $k$ such that $\lfloor\frac{n}{k} \rfloor = m$. Proving it would show that $a_n \geq \lfloor \sqrt{n} \rfloor$, as every number less than or equal to $\lfloor \sqrt{n} \rfloor$ would appear in the product.
We will now show that for all primes $p$ we have $a_{p^2-p} \geq p > a_{p^2-1}$. First notice that because of the above lemma, $(p-1)! \mid \prod_{k=1}^{p^2-p} \left \lfloor \frac{p^2-p}{k} \right \rfloor$, as $\lfloor \sqrt{p^2-p} \rfloor = p-1$. So to prove that $a_{p^2-p} \geq p$ it's enough to notice that $p \mid \left \lfloor \frac{p^2-p}{1} \right \rfloor \mid \prod_{k=1}^{p^2-p} \left \lfloor \frac{p^2-p}{k} \right \rfloor$. Now let's prove that $p$ doesn't divide $\prod_{k=1}^{p^2-1} \left \lfloor \frac{p^2-1}{k} \right \rfloor$. Assume for contradiction it does, then there exists some $k$ such that $p \mid \left \lfloor \frac{p^2-1}{k} \right \rfloor$. Let $\left \lfloor \frac{p^2-1}{k} \right \rfloor = ap$, and denote the residue of $p^2-1$ modulo $k$ by $r$. Then $p^2-1=apk+r$, which means that $r \equiv -1 \pmod p \implies r \geq p-1$. Notice that $k>r$ (because $r$ is a residue modulo $k$, so $k \geq p$, which means that $p^2-1=apk+r \geq p^2$, Which is a contradiction. Therefore, $p$ doesn't divide $\prod_{k=1}^{p^2-1} \left \lfloor \frac{p^2-1}{k} \right \rfloor$, which means that $a_{p^2-1} < p$. Therefore, $a_{p^2-1} < p \leq a_{p^2-p}$, which solves the problem.
14.08.2024 11:16
对于每个正整数$n$,定义$a_n$是使得下式成立的最大正整数: \[(a_n)!\left| \prod_{k=1}^n \left\lfloor \frac{n}{k}\right\rfloor\right.\]证明:有无穷多个正整数$m$,满足$a_{m}>a_{m+1}$