There are five positive integers written in a row. Each one except for the first one is the minimal positive integer that is not a divisor of the previous one. Can all these five numbers be distinct? Boris Frenkin
Problem
Source: 46th International Tournament of Towns, Senior O-Level P3, Fall 2024
Tags: number theory
15.11.2024 14:27
No. Suppose it can. Let this function be $f(n)$. First, we note that $f(n)$ must be a prime power. Assume not, and that $f(n)=kl$, where $k$ and $l$ are coprime and are both not $1$. Then, $kl$ does not divide $n$. However, $k$ and $l$ are both smaller than $kl$, so must divide $n$, contradiction! Hence, the second number must be a prime power $p^\alpha$. If $p=2$, then the third number is $3$, and the fourth number is $2$, contradiction! If $p>2$, then the third number is $2$, the fourth number is $3$, and the fifth number is $2$, contradiction!
07.12.2024 11:05
The answer is No. For the sake of \(contradiction\), we assume it is possible. Suppose, the first number is $a$. Now if $a$ is odd, then the five numbers would be $a,2,3,2,3$ which is not distincts. So $a$ must be even. Let the $2nd$ number be $b$. Now $b$ must be even as the five numbers then would be $a,b,2,3,2$. It also must be multiple of $3$ as then the five numbers would be $a,b,3,2,3$ So $b=6k$ for some $k$. Now it implies all the numbers $1$ to $6k-1$ is a divisor of $a$ but not $6k$. That means $lcm(1,2,...,6k-1)|a$ Now $6k|lcm(k,2k,3k,4k,5k)=60k$ And $lcm(k,2k,...,5k)|lcm(1,2,...,6k-1)$ so $b=6k|lcm(1,2,3,...,6k-1)|a$ \(contadiction!\) So all these $5$ numbers cant be distinct. $\square$