Ci siamo lasciati lo scorso 10 aprile con un articolo riguardante alcuni teoremi di geometria utili nelle gare matematiche. Ci ritroviamo a distanza di nove mesi, il che rende le scuse obbligatorie nei confronti di tutti coloro che seguivano con un certo interesse la rubrica qui proposta. Nel frattempo, troppe cose sono accadute (tra cui il fatto di essere diventato papà per la seconda volta, che in parte giustifica una certa latitanza da questo blog). Tra le grandi novità, troviamo il fatto che nel corrente a.s. 2022/2023 le olimpiadi sono riprese a pieno ritmo e, finalmente, si torna a gareggiare in presenza! E allora, perché non rimboccarsi le maniche e approfondire qualche nuovo tema che potrebbe rivelarsi utile in gara?

Questo articolo è incentrato sulle congruenze, un classico argomento di teoria dei numeri. Quanto proposto prende spunto dal lavoro preparato e utilizzato dal sottoscritto e dal collega Antonio Veredice per un laboratorio PLS tenuto presso Sapienza Università di Roma nel corso degli ultimi anni. Buona lettura, buon divertimento e buon anno olimpico a tutti!

Una delle tecniche più utilizzate dai docenti per scegliere chi interrogare, ma anche fra le più temute dagli studenti, consiste nell’apertura “a caso” di un libro in modo da leggere una delle due pagine che si presenta davanti e poi, scomodando qualche algoritmo di calcolo (generalmente vengono sommate le cifre), ottenere il numero che corrisponde, registro alla mano, al povero sfortunato da chiamare alla lavagna. Proponiamo a riguardo un semplice esercizio:

In una classe in cui sono presenti 30 studenti (cosa non impossibile, nell’era delle cosiddette “classi pollaio”), per poter interrogare lo studente numero 30, qual è il più piccolo numero di pagina che dovrà essere visualizzato dal docente, supponendo che la procedura adottata sia quella di sommare le cifre? Risposta: 3.999, valore ben lontano dall’ampiezza dei più comuni libri in circolazione. Lo studente in questione può quindi dormire sonni tranquilli…

Se volessimo tentare di scomodare un metodo un po’ più equo (sebbene presenta anch’esso dei limiti che però non discuteremo), possiamo pensare di procedere nel seguente modo. Supponiamo di avere, ancora una volta, una classe di 30 studenti. Se apriamo il libro e leggiamo un numero di pagina compreso da 1 a 30, la scelta di chi interrogare è ovvia. Se dovesse capitarci pagina 31, potremmo immaginare di “ricominciare da capo” e quindi interrogare il primo studente della lista. Con pagina 32 interroghiamo il secondo studente e così via, fino a pagina 60 che corrisponde a chiamare l’ultimo studente (il trentesimo). E se capita pagina 61? Nuovamente si ricomincia da capo, chiamando il primo studente, ecc.

L’aritmetica modulare è anche detta “aritmetica dell’orologio”

Quella che stiamo facendo è una semplice operazione che, nella realtà dei fatti, applichiamo tutti i giorni in contesti diversi. Ad esempio, se ora sono le 10.00, fra 24 ore saranno nuovamente le 10.00 e non le 34.00! In termini matematici, diremo che 10 e 34 sono congrui modulo 24 così come, nel caso del precedente esempio, 31 e 1 sono congrui fra loro modulo 30. In generale, due interi $a$ e $b$ si dicono congrui fra di loro modulo $n$, con $n$ naturale maggiore di 1 (e si scriverà $a \equiv b$ mod $n$) se ammettono lo stesso resto nella divisione per $n$ o, equivalentemente, se $a-b$ è un multiplo di $n$. Si può dimostrare che le due definizioni qui proposte sono fra di loro equivalenti. Ad esempio, 7 e 31 sono congrui fra loro modulo 6 in quanto nella divisione per 6 ammettono lo stesso resto (pari ad 1) o, equivalentemente, la differenza $31-7$ è uguale a 24, il quale è un multiplo di 6. Per la dimostrazione o approfondimenti sul tema, suggeriamo la lettura del seguente articolo.

La parola “congruenza” ricorda, in un certo qual modo, il concetto di uguaglianza. E difatti è semplice dimostrare che, come l’uguaglianza, la congruenza gode della proprietà riflessiva, simmetrica e transitiva; inoltre, se $a \equiv b$ mod $n$, $c \equiv d$ mod $n$ e fissato un $k$ intero positivo, allora risulta:

(1) $a+c \equiv b+d$ mod $n$

(2) $a \cdot c \equiv b \cdot d$ mod $n$

(3) $a^{k} \equiv  b^{k}$ mod $n$

Le congruenze permettono di dimostrare i criteri di divisibilità. Ad esempio, è noto che un numero è divisibile per 9 se la somma delle sue cifre è pari a 9 o un multiplo di 9. Perché? Sia $a$ un numero intero positivo di $k+1$ cifre, con $k \geq 0$. Esso può essere scritto nella forma polinomiale $a = a_{k} \cdot 10^{k} + a_{k-1} \cdot 10^{k-1} + … + a_{1} \cdot 10 + a_{0}$. Poiché $10 \equiv 10^{2} \equiv 10^{3} \equiv … \equiv 10^{k} \equiv 1$ mod 9, allora $a \equiv a_{k}+a_{k-1}+…+a_{1}+a_{0}$ mod 9.

Discende dalla definizione che ogni intero positivo è congruo modulo 10 alla sua ultima cifra, vale a dire alla cifra delle unità. Ad esempio, $523 \equiv 3$ mod 10, in quanto 3 è esattamente il resto della divisione per 10 di 523 o, in modo del tutto equivalente, $523-3=10k$ (in questo caso, con $k=52$). Analogamente, ogni intero positivo è congruo modulo 100 alle sue ultime due cifre, e così via: ogni intero positivo è congruo modulo $10^{k}$ alle sue ultime $k$ cifre.

Mostriamo di seguito alcuni classici esercizi relativi alle congruenze.

Determinare la cifra delle unità di $3^{2023}.$

Soluzione: $3^{2023} = 3^{3} \cdot 3^{2020} = 3^{3} \cdot (3^{4})^{505} = 27 \cdot 81^{505}$. Risulta che $81 \equiv 1$ mod 10, da cui per la (3) si ha $81^{505} \equiv 1^{505} = 1$ mod 10, pertanto la cifra delle unità di $3^{2023}$ è pari a 7.

Dimostrare che, per ogni numero naturale $n$, l’espressione $6^{n}-1$ è un multiplo di 5.

Soluzione: $6 \equiv 1$ mod 5, allora per la (3) si ha $6^{n} \equiv 1^{n}$ mod 5, vale a dire $6^{n}-1 = 5k$.

Qual è il resto della divisione per 6 del numero $2023^{2023}$?

Soluzione: poiché $2023 \equiv 1$ mod 6, allora $2023^{2023} \equiv 1^{2023} = 1$ mod 6. Pertanto il resto è pari ad 1.

Qual è il resto della divisione per 37 del numero $6^{1987}$?

Soluzione: poiché $6^{2} \equiv -1$ mod 37, allora risulta che $6^{1987} = 6 \cdot 6^{1986} = 6 \cdot (6^{2})^{993} \equiv 6 \cdot (-1)^{993} = -6 \equiv 31$ mod 37. Pertanto il resto è pari a 31.

Dimostrare che 7 divide $3^{2n+1} + 2^{n+2}$ per ogni $n$ naturale.

Soluzione: fermo restando che per dimostrare quanto richiesto si può procedere per induzione (chi avesse ancora dei dubbi sul tema, trova una breve spiegazione qui), proviamo in questo caso a sfruttare le congruenze. Osserviamo che $3^{2n+1} = 3 \cdot 3^{2n} = 3 \cdot 9^{n} \equiv 3 \cdot 2^{n}$ mod 7. Allora $3^{2n+1} + 2^{n+2} \equiv 3 \cdot 2^{n} + 4 \cdot 2^{n} = 7 \cdot 2^{n} \equiv 0$ mod 7.

Dimostrare che 7 divide $2222^{5555} + 5555^{2222}$.

Soluzione: risulta che $2222 \equiv 3$ mod 7, $5555 \equiv 4$ mod 7 e $3^{5} \equiv 5$ mod 7. Allora $2222^{5555} + 5555^{2222} \equiv 3^{5555} + 4^{2222} \equiv (3^{5})^{1111} + (4^{2})^{1111} \equiv 5^{1111} + (-5)^{1111} \equiv 0$ mod 7.

Dimostrare che, comunque si scelgano tre interi $a$, $b$, $c$, risulta che se 21 divide $100a+10b+c$, allora 21 divide $a-2b+4c$.

Soluzione: dire che 21 divide $100a+10b+c$, vuol dire che $100a+10b+c \equiv 0$ mod 21. Osserviamo che $100a \equiv 16a$ mod 21, per cui risulta $16a+10b+c \equiv 0$ mod 21 e quindi $c \equiv -16a-10b$ mod 21. Pertanto $a-2b+4c \equiv a-2b+4 \cdot (-16a-10b) = -63a-42b = 21 \cdot (-3a-2b) \equiv 0$ mod 21.

Mediante le congruenze è possibile caratterizzare i quadrati perfetti. Infatti ogni quadrato perfetto è della forma $4k$ (se la base è un numero pari, in quanto $(2h)^{2}=4h^{2}=4k$, avendo posto $h^{2}=k$) o $4k+1$ (se la base è un numero dispari, in quanto $(2h+1)^{2} = 4h^{2}+4h+1 = 4(h^{2}+h)+1 = 4k+1$, avendo posto $h^{2}+h=k$). Pertanto il quadrato di un intero pari è sempre congruo a 0 modulo 4, mentre il quadrato di un intero dispari è sempre congruo a 1 modulo 4 (lasciamo al lettore il piacere di dimostrare che il quadrato di un intero dispari è anche congruo a 1 modulo 8).

Dimostrare che non esistono quadrati perfetti della forma $\sum_{k=0}^{n} 10^{k}$, comunque si scelga $n$ intero positivo (vale a dire, numeri della forma 11, 111, 1111,…)

Soluzione: tutti i numeri della forma assegnata sono congrui a 3 modulo 4, dunque non esiste alcun numero di tale tipologia che è un quadrato perfetto.

Un risultato particolarmente importante, che può rivelarsi utile nella risoluzione di alcuni quesiti, è il cosiddetto Piccolo Teorema di Fermat : dato un intero $a$ e un numero primo $p$, allora risulta $a^{p} \equiv a$ mod $p$. In particolare, se $a$ e $p$ sono coprimi fra loro, allora $a^{p-1} \equiv 1$ mod $p$.

Dimostrare che per ogni naturale $n$ il numero $2n^{17}+2n^{15}+3n^{3}+3n$ è divisibile per 5.

Soluzione: poiché, per il piccolo teorema di Fermat, risulta che $n^{5} \equiv n$ mod 5, allora si ha $2n^{17}+2n^{15}+3n^{3}+3n \equiv 2n^{2} \cdot (n^{5})^{3} + 2(n^{5})^{3} + 3n^{3} + 3n \equiv 2n^{2} \cdot n^{3} + 2n^{3} + 3n^{3}+3n \equiv$

$\equiv 2n^{5}+5n^{3}+3n \equiv 2n+5n^{3}+3n \equiv 5n^{3}+5n \equiv 0$ mod 5.

Concludiamo con un esercizio tratto dalle IMO del 9175:

Quando $4444^{4444}$ è scritto in base 10, la somma delle sue cifre è $A$. Sia $B$ la somma delle cifre di $A$; trovare la somma delle cifre di $B$.

Soluzione: chiamiamo $C$ la somma delle cifre di $B$. Proviamo prima di tutto a trovare una limitazione al valore di $C$. Risulta che $4444^{4444} < 10000^{4444} = (10^{4})^{4444} = 10^{17776}$. Dunque $4444^{4444}$ ha un numero di cifre minore di 17776; nel caso “peggiore” in cui ciascuna cifra è pari a 9, risulta che $A < 9 \cdot 17776 = 159984$. Il valore compatibile con la limitazione appena trovata e che massimizza la somma delle cifre è pari ad $A = 99999$, da cui $B \leq 45$. In particolare, se $B$ fosse pari a 39, allora $C$ sarebbe pari a 12, il quale è il massimo valore che può assumere la somma delle cifre di $B$ ($1\leq C \leq 12$).

Ricordiamo ora che un qualunque numero è congruo modulo 9 alla somma delle sue cifre, pertanto $4444^{4444} \equiv A$ mod 9, $A \equiv B$ mod 9 e $B \equiv C$ mod 9, da cui risulta che $4444^{4444} \equiv C$ mod 9. Osserviamo che $4444 \equiv 7$ mod 9, $4444^{2} \equiv 4$ mod 9 e $4444^{3} \equiv 1$ mod 9, per cui $4444^{4444} = 4444^{3 \cdot 1481 + 1} = (4444^{3})^{1481} \cdot 4444 \equiv 1 \cdot 4444 \equiv 7$ mod 9. Ne consegue che, anche alla luce della stima precedentemente trovata, $C=7$.

CC BY-NC-SA 4.0
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.