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 ulteriori soluzioni, si può notare che $b^{k}$ (né suoi multipli) può essere assegnato interamente a $n$ o $n-1$ perché si avrebbe $n=b^{k}$ o $n=1+b^{k}$ e in entrambi i casi $n$ avrebbe non $k$ ma $k+1$ cifre.

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}$. Per sostituzione della prima nella seconda si ha 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}$), ricavabile con l'algoritmo di Euclide, perché $b_{1}$e $b_{2}$ (e quindi $b_{1}^{k}$e $b_{2}^{k}$) sono coprimi. 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 l'equazione

$c_{1}b_{1}^{k}-c_{2}b_{2}^{k}=1{\pmod {b_{2}^{k}}},$

si ottiene la congruenza

$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 hanno

$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	n2
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	n2
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

Collegamenti esterni

• (EN) Eric W. Weisstein, Automorphic Number, su MathWorld, Wolfram Research.