# Numero automorfo

In matematica si dice numero automorfo o anche intero automorfo un intero positivo $n$ in una data base $b$ il cui quadrato ha per cifre meno significative ("termina per") l'intero stesso.

## Esempi

* In base decimale:
       $5^{2}=2{\mathit {5}};$
       $76^{2}=57{\mathit {76}};$
       $890625^{2}=793212{\mathit {890625}}.$
* In base 6:
       $3^{2}=1{\mathit {3}};$
       $4^{2}=1{\mathit {4}}.$

## In base arbitraria

Dalla definizione segue che, data una base $b$, un intero positivo $n$ di $k$ cifre è un numero automorfo se
    $n^{2}=cb^{k}+n$
in cui $cb^{k}$ è un numero che termina con $k$ zeri, sui quali l'addizione inserisce $n$.
I numeri automorfi possono essere trovati dalla loro definizione risolvendo negli interi l'equazione
    $n^{2}-n=n(n-1)=cb^{k}$
equivalente alla congruenza
    $n(n-1)\equiv 0{\pmod {cb^{k}}}.$

### Esistenza e numero di interi automorfi

La scrittura in forma di congruenza permette di notare che 0 e 1 sono soluzioni indipendentemente dalla base. Per cercare soluzioni oltre a queste due, si può notare che la soluzione $n$ non può contenere l'intera base $b$ (né suoi multipli) perché terminerebbe per 0 e $n^{2}$ terminerebbe con un numero di 0 doppio e dunque non potrebbe essere uguale a $n$. Dunque i fattori di $b^{k}$devono essere ripartiti tra $n$ e $n-1$. Poiché due numeri consecutivi non possono avere fattori in comune (la loro differenza a sua volta conterrebbe tali fattori e dunque non potrebbe essere 1), i fattori di $c$ e $b^{k}$devono essere ripartiti in modo che $n$ e $n-1$ siano relativamente primi. Questo è possibile solo se la base $b$ è scomponibile in almeno due fattori diversi. Quindi non esistono numeri automorfi (diversi da quelli banali 0 e 1, che esistono in ogni base) nelle basi prime o potenze di un unico primo. Siano dunque $c=c_{1}c_{2}$ e $b=b_{1}b_{2}$, dove i prodotti $c_{1}b_{1}$e $c_{2}b_{2}$ sono relativamente primi. Deve essere $n=c_{1}b_{1}^{k}$ (che è il numero automorfo cercato) e $n-1=c_{2}b_{2}^{k}$. Si ha così l'identità di Bézout:
    $c_{1}b_{1}^{k}-c_{2}b_{2}^{k}=1.$
Analogamente si ottiene il numero automorfo $c_{2}b_{2}^{k}$ dall'identità
    $c_{2}b_{2}^{k}-c_{1}b_{1}^{k}=1.$
Ciascuna di queste identità, in cui $b_{1}$e $b_{2}$ sono note e $c_{1}$e $c_{2}$ sono incognite, ammette una soluzione unica (modulo $b_{2}^{k}$ per $c_{1}$ e modulo $b_{1}^{k}$ per $c_{2}$) perché $b_{1}$e $b_{2}$ (e quindi $b_{1}^{k}$e $b_{2}^{k}$) sono coprimi. Le identità sono risolvibili con l'algoritmo di Euclide. Quindi, per ogni numero di cifre $k$, esistono due automorfi (dati da $n=c_{1}b_{1}^{k}$ e $n=c_{2}b_{2}^{k}$) per ogni modo di ripartire la base in due gruppi primi tra loro di fattori. Il prodotto $c=c_{1}c_{2}$ dà la parte iniziale del quadrato del numero automorfo, quadrato che termina in $n$.

#### Esempio

In base 30 i fattori della base (2, 3 e 5) possono essere ripartiti in sei modi: $b_{1}=2$ e $b_{2}=3\times 5=15$, $b_{1}=3$ e $b_{2}=2\times 5=10$, $b_{1}=5$ e $b_{2}=2\times 3=6$ e le stesse tre coppie a fattori invertiti. Si ottengono gli automorfi di una cifra 6, 10, 15, 16, 21 e 25 (espressi in notazione decimale), di due cifre 100, 225, 325, 576, 676 e 801, e così via. Per esempio, $10\times 10=100\equiv 10{\pmod {30}}.$

### Proprietà
#### Somma di coppie di autovalori

Si dimostra inoltre che la somma di ogni coppia di automorfi così ottenuta è $b^{k}+1$. Infatti, dette $c_{1}^{*}$ e $c_{2}^{*}$ le soluzioni della prima identità di Bézout, si ha
    $c_{1}^{*}b_{1}^{k}-c_{2}^{*}b_{2}^{k}=1.$
La seconda identità
    $c_{2}b_{2}^{k}-c_{1}b_{1}^{k}=1$
può essere riscritta come
    $(-c_{1})b_{1}^{k}-(-c_{2})b_{2}^{k}=1,$
dalla quale si nota per paragone con la prima identità di Bézout (e ricordando che le soluzioni del coefficiente di $b_{2}^{k}$ sono note modulo $b_{1}^{k}$) che $-c_{2}\equiv c_{2}^{*}{\pmod {b_{1}^{k}}}.$ Poiché si cercano soluzioni di $k$ cifre, il loro valore deve essere compreso tra 0 e $b_{1}^{k}$, e si ha
    $c_{2}=-c_{2}^{*}+b_{1}^{k}.$
Dunque la prima identità dà il primo automorfo $c_{1}^{*}b_{1}^{k}$, mentre la seconda dà il secondo automorfo della coppia
    $c_{2}b_{2}^{k}=-c_{2}^{*}b_{2}^{k}+b_{1}^{k}b_{2}^{k}.$
La loro somma è
    $c_{1}^{*}b_{1}^{k}+c_{2}b_{2}^{k}=c_{1}^{*}b_{1}^{k}-c_{2}^{*}b_{2}^{k}+b_{1}^{k}b_{2}^{k}=1+b^{k},$
dove si è usata la prima identità di Bézout e $b=b_{1}b_{2}.$

#### Residui modulo fattori della base

Considerando
    $c_{1}b_{1}^{k}-c_{2}b_{2}^{k}=1{\pmod {b_{2}^{k}}},$
si ottiene
    $c_{1}b_{1}^{k}\equiv 1{\pmod {b_{2}^{k}}}.$
Inoltre
    $c_{1}b_{1}^{k}\equiv 0{\pmod {b_{1}^{k}}}.$
Analogamente, dalla seconda identità di Bézout, si ha
    $c_{2}b_{2}^{k}\equiv 1{\pmod {b_{1}^{k}}}$
e
    $c_{2}b_{2}^{k}\equiv 0{\pmod {b_{2}^{k}}}.$
Quindi un numero automorfo è congruente a 0 e 1 modulo i due gruppi di fattori della base nei quali essa è suddivisa.

#### Costruzione di un automorfo in base quadrato della base di un altro automorfo

A partire da un numero automorfo $n$ di $k$ cifre, si costruisce un numero automorfo di $2k$ cifre mediante la formula:$n'\equiv 3n^{2}-2n^{3}{\pmod {b^{2k}}}.$
Dimostrazione: se $n'$ è un automorfo di $2k$ cifre, è possibile trovare un intero $j$ tale per cui $n'(n'-1)=jb^{2k}$. Sostituendo l'espressione di $n'$ e fattorizzando si ottiene $n^{2}(n-1)^{2}(4n^{2}-4n-3)=jb^{2k}$. Poiché per ipotesi $n$ è un automorfo di $k$ cifre, esiste un intero $i$ tale per cui $n(n-1)=ib^{k}$. Sostituendo nella precedente equazione si ottiene $i^{2}b^{2k}(4n^{2}-4n-3)=jb^{2k}$ e, semplificando $b^{2k}$, si giunge a $j=i^{2}(4n^{2}-4n-3)$. Dunque esiste $j$ tale per cui $n'(n'-1)=jb^{2k}$e $n'$ è automorfo.

## In base decimale

Poiché la base 10 può essere suddivisa solo in $2\times 5=10$, per ogni numero $k$ di cifre esistono esattamente due numeri automorfi di $k$ cifre (5 e 6 per $k=1$ (una cifra); 25 e 76 per $k=2$; 376 e 625 per $k=3$; ...). Uno di essi gode delle proprietà $n\equiv 0{\pmod {2^{k}}}$ e $n\equiv 1{\pmod {5^{k}}}$; l'altro delle proprietà $n\equiv 0{\pmod {5^{k}}}$ e $n\equiv 1{\pmod {2^{k}}}$. La somma di questi due numeri è $10^{k}+1$ (5+6=11; 25+76=101; 376+625=1001; ...).
Partendo da 76, che è un automorfo di due cifre, si può calcolare un automorfo di quattro cifre da $n'\equiv 3\times 76^{2}-2\times 76^{3}{\pmod {10^{4}}}$. Si ha $n'\equiv -860624\equiv 870000-860624=9376{\pmod {10^{2}}}.$
La seguente sequenza di 1000 cifre consente di individuare un numero automorfo di $k$ cifre per $k\leq 1000.$
12781254001336900860348890843640238757659368219796\ 26181917833520492704199324875237825867148278905344\ 89744014261231703569954841949944461060814620725403\ 65599982715883560350493277955407419618492809520937\ 53026852390937562839148571612367351970609224242398\ 77700757495578727155976741345899753769551586271888\ 79415163075696688163521550488982717043785080284340\ 84412644126821848514157729916034497017892335796684\ 99144738956600193254582767800061832985442623282725\ 75561107331606970158649842222912554857298793371478\ 66323172405515756102352543994999345608083801190741\ 53006005605574481870969278509977591805007541642852\ 77081620113502468060581632761716767652609375280568\ 44214486193960499834472806721906670417240094234466\ 19781242669078753594461669850806463613716638404902\ 92193418819095816595244778618461409128782984384317\ 03248173428886572737663146519104988029447960814673\ 76050395719689371467180137561905546299681476426390\ 39530073191081698029385098900621665095808638110005\ 57423423230896109004106619977392256259918212890625
Qui il segno backslash (\) segnala che la scrittura decimale continua nella linea successiva. Basta prendere la sequenza delle ultime $k$ cifre, e l'altro numero si ottiene sottraendo da $10^{k}+1$ il numero suddetto.

### Tavole dei numeri automorfi in base decimale

| n | n$^2$ |
| 5 | 25 |
| 25 | 625 |
| 625 | 390625 |
| 90625 | 8212890625 |
| 890625 | 793212890625 |
| 2890625 | 8355712890625 |
| 12890625 | 166168212890625 |
| 212890625 | 45322418212890625 |
| 8212890625 | 67451572418212890625 |
| 18212890625 | 331709384918212890625 |
| 918212890625 | 843114912509918212890625 |
| 9918212890625 | 98370946943759918212890625 |
| 59918212890625 | 3590192236006259918212890625 |
| 259918212890625 | 67557477392256259918212890625 |
| 6259918212890625 | 39186576032079756259918212890625 |
| 56259918212890625 | 3165178397321142256259918212890625 |
| 256259918212890625 | 65669145682477392256259918212890625 |
| 2256259918212890625 | 5090708818534039892256259918212890625 |
| 92256259918212890625 | 8511217494096854352392256259918212890625 |
| 392256259918212890625 | 153864973445024588727392256259918212890625 |
| 7392256259918212890625 | 54645452612300005057477392256259918212890625 |
| 77392256259918212890625 | 5989561329000849809744977392256259918212890625 |
| 977392256259918212890625 | 955295622596853633012869977392256259918212890625 |
| 9977392256259918212890625 | 99548356235275381465044119977392256259918212890625 |
| 19977392256259918212890625 | 399096201360473745722856619977392256259918212890625 |
| 619977392256259918212890625 | 384371966908872375601191606619977392256259918212890625 |
| 6619977392256259918212890625 | 43824100673983991394155879106619977392256259918212890625 |
| 106619977392256259918212890625 | 11367819579125235975036734004106619977392256259918212890625 |
| 4106619977392256259918212890625 | 16864327638717175315320739859004106619977392256259918212890625 |
| 9004106619977392256259918212890625 | 81073936023920699329853843152771109004106619977392256259918212890625 |
| 109004106619977392256259918212890625 | 11881895260019399150581837485730896109004106619977392256259918212890625 |
| 6109004106619977392256259918212890625 | 37319931174699748106225700856040418396109004106619977392256259918212890625 |
| 96109004106619977392256259918212890625 | 9236940670366295678712352486134360730896109004106619977392256259918212890625 |
| 896109004106619977392256259918212890625 | 803011347240958259506322368355274985730896109004106619977392256259918212890625 |
| 30896109004106619977392256259918212890625 | 954569551593638156903041697963448048423230896109004106619977392256259918212890625 |
| 230896109004106619977392256259918212890625 | 53313013153236286147859944201930733204673230896109004106619977392256259918212890625 |
| 3230896109004106619977392256259918212890625 | 10438689667177876006012213481761440010548423230896109004106619977392256259918212890625 |
| 23230896109004106619977392256259918212890625 | 539674534027342140805107903732158168526173423230896109004106619977392256259918212890625 |
| n | n$^2$ |
| 6 | 36 |
| 76 | 5776 |
| 376 | 141376 |
| 9376 | 87909376 |
| 109376 | 11963109376 |
| 7109376 | 50543227109376 |
| 87109376 | 7588043387109376 |
| 787109376 | 619541169787109376 |
| 1787109376 | 3193759921787109376 |
| 81787109376 | 6689131260081787109376 |
| 40081787109376 | 1606549657881340081787109376 |
| 740081787109376 | 547721051611007740081787109376 |
| 3740081787109376 | 13988211774267263740081787109376 |
| 43740081787109376 | 1913194754743017343740081787109376 |
| 743740081787109376 | 553149309256696143743740081787109376 |
| 7743740081787109376 | 59965510454276227407743740081787109376 |
| 607743740081787109376 | 369352453608598807478607743740081787109376 |
| 2607743740081787109376 | 6800327413935747244982607743740081787109376 |
| 22607743740081787109376 | 511110077017207231620022607743740081787109376 |
| 80022607743740081787109376 | 6403617750108490103144731780022607743740081787109376 |
| 380022607743740081787109376 | 144417182396352539175410357380022607743740081787109376 |
| 3380022607743740081787109376 | 11424552828858793029898066613380022607743740081787109376 |
| 893380022607743740081787109376 | 798127864794612716138610952755893380022607743740081787109376 |
| 5893380022607743740081787109376 | 34731928090872050116956482046515893380022607743740081787109376 |
| 995893380022607743740081787109376 | 991803624372854204655478894958610995893380022607743740081787109376 |
| 90995893380022607743740081787109376 | 8280252612028442248077870200574646290995893380022607743740081787109376 |
| 890995893380022607743740081787109376 | 793873682020064614638062001059949647890995893380022607743740081787109376 |
| 3890995893380022607743740081787109376 | 15139849042300200261100502491782605903890995893380022607743740081787109376 |
| 103890995893380022607743740081787109376 | 10793339027718304721809848518849204481103890995893380022607743740081787109376 |
| 9103890995893380022607743740081787109376 | 82880831265108558711661197169991017173249103890995893380022607743740081787109376 |
| 69103890995893380022607743740081787109376 | 4775347750772314161424590445979805470298369103890995893380022607743740081787109376 |
| 769103890995893380022607743740081787109376 | 591520795145023046193075431682094307423424769103890995893380022607743740081787109376 |
| 6769103890995893380022607743740081787109376 | 45820767487095743606464368356563075752735936769103890995893380022607743740081787109376 |
| 76769103890995893380022607743740081787109376 | 5893495312226520816809629452480174525948048576769103890995893380022607743740081787109376 |