Problem B. 5366. (February 2024)

B. 5366. Is it possible to find a composite number \(\displaystyle n>1\) with the following property: if \(\displaystyle 1=d_1<d_2<\ldots<d_k=n\) denote the positive divisors of \(\displaystyle n\), then \(\displaystyle d_i\) is divisible by \(\displaystyle (d_{i-1} + d_{i-2})\) for all \(\displaystyle 3 \leq i \leq k\)?

(Based on IMO problem 2023/1)

(3 pont)

Deadline expired on March 11, 2024.

Sorry, the solution is available only in Hungarian. Google translation

Megoldás. Azt fogjuk igazolni, hogy nem létezik ilyen \(\displaystyle n\).

Tegyük fel, hogy egy \(\displaystyle n\) számra teljesülnek a feladat feltételei. Ha \(\displaystyle 3\leq i\leq k\), akkor \(\displaystyle d_{i-1}+d_{i-2}\mid d_i\mid n\), így \(\displaystyle d_{i-1}+d_{i-2}\) is az \(\displaystyle n\) szám egyik osztója. Mivel \(\displaystyle d_{i-1}\)-nél nagyobb, és osztja \(\displaystyle d_i\)-t, ezért csak \(\displaystyle d_{i-1}+d_{i-2}=d_i\) lehetséges. Speciálisan, az összefüggést \(\displaystyle i=k\)-ra alkalmazva (mivel \(\displaystyle n\) összetett szám, így \(\displaystyle k\geq 3\), vagyis a feltétel alkalmazható) \(\displaystyle d_{k-1}+d_{k-2}=d_k=n\), azonban az \(\displaystyle n\) szám második és harmadik osztója legfeljebb \(\displaystyle n/2\), illetve \(\displaystyle n/3\), így \(\displaystyle d_{k-1}+d_{k-2}\leq n/2+n/3=5n/6\) miatt ezzel ellentmondásra jutottunk.

Megjegyzés. A \(\displaystyle d_{i-1}+d_{i-2}=d_i\) összefüggést a kis osztókra használva kapjuk, hogy \(\displaystyle d_3=d_2+d_1=d_2+1\). Itt \(\displaystyle d_2\) az \(\displaystyle n\) összetett szám legkisebb prímosztója, \(\displaystyle d_3\) pedig vagy a második legkisebb prímosztó, vagy a legkisebb prímosztó négyzete. Mivel \(\displaystyle d_2\nmid d_2+1=d_3\), így utóbbi nem lehetséges. Az \(\displaystyle n\) szám két legkisebb prímosztója tehát \(\displaystyle d_2\) és \(\displaystyle d_3=d_2+1\), paritásuk különbözik, így csak \(\displaystyle d_2=2\), \(\displaystyle d_3=3\) lehet. Ezért a 6 is osztó, így biztosan \(\displaystyle 3<k\), így \(\displaystyle d_4=d_3+d_2=5\). Ezzel elletmondásra jutottunk, mert egyrészt \(\displaystyle d_5=6\) kell legyen, hiszen \(\displaystyle 6\mid n\), másrészt a \(\displaystyle d_5=d_4+d_3=8\) összefüggésnek is teljesülnie kellene.

Statistics:

111 students sent a solution.
3 points:	92 students.
2 points:	10 students.
1 point:	2 students.
Not shown because of missing birth date or parental permission:	4 solutions.

Problems in Mathematics of KöMaL, February 2024