Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

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:

A B. 5244. feladat értékelése még nem fejeződött be.


A KöMaL 2022. áprilisi matematika feladatai