Hány automorf szám létezik?

Annyit biztosra lehet mondani, hogy az automorf számok végződései mind ugyanazok;

-egyjegyű automorf szám: 6, mivel 6*6=36 (ezen kívül még van a 0 és az 1, azokkal most nem foglalkozom).

-kétjegyű automorf szám: 76, mivel 76*76=5776

-háromjegyű automorf szám: 376, mivel 376*376=141376

-négyjegyű automorf szám: 9376, mivel 9376*9376=87909376

-ötjegyű automorf szám: 09376, mivel 09376*09376=87909376 (ez nem igazi ötjegyű automorf szám, de ugródeszkaként tudjuk használni)

-hatjegyű automorf szám: 109376, mivel 109376*109376=11963109376

-hétjegyű automorf szám: 7109376, mivel 7109376*7109376=50543227109376

-nyolcjegyű automorf szám: 87109376, mivel 87109376*87109376=7588043387109376

stb.

Ezek alapján én úgy sejtem, hogy végtelen sok van. Lehet, hogy bizonyítani is fogom tudni egyszer, de nem most.

Azt hiszem, megvan; teljes indukcióval fogjuk belátni azt, hogy nem létezik legnagyobb automorf szám (tetszőleges jegyű automorf szám képezhető).

Azt tudjuk, hogy

36 kongruens 6 mod(10).

Tegyük fel, hogy az n-edik jegyig találunk automorf számot (lásd fent), ezt jelölje x, erre a számra igaz, hogy

x^2 kongruens x mod(10^n), vagy másként:

x^2-x kongruens 0 mod(10^n)

Az x számról még azt tudjuk, hogy utolsó számjegye 6, ezt a későbbiekben fel fogjuk használni.

Most nézzük az (n+1) jegyű számot, ennek első számjegye legyen a (ami speciális esetben lehet 0 is, mint például a 09376 esetén láthattuk), ekkor ennek kell igaznak lennie:

(ax)^2 kogruens ax mod(10^(n+1)), ahol ax most nem szorzást jelöl, hanem egy (n+1)-jegyű számot.

Ez az (n+1)-jegyű szám felírható összegként: ax = a*10^n+x, tehát

(a*10^n+x)^2 kongruens a*10^n+x mod(10^(n+1)), kibontjuk a zárójelet:

a^2*10^(2n) + 2*x*a*10^n + x^2 kongruens a*10^n+x mod(10^(n+1))

A bal oldali összeg első tagja biztosan osztható 10^(n+1)-gyel, így az kihúzható, így marad

2*x*a*10^n + x^2 kongruens a*10^n+x mod(10^(n+1))

Vonjunk ki mindkét oldalból (a*10^n+x)-et, majd emeljünk ki a*10^n tényezőt:

a*10^n*(2x-1) + x^2-x kongruens 0 mod(10^(n+1))

A teljes kongruenciát el tudjuk osztani 10^n-nel; a bal oldali összeg első tagja a 10^n tényező miatt, x^2-x pedig az indukciós feltevés miatt osztható (10^n)-nel, így ezt kapjuk:

a*(2x-1) + (x^2-x)/10^n kongruens 0 mod(10)

Tehát már csak az a kérdés, hogy a bal oldal osztható-e 10-zel. Az (x^2-x)/10^n tört utolsó számjegye 0-9-ig bármi lehet. Nézzük meg, hogy az első tag utolsó számjegye mi lehet. Mint mondtuk, x utolsó számjegye 6, és mivel mod(10)-ben vizsgálódunk, ezért x-ből csak ez kell nekünk. Ez azt jelenti, hogy az

a*(2x-1) szorzat utolsó számjegye = a*(2*6-1) utolsó számjegye = a*11 utolsó számjegye = az aa szám utolsó számjegye = a, ami szintén 0-9-ig bármi lehet, csak annak függvényében kell megválasztanunk, hogy mi az (x^2-x)/10^n utolsó számjegye. Az összegnek 10-zel oszthatóval kell lennie, így az összeg vagy 0 lesz (0+0=0), vagy 10.

Ez tetszőleges n-re működni fog, tehát akármennyi jegyű automorf szám kreálható. Sőt, a levezetésből még azt is meg tudjuk mondani, hogy n-jegyű automorf számból pontosan egy létezik, itt természetesen a szükséges 0-s pótlással számolva.

Egy esetben lehet probléma; előfordulhat, hogy több 0-val kell kiegészítenünk a számot, például a tizenegyjegyű 81787109376 automorf számot a 081787109376 és 0087187109376 számok követik, ami után a 40081787109376 következik. Ha végtelen sokszor lehet az 'a' értéke 0, akkor az értékes jegyek száma nem bővülne. Ebben az esetben viszont x=x^2-nek kellene teljesülnie, ami csak az x=0 és x=1 számok esetén igaz, így a 6-ra végződő automorf számokat ez nem veszélyezteti.

Ezzel tehát beláttuk, hogy végtelen sok 6-ra végződő automorf szám létezik.

Ráadásul ezzel így képletet is tudtunk konstruálni az automorf számok kereséséhez! Például vegyük a 40081787109376 automorf számot. Emeljük négyzetre, vonjuk ki az eredeti számot, majd osszuk el 10^14-nel, ekkor ezt kapjuk: 16065496578813. Ez 3-ra végződik, tehát a fenti levezetésben a értékének 7-et kell választanunk, tehát a 740081787109376-ot kapjuk.

Ellenőrzés: 740081787109376^2 = 547721051611007740081787109376, tehát jól számoltunk. Ahelyett, hogy 0-9-es végődésekkel végignéztük volna az összes lehetőséget.