Esercizi sul M.C.D. e Classi Resto

Esercizio 1. Trovare il massimo comun divisore di 444 e 100.Svolgimento. Utilizzando l’algoritmo di Euclide si ha:444 = 100 · 4 + 44100 = 44 · 2 + 1244 = 12 · 3 + 812 = 8 · 1 + 48 = 4 · 2 + 0L’ultimo resto non nullo è il massimo comun divisore. MCD(444; 100) = 4.

Esercizio 2. Trovare MCD(220, 121) e scriverlo come combinazione lineare a coef-ficienti interi di 220 e 121.Svolgimento. Utilizzando l’algoritmo di Euclide si ha:220 = 121 · 1 + 99121 = 99 · 1 + 2299 = 22 · 4 + 1122 = 11 · 2 + 0L’ultimo resto non nullo è il massimo comun divisore. MCD(220; 121) = 11.Esplicitando i resti nei passaggi dell’algoritmo, si ricava:99 = 220− 12122 = 121− 99 = 121− 220 + 121 = 2 · 121− 22011 = 99− 22 · 4 = (220− 121)− (2 · 121− 220) · 411 = 220− 121− 8 · 121 + 4 · 22011 = 5 · 220− 9 · 121il che verifica l’identità di Bezout.

Esercizio 3. Stabilire se l’equazione diofantea 35x + 28y = 14 ammette soluzioni.Svolgimento. Utilizziamo l’algoritmo di Euclide per calcolare MCD(35, 28).35 = 28 · 1 + 728 = 7 · 4 + 0.L’ultimo resto non nullo è 7, quindi il massimo comun divisore divide 14, e l’equazione ammette soluzioni.

Esercizio 4. Utilizzando l’algoritmo di Euclide, trovare il massimo comun divisoredelle seguenti coppie di interi:

(680; 324) (2240; 1024) (1134; 525)e verificare l’identità di Bezout per la prima delle tre coppie.

Esercizio 5. Dire, motivando la risposta, quali delle seguenti equazione diofanteeammettono soluzioni:324x + 81y = 26 324x + 81y = 27 36x + 90y = 54.

Esercizio 6. Calcolare il minimo comune multiplo delle seguenti coppie di interi:(120; 32) (222; 259).

Esercizio 7. Sia n = 2379876328939. Trovare il resto, nella divisione per 4, di n edi n2.Svolgimento. Poichè n − 39 = 2379876328900 è multiplo di 100, e quindi è anchemultiplo di 4, risulta n ≡ 39 ≡ 3(mod4). Inoltre, siccome n è dispari, possiamoscrivere n = 2k + 1 per un opportuno intero k. Quindi

1

2

n2 = (2k + 1)2 = 4k2 + 4k + 1n2 − 1 = 4(k2 + k) n2 ≡ 1(mod4).

Esercizio 8. Calcolare il resto, nella divisione per 10, di 351.Svolgimento. Innanzitutto osserviamo che34 = 81 ≡ 1(mod10) e quindi351 = 348 · 33 = (34)12 · 33 = (81)12 · 27.(81)12 è congruo a (1)12 = 1 modulo 10.

351 ≡ 27(mod10)

351 ≡ 7(mod10).

Esercizio 9. Calcolare il resto, nella divisione per 5, di 228.Suggerimento. 228 = (28) · (112)4.

Esercizio 10. Calcolare il resto, nella divisione per 7, di 71127.

Esercizio 11. Risolvere i seguenti sistemi di equazioni congruenziali:

(a)

{x ≡ 7 mod 9x ≡ 3 mod 5

(b)

{7x ≡ 2 mod 85x ≡ 4 mod 7

(c)

5x ≡ 2 mod 78x ≡ 11 mod 137x ≡ 5 mod 11

.

Soluzioni. (a) 43 mod 45. (b) 54 mod 56 (c) 601 mod 7 · 11 · 13.