Egy n szám pozitív osztóinak száma miért ennyi?

Az osztókat a prímtényezők kombinációjából barkácsolhatod össze. Mindegyik prímtényezőből kiválasztasz valamennyit, összeszorzod őket és az egy osztója lesz az számnak.

n bármelyik osztóját így megkapod: p1^i * p2^j * ... pn^z

És ugye i fut 0-tól x1-ig, j fut 0-tól x2-ig stb. stb.

Biztos ismered az ilyen kombinatorikai feladatokat, hogy hány számot lehet alkotni az adott számjegyekből.

Lényegében itt is erről van szó.

Csak mindegyik "számjegy" (kitevő) 0, 1, 2, ... xn lehet.

Tehát a 0 miatt van a "+1"

Példa 12 = 2^2 * 3^1

A 2-es kitevője lehet 0, 1, 2 és a 3-as kitevője lehet 0, 1

tehát 3*2 féle osztót lehet "összebarkácsolni".

2^0 * 3^0 = 1

2^0 * 3^1 = 3

2^1 * 3^0 = 2

2^1 * 3^1 = 6

2^2 * 3^0 = 4

2^2 * 3^1 = 12

Valami ilyesmi, remélem érthetően sikerült leírnom.

Kombinatorikával, azon belül variációszámítással lehet indokolni;

vegyük például a 21.359.390.325.000 számot. Ennek prímtényezős alakja 2^3 * 3^1 * 5^5 * 7^3 * 13^2 * 17^3. Most készítsünk egy táblázatot, ahol az első sorban a prímek foglalnak helyet:

| 2 | 3 | 5 | 7 | 13 | 17 |

A második sorba írjuk azt, hogy az adott prímszámból mennyit akarunk kiválasztani (értelemszerűen 0-tól addig, amennyi van belőlük), például legyen:

| 1 | 1 | 3 | 0 | 2 | 1 |, majd ezeket a kiválasztottakat összeszorozzuk, így kapjuk a 2*3*5*5*5*13*13*17=2.154.750 számot osztónak. Látható, hogy minden ilyen számsorhoz tartozik pontosan 1 darab szám, és a számelmélet alaptétele miatt biztos, hogy két különböző számsorból kiolvasva a számot, azok különbözőek lesznek.

Fordítva is meg kell nézni, tehát ha van egy számunk, ami osztója az eredetinek, akkor ahhoz egyértelműen tartozik-e számsor. Ennek belátását rád bízom, nem túl bonyolult.

Ezzel a módszerrel tudtunk adni egy kölcsönösen egyértelmű leképezést, tehát minden számsorhoz pontosan 1 szám tartozik, és minden számhoz pontosan 1 számsor. Ez azért jó, mert ha az egyiket meg tudjuk számolni, akkor azzal a másik számosságát is megkapjuk. Már csak az a kérdés, hogy hogyan jön ki, ehhez hívjuk a variációszámítást segítségül.

A 2-es oszlopába a 0;1;2;3 számok valamelyike írható, tehát oda 4-féle szám kerülhet. A 3-as oszlopába 0 és 1 mehet, ez két lehetőség. És így tovább, végül a tanultak miatt ezeket össze kell szorozni, így kapjuk azt, hogy 4*2*6*4*3*4=2304 számsor kreálható a fenti táblázat segítségével, tehát ennyi osztó van.

Ezzel pont azt kaptuk, amit te írtál.

Igazából a 0 miatt kell a kitevőket 1-gyel növelni, ez a titok.