Feladat: B.3651 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Backhausz Ágnes ,  Bartha Emőke ,  Bartha Ferenc ,  Bérczi Kristóf ,  Bereczki Péter ,  Birkus Róbert ,  Bitai Tamás ,  Boros Balázs ,  Csajbók Bence ,  Czank Tamás ,  Eckert Bernadett ,  Farkas Balázs ,  Fehér Borbála ,  Fehér Gábor ,  Füredi Mihály ,  Gehér György ,  Hubai Tamás ,  Jankó Zsuzsanna ,  Juhász Máté Lehel ,  Király Csaba ,  Komáromy Dani ,  Koreck Péter ,  Korotij Ágnes ,  Kórus Péter ,  Kovács Péter ,  Molnár András ,  Pálinkás Csaba ,  Pongrácz András ,  Ruppert László Gábor ,  Salát Máté ,  Simon Balázs ,  Szabó Botond ,  Szabó Tamás ,  Szalai Attila ,  Tábor Áron ,  Torma Róbert ,  Tóthmérész Lilla ,  Vaskó Richárd 
Füzet: 2004/szeptember, 334 - 335. oldal  PDF file
Témakör(ök): Legnagyobb közös osztó, Prímszámok, Oszthatósági feladatok, Feladat
Hivatkozás(ok):Feladatok: 2003/május: B.3651

A pozitív egész n számot osztatlannak nevezzük, ha abból, hogy 1<k<n és (k,n)=1, következik, hogy k prímszám.
Hány 2-nél nagyobb osztatlan szám van?

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Megoldás. Ha létezik olyan p prímszám, hogy pn és p<n, akkor p2<n és (p2;n)=1, de p2 nem prímszám. Ezért ha n osztatlan szám, akkor az összes n-nél kisebb prímmel oszthatónak kell lennie.
Ez a feltétel elegendő is: ha k<n és k összetett, akkor k-nak van k-nál nem nagyobb prímosztója; ez a prímosztó kisebb, mint n, így összetett k-ra (k;n)>1.
n=3 és n=4 nyilván osztatlan.
Ha n5, akkor ‐ a prímszámok növekvő sorozatát p1,p2,...-vel jelölve ‐ a n-nél kisebb prímek legyenek p1,p2,...,pi. Ha n osztatlan szám, akkor az előbbiek szerint n=ap1p2...pi (aN+) és nyilván npi+12, tehát

p1p2...pipi+12.
Csebisev tétele szerint pi+1<2pi és pi<2pi-1, ezért ha i3, akkor
p1p2...pi-2pi+12pipi-1<4pi2pipi-1=4pipi-1<8,
így 235>8 miatt i4. Mivel i1, négy eset van:
a) i=1, ekkor 5n9 (n3 miatt; és mindig csak az új lehetséges n-eket vizsgáljuk) és 2n szükséges. A megfelelő számok a 6 és a 8.
b) i=2, ekkor 10n25 és 23=6n szükséges. A lehetséges számok: 12, 18 és 24.
c) i=3, ekkor 26n49 és 235=30n szükséges, így csak az n=30 felel meg.
d) i=4, ekkor 50n121 és 2357=210n szükséges, ami nyilván lehetetlen.
Az előbbiek szerint a fent felsorolt számok mind osztatlanok, ezért összesen 8 darab 2-nél nagyobb osztatlan szám van: 3, 4, 6, 8, 12, 18, 24, 30.