Esercizi proposti: 20-04-2022
Lorenzo Guerra
guerra@axp.mat.uniroma2.it
1 Testo degli esercizi
1. Determinare esplicitamente una scomposizione in fattori irriducibili dei seguenti numeri interi:
i. 1144 ii. 3480 iii. 6762 iv. 5625
2. Dopo averne determinato la scomposizione in fattori primi, calcolare massimo comun divisore e minimo comune multiplo delle seguenti coppie di numeri:
i. 32, 36 ii. 720, 75 iii. 143, 338 iv. 192, 36
3. Calcolare, con l’algoritmo euclideo per divisioni successive, il massimo comun divisore tra le seguenti coppie di numeri a e b.
i. a = 1080, b = 375 ii. a = 2856, b = 1834 iii. a = 1009, b = 1861
4. Per ognuna delle tre coppie di numeri a e b dell’esercizio precedente, determinare esplicitamente una coppia di numeri interi (x, y) che soddisfa l’identità di Bézout ax + by = MCD(a, b).
5. Determinare tutte le soluzioni delle seguenti equazioni diofantee:
i 1080x − 375y = 45 ii 2856x + 1834y = −21 iii 1009x + 1861y = 2
[SUGGERIMENTO: sfruttare i risultati dell’esercizio precedente]
6. Dato un numero naturale n, indichiamo con Zn l’insieme {. . . , −3n, −2n, −n, 0, n, 2n, 3n, . . . } dei multipli interi di n. Inoltre, dati due sottoinsiemi A e B di Z, indichiamo con A+B l’insieme {x ∈ Z : ∃a ∈ A, b ∈ B : x = a + b} dei numeri interi che si possono scrivere come somma di un elemento di A e di un elemento di B, e con A · B l’insieme {x ∈ Z : ∃a ∈ A, b ∈ B : x = ab} dei numeri che si possono scrivere come prodotto di un elemento di A e di un elemento di B.
Verificare che le seguenti uguaglianze tra insiemi sono verificate per ogni n, m ∈ N:
i. Zn · Zm = Znm
ii. Zn + Zm = Z MCD{n, m}
iii. Zn ∩ Zm = Z mcm{n, m}
7. Sia n ≥ 1 un numero naturale positivo fissato. Definiamo Z[√
−n]come il sottoinsieme {a+ib√ n : a, b ∈ Z} dei numeri complessi che hanno parte reale intera e parte immaginaria che è un multiplo intero di√
n.
i. Verificare che il prodotto e la somma di due numeri qualunque in Z[√
−n] è ancora un elemento di Z[√
−n].
ii. Ricordiamo che l’insieme delle unità di Z[√
−n]è definito come U (Z[√
−n]) = {x ∈ Z[√
−n] : ∃y ∈ Z[√
−n], xy = 1}.
Determinare esplicitamente l’insieme U(Z[√
−n])al variare di n.
iii. Utilizzando la norma complessa, verificare che 2, 1+i√
7e 1−i√
7sono elementi irriducibili di Z[√
−7]. Trovare esplicitamente due fattorizzazioni distinte di 8 in Z[√
−7]. Dedurne che 2è irriducibile ma non primo in Z[√
−7].
iv. Dimostrare, adattando l’idea della dimostrazione vista a lezione per i numeri interi, che in Z[√
−n] ogni elemento si fattorizza come prodotto di elementi irriducibili. Dedurre dal punto precedente che tale fattorizzazione non è necessariamente unica, neanche a meno di unità.
[Nota aggiuntiva: al contrario, in Z[√
−1] la fattorizzazione in elementi irriducibili esiste ed è anche unica a meno di unità, ma la dimostrazione di questo fatto è troppo complicata per poter essere svolta come esercizio. n = 1 e n = 2 sono gli unici valori di n per cui questo succede.]
2 Svolgimento e soluzioni
1. In tutti i casi, possiamo procedere per divisioni successive un primo alla volta.
1144 : 2 = 572, 572 : 2 = 286, 286 : 2 = 143, 143 : 11 = 13. Dunque 1144 = 23· 11 · 13. iii 3480 : 2 = 1740, 1740 : 2 = 870, 870 : 2 = 435, 435 : 3 = 145, 145 : 5 = 29. Dunque
3480 = 23· 3 · 5 · 29.
iii 6762 : 2 = 3381, 3381 : 3 = 1127, 1127 : 7 = 161, 161 : 7 = 23. Dunque 6762 = 2 · 3 · 72· 23. iv 5625 : 3 = 1875, 1875 : 3 = 625, 625 : 5 = 125, 125 : 5 = 25, 25 : 5 = 5. Dunque
5625 = 32· 54.
2. La scomposizione in fattori primi si determina come nell’esercizio precedente. Dopo di che, il minimo comune multiplo sarà ottenuto moltiplicando tutti i fattori, ciascuno con l’esponente maggiore con cui appare. Invece il massimo comune divisore sarà ottenuto moltiplicando i fattori comuni, ciascuno con l’esponente minore con cui appare.
i. 32 = 25 e 36 = 22· 32. Quindi mcm(32, 36) = 25· 32= 288e MCD(32, 36) = 22= 4. ii. 720 = 24· 32· 5e 75 = 3 · 52. Quindi mcm(720, 75) = 24· 32· 52= 3600e MCD(720, 75) =
3 · 5 = 15.
iii. 143 = 11·13 e 338 = 2·132. Quindi mcm(143, 338) = 2·11·132= 3718e MCD(143, 338) = 13.
iv. 192 = 26·3e 36 = 22·32. Quindi mcm(192, 36) = 26·32= 576e MCD(192, 36) = 22·3 = 12. 3. i. 1080 : 375 = 2 con resto r1 = 330. 375 : 330 = 1 con resto r2= 45. 330 : 45 = 7 con resto
r3= 15. 45 : 15 = 3 con resto 0. Quindi MCD(1080, 375) = r3= 15.
ii. 2856 : 1834 = 1 con resto r1 = 1022. 1834 : 1022 = 1 con resto r2 = 812. 1022 : 812 = 1 con resto r3 = 210. 812 : 210 = 3 con resto r4 = 182. 210 : 182 = 1 con resto r5 = 28. 182 : 28 = 6con resto r6= 14. 28 : 14 = 0. Quindi MCD(2856, 1834) = r6= 14.
iii. 1861 : 1009 = 1 con resto r1 = 852. 1009 : 852 = 1 con resto r2 = 157. 852 : 157 = 5 con resto r3 = 67. 157 : 67 = 2 con resto r4 = 23. 67 : 23 = 2 con resto r5 = 21. 23 : 21 = 1 con resto r6= 2. 21 : 2 = 10 con resto r7 = 1. 2 : 1 = 2 con resto 0. Quindi MCD(1009, 1861) = r7= 1.
4. Sfruttiamo i calcoli svolti nell’esercizio precedente per scrivere ricorsivamente i vari resti parziali r1, r2, . . . fino a MCD(a, b) come combinazione lineare di a e b.
i. 1080 = 2 · 375 + r1, quindi r1 = 1080 − 2 · 375. 375 = r1+ r2, quindi r2 = 375 − r1 = 375 − (1080 − 2 · 375) = 3 · 375 − 1080. r1 = 7 · r2+ r3, quindi MCD(1080, 375) = r3 = r1− 7 · r2= (1080 − 2 · 375) − 7 · (3 · 375 − 1080) = 8 · 1080 − 23 · 375. Un’identità di Bézout è dunque data da
8 · 1080 − 23 · 375 = 15.
ii. 2856 = 1834+r1, quindi r1= 2856−1834. 1834 = r1+r2, quindi r2= 1834−(2856−1834) = 2 · 1834 − 2856. r1 = r2+ r3, quindi r3 = r1− r2 = (2856 − 1834) − (2 · 1834 − 2856) = 2·2856−3·1834. r2= 3·r3+r4, quindi r4= r2−2·r3= (2·1834−2856)−3·(2·2856−3·1834) = 11·1834−7·2856. r3= r4+r5, quindi r5= r3−r4= (2·2856−3·1834)−(11·1834−7·2856) = 9 · 2856 − 14 · 1834. r4 = 6 · r5 + r6, quindi MCD(2856, 1834) = r6 = r4− 6 · r5 = (11 · 1834 − 7 · 2856) − 6 · (9 · 2856 − 14 · 1834) = 95 · 1834 − 61 · 2856. Un’identità di Bézout è dunque data da
95 · 1834 − 61 · 2856 = 14.
iii. 1861 = 1009 + r1, quindi r1 = 1861 − 1009. 1009 = r1+ r2, quindi r2 = 1009 − r1 = 1009 − (1861 − 1009) = 2 · 1009 − 1861. r1 = 5 · r2 + r3, quindi r3 = r1 − 5 · r2 = (1861 − 1009) − 5 · (2 · 1009 − 1861) = 6 · 1861 − 11 · 1009. r2 = 2 · r3+ r4, quindi r4= r2−2·r3= (2·1009−1861)−2·(6·1861−11·1009) = 24·1009−13·1861. r3= 2·r4+r5, quindi r5= r3− 2 · r4= (6 · 1861 − 11 · 1009) − 2 · (24 · 1009 − 13 · 1861) = 32 · 1861 − 59 · 1009. r4 = r5+ r6, quindi r6 = r4− r5 = (24 · 1009 − 13 · 1861) − (32 · 1861 − 59 · 1009) = 83 · 1009 − 45 · 1861. r5 = 10 · r6+ r7, quindi MCD(1009, 1861) = r7 = r5− 10 · r6 = (32 · 1861 − 59 · 1009) − 10 · (83 · 1009 − 45 · 1861) = 482 · 1861 − 889 · 1009. Un’identità di Bézout è dunque data da
482 · 1861 − 889 · 1009 = 1.
5. Teniamo bene a mente i risultati degli esercizi 3 e 4.
i. Consideriamo l’equazione diofantea 1080x + 375y = 45. Ricordiamo che MCD(1080, 375) = 15. Siccome 15 divide 45 (perché 45 = 15 · 3), allora, per quanto avete visto a lezione, l’equazione ammette soluzioni.
Per prima cosa, troviamo una soluzione particolare (x, y) = (x0, y0) moltiplicando per 3 l’identità di Bézout determinata nell’esercizio precedente:
8 · 1080 − 23 · 375 = 15 ⇒ 3 · (8 · 1080 − 23 · 375) = 3 · 15 ⇒ 24 · 1080 − 69 · 375 = 45 Di conseguenza, x0= 24e y0= −69soddisfano 1080x0+ 375y0= 45.
Per determinare tutte le soluzioni dell’equazione diofantea data, osserviamo che se 1080x + 375y = 45, allora sottraendo membro a membro le due identità per (x, y) e (x0, y0)si ottiene
1080(x − x0) + 375(y − y0) = 0.
Per risolvere questa equazione diofantea ausiliaria, dividiamo entrambi i membri per il massimo comune divisore MCD(1080, 375) = 15:
1080(x − x0) + 375(y − y0)
15 = 0 ⇒ 1080
15 (x − x0) +375
15(y − y0) = 0
⇒ 72(x − x0) + 25(y − y0) = 0 ⇒ 72(x − x0) = −25(y − y0) Osserviamo che MCD(72, 25) = 1. Siccome 25 divide 72(x − x0) = −25(y − y0), ciò implica che 25 divide (x − x0). Avremo dunque che x = x0+ 25k per qualche k ∈ Z. Similmente 72 divide y − y0, dunque y = y0+ 72lper qualche l ∈ Z. Sostituendo nell’equazione originaria e ricordando che (x0, y0)è soluzione, otteniamo
1080 · (x0+ 25k) + 375 · (y0+ 72l) = 45 ⇔ 1080 · x0+ 375 · y0− 45 = 1080 · 25k + 375 · 72l
⇔ 27000k + 27000l = 0 ⇔ l = −k.
Dovremo quindi imporre l = −k e otterremo che tutte e sole le soluzioni dell’equazione diofantea 1080x + 375y = 45 sono le coppie di numeri interi nella forma
(x, y) = (x0+ 25k, y0− 72k) = (24 + 25k, −69 − 72k)per k ∈ Z.
ii. Consideriamo l’equazione diofantea 2856x+1834y = −21. Ricordiamo che MCD(2856, 1834) = 14. Siccome 14 non divide −21 (per esempio perché 2 è divisore di 14 ma non di −21), allora, per quanto avete visto a lezione, l’equazione non ammette nessuna soluzione.
iii. Consideriamo l’equazione diofantea 1009x + 1861y = 2. Ricordiamo che MCD(1080, 375) = 1. Siccome 1 divide 2, allora, per quanto avete visto a lezione, l’equazione ammette soluzioni.
Per prima cosa, troviamo una soluzione particolare (x, y) = (x0, y0) moltiplicando per 2 l’identità di Bézout determinata nell’esercizio precedente:
482 · 1861 − 889 · 1009 = 1 ⇒ 2 · (482 · 1861 − 889 · 1009) = 2 · 1 ⇒ 964 · 1861 − 1778 · 1009 = 2 Di conseguenza, x0= −1778e y0= 964soddisfano 1009x0+ 1861y0= 2.
Per determinare tutte le soluzioni dell’equazione diofantea data, osserviamo che se 1009x + 1861y = 2, allora sottraendo membro a membro le due identità per (x, y) e (x0, y0)si ottiene
1009(x − x0) + 1861(y − y0) = 0.
Osserviamo che MCD(1009, 1861) = 1. Siccome 1861 divide 1009(x − x0) = −1861(y − y0), ciò implica che 1861 divide (x − x0). Avremo dunque che x = x0+ 1861kper qualche k ∈ Z.
Similmente 1009 divide y − y0, dunque y = y0+ 1009l per qualche l ∈ Z. Sostituendo nell’equazione originaria e ricordando che (x0, y0)è soluzione, otteniamo
1009 · (x0+ 1861k) + 1861 · (y0+ 1009l) = 2 ⇔ 1009 · x0+ 1861 · y0− 2 = 1009 · 1861(k + l)
⇔ l = −k.
Dovremo quindi imporre l = −k e otterremo che tutte e sole le soluzioni dell’equazione diofantea 1009x + 1861y = 2 sono le coppie di numeri interi nella forma
(x, y) = (x0+ 1861k, y0− 1009k) = (−1778 + 1861k, 964 − 1009k)per k ∈ Z.
6. In tutti e tre i casi, dimostriamo che i due insiemi sono uguali verificando la doppia inclusione.
i. Se x ∈ Zn · Zm, allora ∃k, l ∈ Z tali che x = (kn) · (lm) = (kl)(nm) ∈ Znm. Di conseguenza Zn · Zm ⊆ Znm. Viceversa, se x ∈ Znm, allora ∃k ∈ Z tale che x = k(nm) = (kn) · m.
Siccome kn ∈ Zn e m ∈ Zm, ne deduciamo che Znm ⊆ Zn · Zm.
ii. Osserviamo che, per definizione, Zn + Zm = {c : c = xn + ym per qualche x, y ∈ Z}. In altre parole, Zn + Zm è l’insieme degli interi c tali che l’equazione diofantea xn + ym = c ha almeno una soluzione. Per quanto avete visto a lezione, ciò è verificato se e solo se c è un multiplo intero di MCD(n, m), ovvero se e solo se c ∈ Z MCD(n, m).
iii. Se x ∈ Zn ∩ Zm, allora ∃k, l ∈ Z tali che x = kn = lm. Essendo x un multiplo sia di n che di m, abbiamo che |x| ≥ mcm(n, m). Dimostriamo per assurdo che x ∈ Z mcm(n, m). Se ciò non fosse vero allora, operando la divisione con resto, otterremmo un’uguaglianza del tipo
x = a · mcm(n, m) + r con 1 ≤ r < mcm(n, m).
Siccome n divide sia x che mcm(n, m), n dividerà anche r = x−a·mcm(n, m). Similmente m divide r. Ma allora r è un multiplo comune di n e m non nullo tale che 0 < r < mcm(n, m), il che produce una contraddizione con la definizione di minimo comune multiplo. Ne con- segue che x ∈ Z mcm(n, m), ovvero che Zn ∩ Zm ⊆ Z mcm(n, m). L’inclusione opposta Z mcm(n, m) ⊆ Zn ∩ Zm è immediata, osservando che se x è un multiplo di mcm(n, m), allora x è un multiplo sia di n che di m.
7. i. Per definizione, gli elementi Z[√
−n]sono i numeri complessi nella forma x = a+ib√ n, dove a, b ∈ Z (i è l’unità immaginaria). Dati a, b, c, d ∈ Z, posti x = a + ib√
ne y = c + id√ n, la formula per la somma e moltiplicazione di numeri complessi dà
x + y = (a + c) + i(b + d)√ n x · y = (ac − bdn) + i(ad + bc)√
n, che sono ancora elementi di Z[√
−n].
ii. Consideriamo la norma complessa |x| = pRe(x)2+ Im(x)2. Osserviamo che
∀a, b ∈ Z : (a, b) 6= (0, 0) ⇒ |a + ib√ n| ≥ 1.
Dunque tutti gli elementi diversi da 0 di Z[√
−n] hanno norma maggiore o uguale a 1.
Se x ∈ U(Z[√
−n]), allora esiste y ∈ Z[√
−n] tale che x · y = 1. Dato che la norma è moltiplicativa, ne deduciamo che |x| · |y| = 1. Siccome, per quanto appena verificato,
|x| ≥ 1e |y| ≥ 1, dovrà verificarsi che |x| = |y| = 1. Abbiamo quindi dimostrato che U (Z[√
−n]) ⊆ {x ∈ Z[√
−n] : |x| = 1}.
Dobbiamo adesso distinguere due casi:
• Se n ≥ 2, allora {x ∈ Z[√
−n] : |x| = 1} = {1, −1}. Sia 1 che −1 sono unità in Z[√
−n], perché 1 · 1 = (−1) · (−1) = 1. Quindi
U (Z[√
−n]) = {1, −1}.
• Se invece n = 1, allora {x ∈ Z[√
−1] : |x| = 1} = {1, −1, i, −i}. Similmente al caso precedente, tutti questi quattro elementi sono unità in Z[√
−1]. Dunque U (Z[√
−1]) = {1, −1, i, −i}.
iii. Se 2 = x · y, con x, y ∈ Z[√
−7], allora |x| · |y| = 2. Ricordando che tutti gli elementi non nulli di Z[√
−7]hanno norma maggiore o uguale a 1, ne deduciamo che 1 ≤ |x| ≤ 2 e 1 ≤ |y| ≤ 2. D’altra parte, se scriviamo x = a+ib√
7con a, b ∈ Z, vediamo immediatamente che |x| =√
a2+ 7b2 ≥ max{|a|,√
7|b|}. In particolare, |x| ≤ 2 implica che |a| ≤ 2 e b = 0.
Di conseguenza x ∈ {−2, −1, 1, 2}. Se x = ±1, allora x ∈ U(Z[√
−7]). Altrimenti x = ±2, e quindi y = ±1 ∈ U(Z[√
−7]). Ne concludiamo che 2 è irriducibile.
Similmente, se 1 + i√
7 = x · y con x, y ∈ Z[√
−7], allora 1 ≤ |x| ≤ |1 + i√
7| = 2√ 2 e 1 ≤ |y| ≤ |1 + i√
7| = 2√
2. Analogamente a sopra, si verifica che gli unici elementi di Z[
√−7] aventi norma minore o uguale a 2√
2 sono ±1, ±2, ±i√
7, ±1 ± i√
7. Se x = ±1, allora x ∈ U(Z[√
−7]). Se x = ±2, allora |y| =√
2, ma nessuno degli elementi elencati sopra ha norma uguale a√
2: ne consegue che quest’eventualità non può verificarsi. Similmente, l’eventualità x = ±i√
7 non può verificarsi. Se invece x = ±1 ± i√
7, allora |x| = 2√ 2, il che obbliga ad avere |y| = 1, e quindi y ∈ U(Z[√
−7]). In conclusione, se x · y = 1 + i√ 7, allora uno tra x e y è un’unità, cioè 1 + i√
7 è irriducibile. Lo stesso argomento dimostra che 1 − i√
7 è irriducibile.
8 = 23 e 8 = (1 − i√
7) · (1 + i√
7)sono due fattorizzazioni irriducibili distinte di 8. 2 non può essere primo, perché 2 divide 8, ma non divide né 1 − i√
7 né 1 + i√
7, essendo questi ultimi due elementi irriducibili.
iv. È esattamente la stessa dimostrazione dell’esistenza di una fattorizzazione che avete visto a lezione per Z, solo che in questo caso tutti i numeri che compaiono nella dimostrazione sono elementi di Z[√
−n]invece che numeri interi e si procede per induzione forte sulla norma complessa (invece che sul valore assoluto di numeri interi).
