Feladat: 1033. matematika feladat Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Bencsik I. ,  Biborka T. ,  Bollobás B. ,  Bornes Klára ,  Farkas Henrik ,  Farkas Zoltán ,  Fekete J. ,  Frint Gábor ,  Fritz József ,  Gagyi Pálffy A. ,  Gazsi L. ,  Grüner György ,  Hajna J. ,  Knuth E. ,  Kóta G. ,  Krámli A. ,  Mészáros Kornélia ,  Miklóssy E. ,  Molnár E. ,  Nagypál B. ,  Náray-Szabó G. ,  Nováky A. ,  Pinkert A. ,  Rátkai J. ,  Simonovits M. ,  Sonnevend Gy. ,  Székely J. ,  Tattay Emőke ,  Várady G. ,  Zeke A. 
Füzet: 1961/április, 145 - 148. oldal  PDF  |  MathML 
Témakör(ök): Osztók száma függvény, Feladat
Hivatkozás(ok):Feladatok: 1960/április: 1033. matematika feladat

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.

Tájékozódásul táblázatban összeállítjuk az n=2, 3, 4, ..., 12 számok összes osztóit és ezek alapján osztóik számát. Várható, hogy így szabályszerűségeket ismerünk fel, és azokat felhasználva válaszolhatunk a kérdésekre.

 

n osztók τ   n osztók   τ2   1, 2 2   8 1, 2, 4, 8 4  3 1, 3 2  9 1, 3, 9 3  4 1, 2, 4 3  10 1, 2, 5, 10 4  5 1, 5 2  11 1, 11 2  6 1, 2, 3, 6 4  12  {1,2,3,4,6,12671,72


Itt τ-ra négyféle érték fordult elő: τ=2 adódott n=2, 3, 5, 7, 11 esetében ‐ vagyis a megvizsgált törzsszámokra megegyezésben azzal, hogy törzsszámnak azokat a (természetes) számokat nevezzük, amelyeknek 1-en és önmagán kívül nincs más osztója, vagyis amelyek osztóinak száma τ=2. Eszerint τ=2-re a keresett szám a legkisebb törzsszám: N2=2.
τ=3 adódott n=4 és n=9 esetében; e két szám p2 alakban írható, p=2-vel, ill. p=3-mal. Nyilvánvaló, hogy minden p törzsszám négyzetére τ=3, mert p2 osztói csak az 1, p, p2 számok. Hasonlóan, n=8=23-re τ=4, és bármely p törzsszám köbének 4 osztója van: 1, p, p2, p3. Általában pk osztói: 1, p, p2, p3, ..., pk-1, pk és számuk τ=k+1.
τ=4 adódott továbbá n=6=2⋅3 és n=10=2⋅5 esetében is. Ezek osztóit táblázatokba rendezve látjuk, hogy a második sorbeli osztók az első sorbelieknek
n=6:11,326n=10:1,5210
3-, ill. 5-szörösei; vagy az oszlopokat nézve: a 2-ik oszlopban az első oszlopbeli osztók 2-szerese áll. Nyilvánvaló, hogy minden, két különböző törzsszám szorzataként írható n=p1p2 alakú számnak ugyancsak 4 osztója van:
1p1p2p1p2.
Hasonlóan rendezhetjük el 12=4⋅3=22⋅3 osztóit, valamint tájékozódásunkat a 36=3⋅12 számra kiterjesztve ‐ a 12 osztói mellé csatlakozó 9, 18 és 36 osztókat:
1,3,2,6=2⋅3,4=2212=22⋅3,}12 osztói9¯=32¯,18¯=2⋅32¯,36¯=22⋅32¯}36 osztói
Általában egy p1k1 p2k2 alakú szám osztói a következők:
1,p1,p12,...,p1k1,p2,p1p2,p12p2,...,p1k1⋅p2,p22,p1p22,p12p22,...,p1k1⋅p22,.....................p2k2,p1p2k2,p12p22,...,p1k1p2k2.
(A táblázat minden száma egyenlő az oszlopa fején és a sora elején álló két szám szorzatával.) Ezek száma: τ=(k1+1)(k2+1).
Általánosabban, ha A és B egymáshoz relatív prím számok és A osztói (nagyság szerint rendezve): a1=1, a2, a3, ..., ar=A (számuk τ=r), B osztói: b1=1, b2, b3, ..., bs=B (számuk τ=s), akkor e két felsorolásban az 1-től eltekintve nincs közös szám, így az AB szorzat összes osztóit úgy kapjuk, ha a két felsorolás egy‐egy számát minden lehetséges módon összeszorozzuk:
1,a2,a3,...,arb2,a2b2,a3b2,...,arb2,b3,a2b3,a3b3,...,arb3,(1)............bs,a2bs,a3bs,...,arbs,
és nem nagyon nehéz bizonyítani, hogy ezek egymástól különbözők. Világos, hogy mindezek a számok osztói AB-nek, és más osztó nem lehetséges. Így a sorok és oszlopok számából az osztók száma τ=rs.
Mindezek alapján azt sejtjük (és ezt be is bizonyíthatjuk), hogy ha pl, p1, p2, ..., pr különböző törzsszámok, és k1, k2 ..., kr (pozitív egész) kitevők, akkor az
n=p1k1p2k2...prkr
szám osztóinak száma:
τ(n)=(k1+1)(k2+1)...(kr+1),(2)
vagyis, hogy egy adott szám különböző törzsszámok hatványainak szorzataként felírt alakjából osztóinak számát úgy kapjuk, hogy valamennyi kitevőt 1-gyel növeljük, és az így kapott számokat összeszorozzuk. Háromféle törzstényező fellépése esetén már ,,térbeli'' táblázatra van szükség, pl. n=30=2⋅3⋅5 esetén e táblázat két ,,emelete'':
1,2,510=2⋅53,6=2⋅315=3⋅530=2⋅3⋅5.
Többféle törzstényező fellépése esetén hasonló áttekinthető elrendezés már nem lehetséges, de (1) mintájára ‐ ahol A és B-ben többféle törzstényező is felléphet ‐ ilyenkor is képezhetünk táblázatot pl. n=210=2⋅3⋅5⋅7 esetén A-t 2⋅3-nak, B-t 5⋅7-nek véve a következő táblázat adódik:
1,2,3,6,5,10,15,30,7,14,21,42,35,70,105,210.

Most már (2) eredményünkre támaszkodva olyan természetes számokat, amelyek osztóinak száma egy adott τ szám, úgy képezhetünk, hogy τ-t minden lehetséges módon természetes számok szorzataként írjuk, ideértve a τ=1⋅τ ,,kéttényezős'' szorzatot is, majd a tényezőket 1-gyel csökkentve különböző törzsszámok fölé kitevőknek írjuk, végül az így kapott hatványokat összeszorozzuk.
Mivel az előírt τ értékek közül τ=3 és τ=5 törzsszám, azért ezek szerint 3, ill. 5 osztója csak a p3-1=p2, ill. p5-1=p4 alakú számoknak lehet. Nyilvánvaló, hogy a legkisebb 3, ill. 5 osztóval bíró szám p=2-vel adódik: N3=22=4, N5=24=16.
Ha az előírt τ érték összetett szám, akkor az ennyi osztóval bíró alakok közül a legkisebb számot adót esetenként kell kiválasztanunk.
τ=4=4⋅1=2⋅2-höz két alak lehetséges: p14-1p21-1=p13 és p12-1⋅p22-1=p1p2. Nyilván ismét p1=2-vel, ill. p1=2 és p2=3-mal adódik a legkisebb ilyen szám: 23=8, ill. 2⋅3=6. Az utóbbi a kisebb, eszerint N4=6. ‐ A továbbiakban is p1 helyére mindig 2-t, p2 helyére mindig 3-at írunk.
A τ=6=6⋅1=3⋅2-höz hasonlóan képezhető alakok: p15 és p12p2, a legkisebb számok pedig 32, ill. 22⋅3=12 (nyilvánvaló ugyanis, hogy 32⋅2>22⋅3 (általában, ha p1<p2 és k1>k2, akkor p1k1p2k2<p1k2p2k2, mert innen p1k2p2k2-vel egyszerűsítve a helyes p1k1-k2<p2k1-k2 egyenlőtlenség adódik), tehát N6=12.
Hasonlóan τ=10=10⋅1=5⋅2 esetén a p19 és p14p2 alakokból N10=24⋅3=48, ugyanis kiszámítás nélkül megállapíthatjuk, hogy 24⋅3<29=24⋅25.
A τ=8 szám felbontásai: 8⋅1=4⋅2=2⋅2⋅2, az így adódó p17, p13p2 és p1p2p3 alakokból (ahol p3 gyanánt nyilván a nagyságra nézve 3-ik törzsszám: 5 veendő) N8=23⋅3=24. Itt a p1p2p3 ból adódó legkisebb szám: 30, nagyobb a p13p2 alak legkisebb lehetséges értékénél, 24-nél.
A τ=16 egytényezős felbontásából adódó p115 nagyobb a kéttényezős 8⋅2 és 4⋅4 felbontásokból adódó p17p2 és p13p23 alakok legkisebb lehetséges értékénél, mert p115-7=p18>p2, ill. p115-3=p112>p23. Az utóbbi két alak közül p13p23 kisebb, mert legnagyobb közös osztójukkal, p13p2-vel osztva p14=16>9=p22. ‐ Három tényezőre bontva 16=4⋅2⋅2; és p13p2p3 kisebb p13p23-nél, mert p3=5<9=p22. Viszont a 16=2⋅2⋅2⋅2 négytényezős felbontásból adódó p1p2p3p4 alak legkisebb lehetséges értéke (p4=7-tel) ismét nagyobb p13p2p3-nál, mert p12=4<7=p4. Ezek szerint N16=23⋅3⋅5=120.
Hasonlóan τ=36=3⋅3⋅2⋅2-höz N36=p12p22p3p4=1260, ugyanis a háromtényezős 36=4⋅3⋅3=6⋅3⋅2=9⋅2⋅2 felbontásokhoz tartozó p13p22p32, p15p22p3, p18p2p3 számok nagyobbak N36-nál, és még nagyobbnak adódnak a 9⋅4=6⋅6 felbontásoknak megfelelő alakok legkisebb értékei. ‐ Ugyanígy τ=100=5⋅5⋅2⋅2-ből N100=24⋅34⋅5⋅7=45360, mert pl. a háromtényezős 10⋅5⋅2 felbontásra áttérve p4=7-tel osztunk, viszont p15=32-vel szorzunk. Hasonlóan a többi felbontásokhoz adódó legkisebb 100 osztós számok is nagyobbak N100-nál.
A τ=64=26 érték hattényezős felbontásából adódó p1p2p3p4p5p6 alak legkisebb értéke (p5=11 és p6=13-mal) nagyobb az öttényezős p13p2p3p4p5 alak legkisebb értékénél, mert az utóbbi annak csak p22/p6=4/13 része. Ismét kisebbet kapunk p13p23p3p4-ből, mert p22/p5=9/11<1. Viszont p13p23p33 már nagyobb lenne, mert p32/p4=25/7>1. Így N64=23⋅33⋅5⋅7=7560.
Az egymáshoz hasonló felbontási lehetőségeket nyújtó τ=216=3323 és τ=1000=5323 értékekből előálló alakokból a N216=25⋅32⋅52⋅7⋅11=554400, ill. N1000=24⋅34⋅54⋅7⋅11⋅13=810810000 szám adódik. Itt az N10=24⋅3, N100=(2⋅3)4⋅5⋅7 és N1000=(2⋅3⋅5)4⋅7⋅11⋅13 eredményekben mutatkozó szabályszerűség, valamint az N6=22⋅3 és N36=(2⋅3)2⋅5⋅7 eredmények alapján N216-ra a (2⋅3⋅5)2⋅7⋅11⋅13 szám lett volna várható, viszont a fenti 23(2⋅3⋅5)2⋅7⋅11 szám amannál kisebb, mert 23/13<1.
Bár ezek szerint nincs alapunk általánosításra, az N10, N100 és N1000 szabályszerűsége alapján mégis célszerű N1000000-ra valamennyi lehetőség vizsgálata helyett az
N*=(2⋅3⋅5⋅7⋅11⋅13)4⋅17⋅19⋅23⋅29⋅31⋅37
számból kiindulni, amely az 1000000=5⋅5⋅5⋅5⋅5⋅5⋅2⋅2⋅2⋅2⋅2⋅2 felbontásból adódik. Mégis látjuk, hogy ha egy 5⋅2-s szorzat helyett 10-et írunk, és ezt tekintjük k1+1-nek, ezáltal p1 kitevője 5-tel emelkedik, viszont p12=37 az N*-ból kiesik, vagyis így N*-nak 32/37-szeresét, azaz kisebb számot kapunk. Az így nyert számról könnyű elfogadni, hogy ez a legkisebb 1000000 osztójú szám, mert az 1000000 szám 10-tényezős felbontására áttérve, vagyis p11=31-et is törölve vagy p2 kitevője emelkednék 9-re, vagy p1 kitevője 19-re, ami 35=243-mal, ill. 210=1024-gyel való szorzást jelent, mindenképpen N*-nál nagyobb számra vezet.
Ezt a belátást természetesen még teljes bizonyítássá kellene kifejleszteni, de ez messze vezetne. Eszerint elfogadhatjuk, hogy
N1000000=29(3⋅5⋅7⋅11⋅13)4⋅17⋅19⋅23⋅29⋅31.

Összeállítva Fritz József, Frint Gábor és Grüner György
(Mosonmagyaróvár, Kossuth L. g. III. o. tanulók) különböző indokolású dolgozataiból.

 

Megjegyzések. 1. A (2) képlet bizonyítása megtalálható Faragó László: A számelmélet elemei c. könyvben (Középisk. Szakköri Füzetek, Tankönyvkiadó 1954, 38. o.), továbbá az Erdős Pál‐Surányi János: Válogatott fejezetek a számelméletből c. könyvben (Tankönyvkiadó, 1960, 208. o.).
2. Egy dolgozat a tízes számrendszerben is megadta N1000000-t, emiatt a számítást ellenőriznünk kellett. Bár az ellenőrzés hamar megmutatta, hogy a számítás hibás ‐ a közölt szám ugyanis 3-mal nem volt osztható ‐, mégis kiszámítottuk a helyes értéket:
N1000000=173804636288811640432320000.

Ennek kapcsán megemlítjük, hogy a feladat ötletét egy nem‐európai folyóirat egy húsz évvel ezelőtti számából vettük, amely ‐ idegen forrásra hivatkozva ‐ az 1000000 osztóval bíró számok legkisebbike gyanánt a következőt közölte:
N=(1267650600228229401496703205376)66⋅(847288609443)4,
a következő megjegyzéssel: ,,az első zárójelbeli szám a legkisebb olyan, amelynek 100 osztója van.'' Mivel a zárójelekben 2100, ill. 325 áll, azért N=26600⋅3100, ezért egyrészt osztóinak száma 6601⋅101=666701<1000000, másrészt még az első zárójelbeli alap is 4 jeggyel hosszabb N1000000-nál. ‐ Ebből is az a tanulság, hogy számításainkat ismételten ellenőriznünk kell, és hogy tartózkodjunk a túl merész általánosításoktól.