Scopo di questo breve articolo di Alessandro Zaccagnini è parlare di una delle operazioni matematiche di base, e cioè la moltiplicazione.

[originariamente pubblicato il 19 gennaio 2020]

In questo articolo non si parlerà di algoritmi, che certamente meriterebbero una trattazione a parte: ve ne sono di molto belli, dalle piccole variazioni sul tema della “moltiplicazione in colonna” che tutti abbiamo imparato alle scuole elementari (scuola primaria), a quelli che usano idee raffinate come la Trasformata di Fourier discreta, e che servono a moltiplicare esattamente dei numeri interi molto grandi facendo relativamente poca fatica.

Cominceremo invece facendo un passo indietro, cioè dall’addizione, e confrontando poi le proprietà formali delle due operazioni, che sembrano molto simili fra loro. Ma non appena cominciamo a giocare facendo qualche disegno, “grafo” in termini tecnici, scopriamo che le due operazioni sono radicalmente diverse, con conseguenze inattese (su crittografia ed altro).

L’addizione

L’ambiente naturale dove introdurre l’addizione è \({\mathbb{N}}= \{0\), 1, 2, 3, \(\dots \}\). Ne ricordiamo le piú importanti proprietà formali: l’addizione è commutativa e associativa, e ha un elemento neutro, cioè \(0\).

Possiamo ordinare gli elementi di \({\mathbb{N}}\) dicendo che \(n < n + 1\), e poi estendendo questa relazione per transitività. Per i nostri scopi, è piú utile, per quanto equivalente, dire che \(a \le b\) se l’equazione \(a + x = b\) ha una soluzione in \({\mathbb{N}}\). Associamo a questa relazione d’ordine un grafo disegnando una freccia che va da un intero piú piccolo ad un intero piú grande:

Qui non indichiamo la freccia che parte da 2 ed arriva a 5, per esempio, perché la relazione passa attraverso (“transita” per) i valori intermedi 3 e 4, e quindi non è necessario aggiungere altre frecce a quelle già disegnate. In altre parole, in tutti i nostri disegni indicheremo solo i successori immediati dell’intero che stiamo considerando. L’uso del plurale sarà giustificato quando vedremo i grafi relativi alla moltiplicazione: in questo secondo caso, infatti, ogni intero ha infiniti successori immediati!

La transitività della relazione può essere espressa anche mediante la risolubilità delle equazioni che abbiamo visto sopra: dato che le equazioni \(2 + x = 3\) e \(3 + y = 5\) hanno soluzione in \({\mathbb{N}}\), allora anche l’equazione \(2 + z = 5\) ha soluzione in \({\mathbb{N}}\), e naturalmente \(z = x + y\), perché \(2 + x + y = 3 + y = 5\). Non a caso, la relazione d’ordine cosí trovata si dice lineare, o anche totale. Notiamo, a futura memoria, che è sufficiente un solo colore per le nostre frecce.

La moltiplicazione

Ora proviamo a ripetere, per quanto possibile, quello che abbiamo fatto per l’addizione anche con la moltiplicazione. L’ambiente naturale dove introdurre la moltiplicazione è \({\mathbb{N}}^* = \{1\), 2, 3, 4, \(\dots \}\). Ne ricordiamo le piú importanti proprietà formali, che sono poi le stesse dell’addizione: la moltiplicazione è commutativa e associativa, e ha un elemento neutro, cioè \(1\).

In analogia con quanto abbiamo fatto per l’addizione, diremo che \(a\) precede \(b\) se l’equazione \(a x = b\) ha soluzione in \({\mathbb{N}}^*\), cioè se \(b\) è divisibile per \(a\). Anche questa relazione è transitiva, per lo stesso motivo visto sopra e non ci soffermiamo su questo aspetto.

Non ci resta che determinarne il grafo. E qui ci togliamo qualche soddisfazione …Sistemiamo il numero 1 all’estremità sinistra del nostro disegno, e il numero 2 immediatamente alla sua destra con una freccia da sinistra a destra, dal numero che precede verso il seguente. Dove dobbiamo mettere il numero 3? Senz’altro a destra di 1, ma rispetto a 2? In questo caso, dobbiamo dire che 2 e 3 non si possono confrontare (2 non divide 3 e 3 non divide 2). Accantoniamo momentaneamente il problema, e disegniamo solo le potenze di 2, con una freccia rossa da una potenza di 2 alla successiva. Anche qui, non indicheremo frecce superflue quando la relazione transita attraverso valori intermedi. Otteniamo un disegno come questo:

Otterremmo lo stesso disegno considerando le potenze di un qualsiasi altro numero primo: per esempio

Da qui in avanti, associamo al numero primo 3 il colore blu, al numero 5 il colore verde e al 7 il colore nero. In generale, disegneremo una freccia rossa da \(a\) a \(b\) se \(b = 2 a\), blu se \(b = 3 a\) e cosí via, sempre rispettando la regola di disegnare solo le frecce che collegano un intero ad un suo successore immediato.

Il nostro primo obiettivo è costruire un grafo in cui compaiono tutti questi valori, oltre ai numeri interi che si ottengono moltiplicando questi fra loro. Procediamo gradualmente, facendo un passo alla volta.

Per poter inserire 3 e le sue potenze nel grafo ottenuto al primo passo abbiamo bisogno di una seconda dimensione. Possiamo “saldare” i due grafi in questo modo:

Il primo numero non ancora utilizzato è 5, che, come prima, non è confrontabile né con 2 né con 3. Dunque lo lasciamo momentaneamente da parte, e ci occupiamo di sistemare il numero 6: per le nostre convenzioni, si deve trovare a destra di 2 e di 3, e deve essere raggiunto da una freccia rossa che parte da 3 e da una freccia blu che parte da 2; quindi possiamo collocarlo cosí:

Lasciando sempre da parte i numeri interi che contengono fattori primi piú grandi di 3 (in termini algebrici, considerando solo il semigruppo generato da 2 e da 3) e collocando i numeri seguendo sempre la stessa regola, troviamo una figura fatta cosí:

Nella colonna all’estrema sinistra abbiamo i numeri con 0 fattori primi (il solo numero 1), poi i numeri con un fattore primo (scelto fra 2 e 3), poi quelli con un totale di due fattori primi, e cosí via. Quindi nella quarta colonna troviamo \(2^3\), \(2^2 \cdot 3\), \(2 \cdot 3^2\) e \(3^3\), mentre nella quinta troviamo \(2^4\), \(2^3 \cdot 3\), \(2^2 \cdot 3^2\), \(2 \cdot 3^3\) e \(3^4\). Osserviamo che ci sono piú modi per andare da 1 a 12 (in generale, da \(a\) a \(12 a\)), per fare un esempio, ma dovremo comunque seguire due frecce rosse e una blu, perché la scomposizione in fattori primi di \(12 = 2^2 \cdot 3\) è unica, a parte l’ordine dei fattori.

Questo grafo sta a malapena sul piano, senza intersezioni, collocando in ogni colonna i numeri come appena detto, e cioè mettendo in basso la corrispondente potenza di 2 e poi sostituendo un fattore 2 con un fattore 3 fino a trovare, nella riga piú in alto, la potenza di 3. In pratica, nella colonna \((n + 1)\)-esima valutiamo tutti i monomi di grado \(n\) in \(x\) ed \(y\) (dove \(x = 2\) ed \(y = 3\)), disposti ordinatamente secondo le potenze decrescenti di \(x\).

Cosa succede quando aggiungiamo 5, le sue potenze e tutti i numeri che sono prodotti di potenze di 2, 3, 5? Cominciamo a sistemare le potenze di 5, ricordando che 5 e le sue potenze non sono confrontabili con nessuno degli interi già presenti sul grafo, a parte ovviamente il numero 1:

Il numero 10 e il numero 15 dovranno essere inseriti nella terza colonna da sinistra, e saranno raggiunti dalle frecce colorate che spettano loro, secondo le nostre convenzioni:

A questo punto il grafo comincia irrimediabilmente ad auto-intersecarsi. Nella quarta colonna dovremmo ancora inserire i numeri 20, 30, 45, 50, 75.

Riduciamo la larghezza verso destra, e aumentiamo l’altezza collocando al loro posto anche le potenze di 7:

Ci possiamo fermare qui, perché è chiaro come si prosegue: per ogni numero primo \(p\) c’è una riga con le sue potenze, che poi devono essere collegate con i loro altri multipli come abbiamo fatto sopra. Il “vero” grafo è illimitato verso destra e anche verso l’alto, perché esistono infiniti numeri primi.

Conclusioni e commenti finali

Cerchiamo ora di trarre qualche conclusione dal nostro lavoro. Il punto essenziale è che la moltiplicazione è un’operazione molto “rimescolante” e quindi interi che sono “prossimi” rispetto all’ordinamento naturale possono essere, anzi sono, molto distanti su questo grafo. La difficoltà di scomporre in fattori primi dipende da questo. Proviamo a cercare 100 e 101 sul grafo completo, che ci limitiamo ad immaginare senza disegnarlo. 100 si trova nella quinta colonna perché ha un totale di 4 fattori primi, e dovremmo collocarlo piuttosto in basso perché i suoi fattori primi sono tutti piccoli. 101, invece, è un numero primo e quindi si trova nella seconda colonna, al ventiseiesimo piano.

L’esistenza di infiniti numeri primi e la complessità dell’ordinamento che abbiamo introdotto e studiato hanno come conseguenza il fatto che gli algoritmi noti per la scomposizione in fattori primi sono relativamente poco efficienti. In positivo, questo permette di utilizzare sistemi crittografici come RSA, la cui sicurezza dipende appunto dalla difficoltà della fattorizzazione.

Durante la costruzione del grafo abbiamo notato che il rapporto fra successori immediati è sempre un numero primo. In particolare, i successori immediati di 1 sono infiniti, perché sono tutti i numeri primi. Altre cose che vediamo bene dal grafo sono il massimo comun divisore e il minimo comune multiplo di due interi \(a\) e \(b\). Si tratta del piú grande predecessore e del piú piccolo successore comune. Nel primo caso, è il piú grande intero dal quale è possibile raggiungere sia \(a\) che \(b\) muovendosi lungo le frecce; nel secondo, si tratta del piú piccolo intero raggiungibile da entrambi, sempre spostandosi lungo le frecce. Chiaramente, dal numero 1 è possibile raggiungere ogni altro numero, e \(a b\) è raggiungibile sia da \(a\) che da \(b\), quindi il problema è ben posto.

Proponiamo qualche ulteriore osservazione finale, per sottolineare ancora quanto siano strutturalmente differenti le operazioni di addizione e moltiplicazione. Sommiamo due numeri interi, ottenendo un certo risultato. Immaginiamo di cambiare di una unità una cifra di uno degli addendi: a meno di riporti, cambia solo la corrispondente cifra del risultato. Se moltiplichiamo due interi e poi modifichiamo di una unità una cifra di uno dei fattori, il cambiamento si “propaga” a sinistra su molte altre cifre, potenzialmente tutte. È un rudimentale esempio del fenomeno che in crittografia si chiama “effetto valanga”: un piccolo cambiamento dei dati iniziali provoca un grande cambiamento del risultato.

Lasciamo ai lettori la soluzione di due problemi, formalmente analoghi, uno per l’addizione e uno per la moltiplicazione. Vogliamo contare il numero di soluzioni delle equazioni introdotte all’inizio. Dato \(n \in {\mathbb{N}}\), determinare \(\vert \{ (a, b) \in {\mathbb{N}}^2 \colon a + b = n \} \vert\). Analogamente, dato \(n \in {\mathbb{N}}^*\), determinare \(\vert \{ (a, b) \in ({\mathbb{N}}^*)^2 \colon a b = n \} \vert\). Quest’ultimo è il numero di volte in cui \(n\) appare in una tavola pitagorica con almeno \(n\) righe ed \(n\) colonne, ed è il numero totale dei divisori di \(n\). Questa è una delle funzioni piú naturali da studiare sui numeri interi positivi, ed è anche una delle piú difficili da comprendere a fondo. Invitiamo i lettori a risolvere i problemi proposti almeno per tutti gli interi fra 1 e 10. La radicale differenza delle risposte si può leggere dai nostri grafi: tutti gli interi \(m \le n\) precedono \(n\) dal punto di vista dell’addizione, solo alcuni (pochi) lo precedono dal punto di vista della moltiplicazione, e il loro numero è molto variabile da un intero all’altro. I numeri primi hanno solo due divisori, per definizione, ma ogni tanto si incontrano degli interi che ne hanno relativamente tanti.

In conclusione, anche una delle piú semplici operazioni aritmetiche è all’origine di una tale complessità che possiamo usarla per proteggere la sicurezza e la riservatezza delle nostre conversazioni private, e dei nostri dati. Siete ancora convinti che addizione e moltiplicazione siano parenti?

Un gioco

Ci congediamo con un piccolo gioco. Abbiamo visto sopra che è possibile disegnare su un piano, senza intersezioni, il grafo che contiene tutte le potenze di 2 e tutte le potenze di 3, e che compaiono delle intersezioni non appena tentiamo di aggiungere le potenze di 5. Vogliamo mostrare come sia possibile disegnare una porzione di quest’ultimo grafo, senza intersezioni, se accettiamo di utilizzare una superficie diversa dal piano.

La figura qui sotto contiene tutti gli interi con 0, 1 o 2 fattori primi scelti fra 2, 3, 5, 7, collegati da frecce usando le stesse regole del resto di questo articolo. Le righe colorate esterne rosse e blu, e i punti \(A_1\), \(A_2\), …, \(H_1\), \(H_2\) servono alla costruzione, ma non fanno parte del grafo vero e proprio, e si dovrebbero cancellare alla fine dell’operazione. Proponiamo di stampare a colori, ritagliare e incollare la figura qui sopra, facendo corrispondere i lati colorati preservando l’orientamento delle frecce, e le coppie di punti \(A_1\) e \(A_2\), \(B_1\) e \(B_2\), …

Procediamo in questo modo: per prima cosa incolliamo i lati rossi verticali, ottenendo un cilindro di carta. I punti \(B_1\) e \(B_2\) devono corrispondere, in modo che la freccia nera che esce da \(5\) “entri” in 35, passando appunto prima per \(B_1\) e per \(B_2\), che sono sovrapposti. Lo stesso accade, automaticamente, per le coppie di punti \(C_1\) e \(C_2\), …, \(H_1\) e \(H_2\).

L’unica freccia che resta “spezzata” è quella rossa che proviene da 5 e dovrebbe arrivare a 10. Per poterla collegare, incolliamo anche i lati blu: per fare questo dobbiamo appiattire e piegare il cilindro ottenuto al passo precedente ed inserire una delle estremità nell’altra.

In questo modo, il grafo non ha intersezioni, ma se non incolliamo i lati orizzontali blu non c’è modo di collegare 5 a 10 senza attraversare uno degli archi già disegnati. In pratica, lo stiamo disegnando su un toro, cioè su una ciambella. Se incolliamo solo i lati verticali rossi, cioè se disegniamo il grafo su un cilindro, i numeri 5 e 10 non sono collegabili. L’ideale sarebbe disegnare questo grafo su un supporto elastico, invece che su un foglio di carta, e poi incollarlo su un anello di plastica.

Riferimenti

L’idea che la moltiplicazione iterata possa dare dei bei grafi è alla base di un laboratorio sviluppato dall’Autore con Giancarlo Fiorini nell’ambito del Piano Nazionale Lauree Scientifiche: si veda ^{[1 ]}G. Fiorini & A. Zaccagnini, Costruzione dei grafi di \(\mathbb{Z}_{n}^*\). Un laboratorio PLS in una classe terza del Liceo Scientifico, A spasso per la Matematica — PLS 2014–2018 (A. Saracco e A. Zaccagnini, ed.), CLEUP, Padova, 2018, Dipartimento di Scienze Matematiche, Fisiche e Informatiche, Università di Parma, pp. 51–73 & 97–102. per la versione a stampa e ^{[2 ]}G. Fiorini & A. Zaccagnini, Costruzione dei grafi di \(\mathbb{Z}_{n}^*\). Un laboratorio PLS in una classe terza del Liceo Scientifico, Dipartimento di Scienze Matematiche, Fisiche e Informatiche, Università di Parma (2018), PLS – Parma. Versione integrale. Online dal 9.10.2018. http://people.dmi.unipr.it/alessandro.zaccagnini/psfiles/papers/fz-integrale.pdf per una versione estesa. Ci siamo naturalmente ispirati al bel libro di Daniel Shanks ^{[3 ]}D. Shanks, Solved and Unsolved Problems in Number Theory, fourth ed., Chelsea, New York, 1993., molto originale nella forma e nei contenuti.

Alessandro Zaccagnini