Feladat: Pontversenyen kívüli P.89 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Bacsó G. ,  Bara T. ,  Ferró J. ,  Katona E. ,  Reviczky János ,  Szendrei Ágnes 
Füzet: 1971/november, 152 - 153. oldal  PDF file
Témakör(ök): Algoritmikus eljárások, Prímszámok, Természetes számok, Pontversenyen kívüli probléma
Hivatkozás(ok):Feladatok: 1971/január: Pontversenyen kívüli P.89

Mutassuk meg, hogy nincs olyan természetes szám, amelyik 10-zel nagyobb volna a nála kisebb, hozzá relatív prím természetes számok számánál.

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.

Jelöljük Dn-nel az n-nél nem nagyobb természetes számok közül azoknak a halmazát, amelyeknek van 1-nél nagyobb közös osztójuk n-nel, és jelöljük d(n)-nel a Dn halmaz elemeinek a számát. Feladatunk állítása azt jelenti, hogy nincs olyan n természetes szám, melyre d(n) értéke 10 volna. Ezt fogjuk bizonyítani, és rögtön feltesszük, hogy n>1, hiszen d(1)=0.
Ha n prímszám, vagy egy prímszám hatványa, azaz n=pk, ahol p prímszám, és k1, akkor

Dn={p,2p,3p,...,pk-1p},
tehát d(n)=pk-1, ami ugyancsak prímszámhatvány ‐ vagy 1. Ilyen n-ekre tehát d(n) értéke nem lehet 10.
Minden más természetes szám felbontható két egymáshoz prím, 1-nél nagyobb természetes szám szorzatára. Legyen n=ab az n-nek ilyen ‐ de különben tetszőleges ‐ felbontása. Ekkor a
Dn(a)=a,2a,...,ba,Dn(b)=b,2b,...,ab
halmazoknak egyetlen közös elemük az n=ab szám, hiszen ha ja=lb, ahol 1jb, 1la, akkor a minden osztója l-nek is osztója, és b minden osztója j-nek is osztója, vagyis csak j=b és l=a lehet. A Dn(a), Dn(b) halmazok egyesítésében tehát (a+b-1) szám van, és ezek mind elemei Dn-nek is. Emiatt
d(n)a+b-1.

Itt akkor és csakis akkor lehet az egyenlőség jele érvényes, ha a is és b is, prímszám, hiszen a-nak és b-nek 1-nél nagyobb, de a-nál, illetve b-nél kisebb osztói elemei Dn-nek, de nincsenek benne a Dn(a), Dn(b) halmazokban. Ha viszont a is, b is prímszámok, akkor Dn minden eleme vagy a-val, vagy b-vel osztható, tehát vagy Dn(a)-nak, vagy Dn(b)-nek eleme.
Ha itt a és b prímszámok, akkor ezek szerint d(n)=10 csak akkor lehetne, ha a+b=11 volna, viszont a 11-et nem lehet két prímszám összegeként előállítani.
Ezek szerint már csak azokat az n számokat kell vizsgálni, amelyek n=ab alakúak, ahol a és b relatív prímek, 1-nél nagyobbak, nem mind a kettő prímszám, és a+b<11. Csak két ilyen szám van: a 34 és a 45, ezekre
D12={2,3,4,6,8,9,10,12},D20={2,4,5,6,8,10,12,14,15,16,18,20},
tehát d(12)=8, d(20)=12, így d(n) értéke ezekre sem 10. Feladatunk állítását ezzel bebizonyítottuk.
 

Reviczky János (Budapest, I. István Gimn.)