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α. 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. ◻