A B. 5244. feladat (2022. április)

B. 5244. Határozzuk meg azokat az \(\displaystyle n > 4\) egész számokat, melyekre minden \(\displaystyle n\)-nél kisebb \(\displaystyle k\) összetett számra \(\displaystyle (k,n) > 1\).

Javasolta: Róka Sándor (Nyíregyháza)

(5 pont)

A beküldési határidő 2022. május 10-én LEJÁRT.

Megoldás. Ha egy \(\displaystyle p\) prímszámra \(\displaystyle p^2<n\), akkor a feltétel alapján \(\displaystyle (p^2,\,n)>1\), ami azt jelenti, hogy \(\displaystyle n\) biztosan osztható a \(\displaystyle p\) prímszámmal. Tehát ha egy \(\displaystyle n>4\) egész számra teljesül a feltétel, akkor osztható kell legyen minden \(\displaystyle \sqrt{n}\)-nél kisebb prímszámmal. Ez megfordítva is igaz, tegyük fel ugyanis, hogy \(\displaystyle n\) osztható minden \(\displaystyle \sqrt{n}\)-nél kisebb prímszámmal. Legyen \(\displaystyle k<n\) egy összetett szám, ekkor \(\displaystyle k\) felírható \(\displaystyle k=pqk'\) alakban, ahol \(\displaystyle p\), \(\displaystyle q\) prímszámok (esetleg \(\displaystyle p=q\)), \(\displaystyle k'\) pedig egész szám. Mivel \(\displaystyle pqk'=k<n\), ezért \(\displaystyle \min(p,q)<\sqrt{n}\), és így \(\displaystyle \min(p,q)\) a \(\displaystyle k\) és \(\displaystyle n\) számok egy közös prímosztója, és így \(\displaystyle (k,n)>1\).

Legyenek a \(\displaystyle \sqrt{n}\)-nél kisebb prímszámok \(\displaystyle p_1,\ p_2,\ \dots,\ p_k\) (ahol \(\displaystyle p_i\) az \(\displaystyle i\)-edik prímszám). Ha az \(\displaystyle n\) számra teljesül a feltétel, akkor \(\displaystyle n\) osztható a \(\displaystyle p_1,\ p_2,\ \dots,\ p_k\) prímek mindegyikével, és így \(\displaystyle p_1p_2\dots p_k\leq n\leq p_{k+1}^2\) (hiszen \(\displaystyle p_k\) a legnagyobb \(\displaystyle \sqrt{n}\)-nél kisebb prím).

Most belátjuk, hogy \(\displaystyle p_1p_2\dots p_k>p_{k+1}^2\), ha \(\displaystyle k\geq 4\). Az állítást \(\displaystyle k\)-ra vonatkozó indukcióval igazoljuk, \(\displaystyle k=4\) esetén valóban \(\displaystyle 2\cdot 3\cdot 5 \cdot 7=210>121=11^2\).

Az indukciós lépés igazolásához tegyük fel, hogy \(\displaystyle k\geq 5\) és a \(\displaystyle p_1p_2\dots p_{k-1}>p_{k}^2\) egyenlőtlenséget már igazoltuk, célunk belátni, hogy \(\displaystyle p_1p_2\dots p_k>p_{k+1}^2\) is teljesül. Csebisev tétele (más néven Bertrand posztulátuma) szerint bármely pozitív egész szám és kétszerese között van prímszám, így \(\displaystyle p_{k+1}<2p_k\). Ezt és az indukciós feltevést használva:

\(\displaystyle p_{k+1}^2<4p_k^2<4p_1p_2\dots p_{k-1}<p_1p_2\dots p_k,\)

hiszen \(\displaystyle k\geq 5\) alapján \(\displaystyle p_k\geq 11\geq 4\).

Tehát \(\displaystyle k\geq 4\) esetén \(\displaystyle p_1p_2\dots p_k>p_{k+1}^2\), ami azt jelenti, hogy ha az \(\displaystyle n\) számra teljesül a feltétel, akkor a \(\displaystyle \sqrt{n}\)-nél kisebb prímszámok közül a legnagyobb értékére \(\displaystyle p_k\leq p_3=5\) teljesül. Így \(\displaystyle \sqrt{n}\)-nél egy, kettő vagy három kisebb prímszám van. Vizsgáljuk meg a három esetet külön-külön.

Ha csak egy van, akkor ez a 2, és \(\displaystyle n\leq 9\) páros szám kell legyen. Mivel \(\displaystyle n>4\), ezért csak \(\displaystyle n=6\) vagy \(\displaystyle n=8\) lehet, mindkét szám megoldást ad.

Ha kettő is van, akkor ezek a 2 és a 3, és a \(\displaystyle 9<n\leq 25\) számnak 6-tal oszthatónak kell lennie. Így \(\displaystyle n\) értéke 12, 18 vagy 24 lehet, mindhárom szám megoldást ad.

Végül, ha három is van, akkor ezek a 2, 3 és az 5, és a \(\displaystyle 25<n\leq 49\) számnak \(\displaystyle 2\cdot 3\cdot 5=30 \)-cal oszthatónak kell lenne. Így ebben az esetben \(\displaystyle n\) értéke csak 30 lehet, ami valóban megoldást ad.

Tehát a megadott tulajdonsággal rendelkező számok: \(\displaystyle 6,8,12,18,24,30\).

Megjegyzés. Csebisev tételének bizonyítása megjelent a KöMaL-ban, 1950/február, 7-13. o.: Bizonyítsuk be Csebisev tételét 1.; 1950/március, 90-91. o.: Bizonyítsuk be Csebisev tételét 2.; 1950/május, 121-124. o.: Bizonyítsuk be Csebisev tételét 3.

Egyelőre mindhármat szkennelve lehet olvasni itt: KöMaL Archívum szkennelt oldalak.

Statisztika:

59 dolgozat érkezett.
5 pontot kapott:	Bálint Béla, Balla Álmos András, Bencsik Dávid, Bényei Borisz, Christ Miranda Anna, Csonka Illés, Czanik Pál, Diaconescu Tashi, Dienes Ervin Fotisz, Duchon Márton, Farkas 005 Bendegúz, Farkas 512 Izabella, Foris Dávid, Fülöp Csilla, Horváth 530 Mihály, Jánosik Máté, Kalocsai Zoltán, Kocsis 827 Péter, Koleszár Domonkos, Kovács Benedek Noel, Lovas Márton, Melján Dávid Gergő, Mohay Lili Veronika, Móricz Benjámin, Nádor Artúr, Nagy 429 Leila, Németh Márton, Nguyen Kim Dorka, Romaniuc Albert-Iulian, Sági Mihály, Simon László Bence, Somogyi Dalma, Szakács Ábel, Szanyi Attila, Tarján Bernát, Tóth 057 Bálint, Török Eszter Júlia, Tran Dávid, Varga Boldizsár, Virág Rudolf, Wiener Anna, Zömbik Barnabás.
4 pontot kapott:	Bencz Benedek, Csilling Dániel, Diószeghy Erzsébet, Juhász-Molnár Erik, Molnár Péter, Sütő Áron.
3 pontot kapott:	5 versenyző.
2 pontot kapott:	4 versenyző.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2022. áprilisi matematika feladatai