Teoria dei numeri · laboratorio
Dall’orologio alle congruenze, dai cicli delle potenze al teorema cinese del resto.
Un orologio da 12 ore non si ferma a 12: dopo le 10, cinque ore più tardi indica le 3. Il laboratorio usa questa idea per studiare resti, divisibilità e problemi sempre più ricchi. Apri “Perché funziona?” in ogni tappa e poi prova gli strumenti.
Tappa 1 / 15
Dopo un giro completo si torna allo stesso punto. Contiamo solo quanto avanza oltre i giri interi.
10+5=15 ≡ 3 (mod 12)
Esempio: 17, 29 e 41 lasciano tutti resto 5 nella divisione per 12.
Le differenze tra questi numeri sono multipli di 12: cambiano i giri, non la posizione.
Tappa 2 / 15
Due interi sono congruenti quando appartengono alla stessa classe di resto.
a ≡ b (mod n) ⇔ n divide a−b
Esempio: 23 ≡ 3 (mod 10), perché 23−3=20.
Se a−b=kn, allora a e b differiscono di k giri completi di ampiezza n.
Tappa 3 / 15
Usiamo la divisione euclidea e scegliamo sempre il resto non negativo.
a=nq+r, 0≤r<n
Esempio: −17=5×(−4)+3: quindi −17 mod 5=3.
Il quoziente può essere negativo; la condizione 0≤r<n rende il resto unico. Modulo 1 il resto è sempre 0.
Tappa 4 / 15
Possiamo ridurre gli addendi prima di sommare o sottrarre.
a≡b, c≡d ⇒ a±c≡b±d (mod n)
Esempio: 17+29 ≡ 5+5 ≡ 10 (mod 12).
La somma e la differenza di multipli di n sono ancora multipli di n.
Tappa 5 / 15
Anche il prodotto conserva le congruenze.
a≡b, c≡d ⇒ ac≡bd (mod n)
Esempio: 123×456 mod 7 = 4×1 mod 7 = 4.
Se a=b+kn e c=d+hn, il prodotto ac−bd contiene n come fattore.
Tappa 6 / 15
Le potenze visitano un numero finito di resti: prima o poi un resto si ripete.
7¹,7²,7³,7⁴ ≡ 7,9,3,1 (mod 10)
Esempio: 2026 mod 4=2, quindi 7^2026 termina con 9.
Quando uno stato si ripete, moltiplicare ancora per la stessa base riproduce il percorso. Alcuni cicli hanno una preattesa prima della ripetizione.
Tappa 7 / 15
La cifra finale è semplicemente il resto modulo 10.
ultima cifra di a^b = a^b mod 10
Esempio: 3^25: ciclo 3,9,7,1; 25 mod 4=1, quindi la cifra è 3.
Due numeri sono uguali modulo 10 proprio quando hanno la stessa ultima cifra.
Tappa 8 / 15
Per le ultime due cifre passiamo a modulo 100 e scriviamo sempre due cifre.
ultime due cifre di a^b = a^b mod 100
Esempio: 3^100 mod 100=1, quindi le ultime due cifre sono 01.
L’esponenziazione per quadrati successivi evita di costruire una potenza enorme.
Tappa 9 / 15
Una cifra decimale è una potenza di 10: possiamo sostituire 10 con il suo resto.
10≡1 (mod 9); 10≡−1 (mod 11)
Esempio: 5724: 5+7+2+4=18, quindi è divisibile per 9. Per 11, 2728 dà 2−7+2−8=−11: è divisibile per 11.
Modulo 9 tutte le potenze di 10 valgono 1; modulo 11 alternano 1 e −1.
Tappa 10 / 15
Le ore girano modulo 12 o 24; i giorni della settimana modulo 7.
22+17≡15 (mod 24); 100≡2 (mod 7)
Esempio: Cento giorni dopo lunedì sarà mercoledì.
Ogni ciclo completo riporta lo stesso indicatore alla posizione iniziale.
Tappa 11 / 15
L’equazione ax≡b (mod n) può avere nessuna, una o più soluzioni.
d=MCD(a,n); esistono soluzioni ⇔ d divide b
Esempio: 6x≡4 (mod 8): d=2, le soluzioni sono 2 e 6.
Dividendo per d si ottiene una soluzione modulo n/d; questa produce d classi modulo n.
Tappa 12 / 15
L’inverso di a è il numero che moltiplicato per a dà resto 1.
a⁻¹ esiste (mod n) ⇔ MCD(a,n)=1, n>1
Esempio: 7×3=21≡1 (mod 10); dunque 7⁻¹≡3.
L’identità di Bézout fornisce 1 come combinazione di a e n esattamente quando il loro MCD è 1.
Tappa 13 / 15
Cerchiamo un intero che soddisfi più condizioni sui resti nello stesso tempo.
x≡2 (mod 3); x≡3 (mod 5)
Esempio: Il più piccolo positivo è x=8.
Dalla prima condizione x=2+3t; sostituendo nella seconda troviamo t≡2 (mod 5).
Tappa 14 / 15
Con moduli coprimi a coppie il sistema ha una sola classe soluzione modulo il loro prodotto.
x≡2 (mod 3), x≡3 (mod 5), x≡2 (mod 7) ⇒ x≡23 (mod 105)
Esempio: 23 diviso per 3, 5 e 7 lascia rispettivamente 2, 3 e 2.
Ogni nuova congruenza sceglie un valore del parametro della soluzione precedente; la coprimalità rende possibile e unica la scelta.
Tappa 15 / 15
I resti diventano uno strumento per cifre finali, quadrati impossibili, sfide su orologi e sistemi.
7^(7^7) mod 10: prima riduci l’esponente modulo 4
Esempio: 7^7≡3 (mod 4), quindi l’ultima cifra di 7^(7^7) è 3.
Un grande problema si spezza in piccoli moduli annidati. Le 25 sfide qui sotto permettono di esercitarsi.
Inserisci numeri interi. Il modulo deve essere positivo; modulo 1 è ammesso nei calcoli dei resti, ma non ha inversi modulari.
Confronta tutti i quadrati o cubi modulo n (fino a 60) e osserva i residui distinti.
Rispondi prima di aprire il suggerimento o la soluzione. I tentativi e i problemi risolti restano soltanto in questo browser, anche cambiando lingua.
1 / 25 · Facile
Calcola 37 mod 5.
Quante volte 5 entra in 37?
2 / 25 · Facile
È vero che 47≡5 (mod 7)? Rispondi sì o no.
Sottrai 5 da 47.
3 / 25 · Facile
Sono le 9. Che ora sarà tra 17 ore su un orologio da 12 ore?
Somma e poi togli i giri completi di 12.
4 / 25 · Facile
Oggi è lunedì. Che giorno sarà tra 100 giorni?
Riduci 100 modulo 7.
5 / 25 · Facile
Qual è l’ultima cifra di 3^25?
Il ciclo modulo 10 è 3,9,7,1.
6 / 25 · Facile
Qual è l’ultima cifra di 7^2026?
Il ciclo è 7,9,3,1.
7 / 25 · Facile
123456789 è divisibile per 9? Rispondi sì o no.
Somma le cifre.
8 / 25 · Medio
2728 è divisibile per 11? Rispondi sì o no.
Alterna i segni delle cifre.
9 / 25 · Medio
Calcola (1234567+9876543) mod 9.
Riduci separatamente i due addendi.
10 / 25 · Medio
Calcola 123×456 mod 7.
Riduci i fattori prima di moltiplicarli.
11 / 25 · Medio
Calcola 2^100 mod 7.
Il ciclo è 2,4,1.
12 / 25 · Medio
Calcola 5^2025 mod 13.
Calcola le prime quattro potenze di 5 modulo 13.
13 / 25 · Medio
Risolvi 3x≡1 (mod 7): indica x modulo 7.
Cerca il numero che moltiplicato per 3 dà resto 1.
14 / 25 · Medio
Risolvi 7x≡3 (mod 10): indica x modulo 10.
L’inverso di 7 modulo 10 è 3.
15 / 25 · Difficile
Risolvi 6x≡5 (mod 8). Scrivi “nessuna” se non esistono soluzioni.
Calcola MCD(6,8).
16 / 25 · Difficile
Risolvi 6x≡4 (mod 8). Scrivi entrambe le soluzioni separate da virgola.
Dividi per MCD(6,8)=2.
17 / 25 · Difficile
Trova il minimo x positivo con x≡2 (mod 3) e x≡3 (mod 5).
Scrivi x=2+3t.
18 / 25 · Difficile
Trova il minimo x positivo con resti 2 modulo 3, 3 modulo 5 e 2 modulo 7.
Parti dalla soluzione x=8 delle prime due condizioni.
19 / 25 · Difficile
Trova il minimo positivo con resti 1,2,3,4 quando è diviso per 2,3,4,5.
Il numero è −1 modulo ciascuno dei quattro moduli.
20 / 25 · Difficile
Quali sono le ultime due cifre di 3^100? Scrivile come due cifre.
3^20≡1 (mod 100).
21 / 25 · Sfida
Calcola (10^1000+3) mod 7.
10≡3 (mod 7) e 3^6≡1 (mod 7).
22 / 25 · Sfida
Può esistere x intero con x²≡3 (mod 4)? Rispondi sì o no.
Prova i quattro resti 0,1,2,3.
23 / 25 · Sfida
Quali sono i residui distinti di x³ modulo 9? Scrivili separati da virgola.
Prova x=0,1,…,8.
24 / 25 · Sfida
Spiega perché n³−n è divisibile per 6 per ogni intero n.
Scomponi n³−n=n(n−1)(n+1).
25 / 25 · Sfida
Trova l’ultima cifra di 7^(7^7).
Il ciclo di 7 modulo 10 ha periodo 4: riduci prima 7^7 modulo 4.
Da monete e soldati ai calendari: risolvi i sistemi di congruenze, controlla i vincoli e scopri quando una risposta non esiste. Le soluzioni sono subito sotto ogni problema, ma restano chiuse finché vuoi provarci.
Leggi l’articolo: Sunzi e il teorema cinese del resto →
Nel Sunzi Suanjing il problema classico chiede un numero con resti 2, 3 e 2 quando è diviso per 3, 5 e 7. I blocchi 70, 21 e 15 danno 2×70 + 3×21 + 2×15 = 233; togliendo due volte 105 si ottiene 23.
1 / 30 · Base
Trova il più piccolo intero positivo che soddisfa tutte le condizioni.
x ≡ 1 (mod 3) · x ≡ 2 (mod 5) · x ≡ 3 (mod 7)
Unisci le congruenze una alla volta: poni x uguale al primo resto più un multiplo del primo modulo.
2 / 30 · Base
Trova il più piccolo intero positivo che soddisfa tutte le condizioni.
x ≡ 2 (mod 3) · x ≡ 2 (mod 5) · x ≡ 2 (mod 7)
Se tutti i resti coincidono, sottrai quel resto e cerca un multiplo del mcm dei moduli.
3 / 30 · Base
Trova il più piccolo intero positivo che soddisfa tutte le condizioni.
x ≡ 2 (mod 3) · x ≡ 4 (mod 5) · x ≡ 6 (mod 7)
Ogni resto è uno meno del modulo: prova a ragionare su x+1.
4 / 30 · Base
Trova il più piccolo intero positivo che soddisfa tutte le condizioni.
x ≡ 2 (mod 5) · x ≡ 3 (mod 7)
Unisci le congruenze una alla volta: poni x uguale al primo resto più un multiplo del primo modulo.
5 / 30 · Base
Trova il più piccolo intero positivo che soddisfa tutte le condizioni.
x ≡ 1 (mod 4) · x ≡ 2 (mod 5) · x ≡ 3 (mod 7)
Unisci le congruenze una alla volta: poni x uguale al primo resto più un multiplo del primo modulo.
7 / 30 · Base
Un mercante raggruppa le monete a 3, 5 e 7: avanzano rispettivamente 2, 4 e 6 monete. Qual è il minimo?
x ≡ 2 (mod 3) · x ≡ 4 (mod 5) · x ≡ 6 (mod 7)
Ogni resto è uno meno del modulo: prova a ragionare su x+1.
16 / 30 · Base
Un mercante dispone i sacchi di riso in gruppi da 4, 5 o 6: ne rimangono sempre uno meno del gruppo.
x ≡ 3 (mod 4) · x ≡ 4 (mod 5) · x ≡ 5 (mod 6)
Ogni resto è uno meno del modulo: prova a ragionare su x+1.
6 / 30 · Intermedi
Trova il più piccolo intero positivo che soddisfa tutte le condizioni.
x ≡ 1 (mod 5) · x ≡ 2 (mod 7) · x ≡ 3 (mod 8)
Unisci le congruenze una alla volta: poni x uguale al primo resto più un multiplo del primo modulo.
8 / 30 · Intermedi
Un generale schiera i soldati in file da 4, 5 e 7: restano fuori rispettivamente 1, 2 e 4 soldati.
x ≡ 1 (mod 4) · x ≡ 2 (mod 5) · x ≡ 4 (mod 7)
Unisci le congruenze una alla volta: poni x uguale al primo resto più un multiplo del primo modulo.
10 / 30 · Intermedi
Trova il più piccolo intero positivo che soddisfa tutte le condizioni.
x ≡ 3 (mod 5) · x ≡ 4 (mod 7) · x ≡ 5 (mod 9)
Unisci le congruenze una alla volta: poni x uguale al primo resto più un multiplo del primo modulo.
11 / 30 · Intermedi
Trova il più piccolo intero positivo che soddisfa tutte le condizioni.
x ≡ 1 (mod 2) · x ≡ 2 (mod 3) · x ≡ 3 (mod 5) · x ≡ 4 (mod 7)
Unisci le congruenze una alla volta: poni x uguale al primo resto più un multiplo del primo modulo.
13 / 30 · Intermedi
Quali resti lascia 47 quando viene diviso per 3, 5 e 7? Scrivi i tre resti nell’ordine, separati da virgole.
47 mod 3, 5, 7
Dividi 47 per ciascun modulo e annota i tre resti nell’ordine.
17 / 30 · Intermedi
Le file di soldati sono da 5, 7 o 8 e lasciano rispettivamente 1, 3 o 4 soldati fuori.
x ≡ 1 (mod 5) · x ≡ 3 (mod 7) · x ≡ 4 (mod 8)
Unisci le congruenze una alla volta: poni x uguale al primo resto più un multiplo del primo modulo.
19 / 30 · Intermedi
Trova il più piccolo intero positivo che soddisfa tutte le condizioni.
x ≡ 1 (mod 6) · x ≡ 2 (mod 7) · x ≡ 3 (mod 8)
Unisci le congruenze una alla volta: poni x uguale al primo resto più un multiplo del primo modulo.
20 / 30 · Intermedi
Tre eventi periodici si ripetono ogni 5, 7 e 9 giorni. Le prossime occorrenze sono tra 1, 3 e 4 giorni: quando avverranno insieme?
x ≡ 1 (mod 5) · x ≡ 3 (mod 7) · x ≡ 4 (mod 9)
Unisci le congruenze una alla volta: poni x uguale al primo resto più un multiplo del primo modulo.
21 / 30 · Intermedi
Travasando una quantità intera d’acqua in recipienti da 8, 9 o 13 litri avanzano 3, 5 o 7 litri.
x ≡ 3 (mod 8) · x ≡ 5 (mod 9) · x ≡ 7 (mod 13)
Unisci le congruenze una alla volta: poni x uguale al primo resto più un multiplo del primo modulo.
22 / 30 · Intermedi
Trova il più piccolo intero positivo che soddisfa tutte le condizioni.
x ≡ 2 (mod 6) · x ≡ 5 (mod 9)
Per moduli non coprimi, i resti devono coincidere modulo il loro MCD.
25 / 30 · Intermedi
Trova il più piccolo intero positivo che soddisfa tutte le condizioni.
x ≡ 1 (mod 5) · x ≡ 2 (mod 6) · x ≡ 3 (mod 7)
Unisci le congruenze una alla volta: poni x uguale al primo resto più un multiplo del primo modulo.
9 / 30 · Difficili
Trova il più piccolo intero positivo che soddisfa tutte le condizioni.
x ≡ 3 (mod 8) · x ≡ 5 (mod 9) · x ≡ 7 (mod 11)
Unisci le congruenze una alla volta: poni x uguale al primo resto più un multiplo del primo modulo.
12 / 30 · Difficili
Trova il più piccolo intero positivo che soddisfa tutte le condizioni.
x ≡ 5 (mod 8) · x ≡ 7 (mod 9) · x ≡ 9 (mod 11)
Unisci le congruenze una alla volta: poni x uguale al primo resto più un multiplo del primo modulo.
15 / 30 · Difficili
Trova il più piccolo intero positivo che soddisfa tutte le condizioni.
x ≡ 2 (mod 7) · x ≡ 4 (mod 9) · x ≡ 6 (mod 11)
Unisci le congruenze una alla volta: poni x uguale al primo resto più un multiplo del primo modulo.
26 / 30 · Difficili
Il numero cercato è tra 100 e 500 inclusi.
x ≡ 2 (mod 7) · x ≡ 3 (mod 8) · x ≡ 4 (mod 9)
Cerca una soluzione nel limite indicato; se non esiste, scrivi “nessuna”. Da 100 · Fino a 500
Risolvi prima senza vincoli; poi confronta il minimo positivo con l’intervallo richiesto.
28 / 30 · Difficili
Trova il più piccolo intero positivo che soddisfa tutte le condizioni.
x ≡ 1 (mod 3) · x ≡ 2 (mod 4) · x ≡ 3 (mod 5) · x ≡ 4 (mod 7)
Unisci le congruenze una alla volta: poni x uguale al primo resto più un multiplo del primo modulo.
30 / 30 · Difficili
Trova il più piccolo intero positivo che soddisfa tutte le condizioni.
x ≡ 4 (mod 7) · x ≡ 5 (mod 8) · x ≡ 6 (mod 9) · x ≡ 7 (mod 11)
Unisci le congruenze una alla volta: poni x uguale al primo resto più un multiplo del primo modulo.
14 / 30 · Trabocchetti senza soluzione nel vincolo dato
Trova il più piccolo intero positivo che soddisfa tutte le condizioni.
x ≡ 1 (mod 4) · x ≡ 2 (mod 6)
Per moduli non coprimi, i resti devono coincidere modulo il loro MCD.
18 / 30 · Trabocchetti senza soluzione nel vincolo dato
Il tesoro contiene meno di 500 monete; i resti dividendo per 7, 9 e 11 sono 2, 4 e 6.
x ≡ 2 (mod 7) · x ≡ 4 (mod 9) · x ≡ 6 (mod 11)
Cerca una soluzione nel limite indicato; se non esiste, scrivi “nessuna”. Meno di 500
Risolvi prima senza vincoli; poi confronta il minimo positivo con l’intervallo richiesto.
23 / 30 · Trabocchetti senza soluzione nel vincolo dato
Trova il più piccolo intero positivo che soddisfa tutte le condizioni.
x ≡ 2 (mod 6) · x ≡ 4 (mod 9)
Per moduli non coprimi, i resti devono coincidere modulo il loro MCD.
24 / 30 · Trabocchetti senza soluzione nel vincolo dato
Un magazzino contiene meno di 1000 scatole; in gruppi da 11, 13 e 17 ne avanzano 4, 6 e 10.
x ≡ 4 (mod 11) · x ≡ 6 (mod 13) · x ≡ 10 (mod 17)
Cerca una soluzione nel limite indicato; se non esiste, scrivi “nessuna”. Meno di 1000
Risolvi prima senza vincoli; poi confronta il minimo positivo con l’intervallo richiesto.
27 / 30 · Trabocchetti senza soluzione nel vincolo dato
Il numero cercato è tra 200 e 400 inclusi.
x ≡ 1 (mod 7) · x ≡ 1 (mod 9) · x ≡ 1 (mod 11)
Cerca una soluzione nel limite indicato; se non esiste, scrivi “nessuna”. Da 200 · Fino a 400
Risolvi prima senza vincoli; poi confronta il minimo positivo con l’intervallo richiesto.
29 / 30 · Trabocchetti senza soluzione nel vincolo dato
Trova il più piccolo intero positivo che soddisfa tutte le condizioni.
x ≡ 2 (mod 4) · x ≡ 3 (mod 6) · x ≡ 4 (mod 8)
Per moduli non coprimi, i resti devono coincidere modulo il loro MCD.
Ogni sfida è generata sul momento: la risposta è calcolata, non letta da un elenco fisso.