Trovare l’intero d=MCD(a,b) per le seguenti coppie di interi:
1) a=97929, b=8100;
2) a=20384, b=3575;
3) a=48400, b=5733;
4) a=32760, b=350;
trovare inoltre gli interi s,t tali che d si possa scrivere come combinazione lineare di a e b, cioè tali che d=sa+tb.
Svolgimento.
Come visto negli esempi, applichiamo direttamente l’algoritmo di Euclide, che consiste nell’applicazione ripetuta del lemma di divisione:
1) a=12765, b=4768.
Prendiamo gli interi a e b e calcoliamo
97929 : 8100 = 12 con resto 729,
quindi possiamo scrivere
97929 = 8100·12 + 729.
Iterando questo procedimento più volte fino ad ottenere un resto nullo, otteniamo la seguente serie di divisioni:
8100 = 729·11 + 81,
729 = 81·9 + 0.
L’ultimo resto non nullo è 81, quindi MCD(97929,8100)=81.
Per la seconda parte dell’esercizio, riprendiamo i passaggi ottenuti applicando l’algoritmo euclideo ed isolando il resto di ogni divisione. Partendo dall’ultimo e procedendo a ritroso, sostituiamo in ogni uguaglianza il valore del resto evidenziato nella precedente sino a risalire al passo iniziale.
Avremo:
729 = 97929 - 8100·12,
81 = 8100 - 729·11.
Sostituendo la prima nella seconda, si ha:
81 = 8100 – (97929 - 8100·12) ·11 = 8100·133 - 97929·11;
quindi i valori cercati sono t=133 e s=-11, infatti 81 = 97929·s+8100·t.
2) a=20384, b=3575.
Applicando lo stesso procedimento, abbiamo:
20384 = 3575·5 + 2509,
3575 = 2509·1 + 1066,
2509 = 1066·2 + 377,
1066 = 377·2 + 312,
377 = 312·1 + 65,
312 = 65·4 + 52,
65 = 52·1 + 13,
52 = 13·4 +0..
L’ultimo resto diverso da zero è 13, quindi si ha che MCD(20384, 3575)=13.
Ora calcoliamo i valori di s,t tali che 13 = 20384·s+3575·t procedendo come sopra.
Avremo:
2509 = 20384 - 3575·5,
1066 = 3575 - 2509·1,
377 = 2509 - 1066·2,
312 = 1066 - 377·2,
65 = 377 - 312·1,
52 = 312 - 65·4,
13 = 65 - 52·1.
Sostituiamo i resti calcolati nelle uguaglianze precedenti:
13 = 65 – (312 - 65·4) ·1 = 65·5 - 312·1,
13 = (377 - 312·1) ·5 - 312·1 = 377·5 - 312·6,
13 = 377·5 – (1066 - 377·2) ·6 = 377·17 - 1066·6,
13 = (2509 - 1066·2) ·17 - 1066·6 = 2509·17 - 1066·40,
13 = 2509·17 – (3575 - 2509·1) ·40 = 2509·57 - 3575·40,
13 = (20384 - 3575·5) ·57 - 3575·40 = 20384·57 - 3575·325,
da cui avremo che s=57 e t=-325.
3) a=48400, b=5733.
Acquistata familiarità con l’algoritmo, dovrebbe risultare immediato procedere con le seguenti divisioni:
48400 = 5733·8 + 2536,
5733 = 2536·2 + 661,
2536 = 661·3 + 553,
661 = 553·1 + 108,
553 = 108·5 + 13,
108 = 13·8 + 4,
13 = 4·3 + 1,
4 = 1·4 +0.
L’ultimo resto diverso da zero è 1, quindi a e b sono relativamente primi fra loro, cioè MCD(48400,5733)=1.
Ora, per calcolare calcoliamo i valori di s,t tali che 1 = 48400·s+5733·t e consideriamo:
2536 = 48400 - 5733·8,
661 = 5733 - 2536·2,
553 = 2536 - 661·3,
108 = 661 - 553·1,
13 = 553 - 108·5,
4 = 108 - 13·8,
1 = 13 - 4·3.
e sostituiamo i resti calcolati nelle uguaglianze precedenti:
1= 13 – (108 - 13·8) ·3 = 13·25 - 108·3,
1 = (553 - 108·5) ·25 - 108·3 = 553·25 - 108·128,
1 = 553·25 – (661 - 553·1) ·128 = 553·153 - 661·128,
13 = (2536 - 661·3) ·153 - 661·128 = 2536·153 - 661·587,
13 = 2536·153 – (5733 - 2536·2) ·587 = 2536·1327 - 5733·587,
13 = (48400 - 5733·8) ·1327 - 5733·587 = 48400·1327 - 5733·11203,
da cui avremo che s=1327 e t=-11203.
4) a=32760, b=350.
Ormai dovrebbe risultare semplice utilizzare l’algoritmo euclideo:
32760 = 350·93 + 210,
350 = 210·1 + 140,
210 = 140·1 + 70,
140 = 70·2 + 0.
L’ultimo resto diverso da zero è 70, quindi MCD(32760,350)=70.
Cerchiamo i valori di s,t tali che 70 = 32760·s+350·t, eseguendo:
210 = 32760 - 350·93,
140 = 350 - 210·1,
70 = 210 - 140·1,
e sostituiamo i resti calcolati nelle uguaglianze precedenti:
70 = 210 – (350 - 210·1) ·1 = 210·2 - 350·1,
70 = (32760 - 350·93) ·2 - 350·1 = 32760·2 - 350·187,
da cui avremo che s=2 e t=-187.
Esercizio n.2
Esistono altri valori per s e per t?
In caso di risposta affermativa, trovare almeno un’altra coppia di valori con le stesse caratteristiche per ogni punto dell’esercizio precedente.
Soluzione
a) In questo caso abbiamo trovato che a=97929, b=8100 e s=-11, t=133.
Nelle pagine di teoria, abbiamo studiato che ponendo s’=s+b, t’=t-a costruiamo altri coefficienti per la nostra combinazione lineare, quindi avremo:
s’=-11+8100=8089, t’=133-97929=-97796.
Verifichiamo questa soluzione: 97929·8089 - 97796·8100=792147681 – 792147600 = 81.
b) Ora abbiamo a=20384, b=3575, s=57, t=-325.
Procediamo direttamente con i calcoli:
s’=s+b=57+3575=3532, t’=t-a=-325-20384=-20709.
c) Ora abbiamo a=48400, b=5733, s=1327, t=-11203.
Procediamo direttamente con i calcoli:
s’=s+b=1327+5733=7060, t’=t-a=-11203-48400=-59603.
d) Nel quarto caso a=32760, b=350, s=2, t=-187.
Procediamo direttamente con i calcoli:
s’=s+b=2+350=352, t’=t-a=-187-32760=-32947.
Esempio n.3
Trovare, se esiste, una delle soluzioni in interi delle equazioni
1)
273x
+ 225y = 84,
2)
210x
+ 175y = 264,
3)
231x+225y=162,
4)
455x+126y=308.
Svolgimento.
Per risolvere l’esercizio, dobbiamo applicare la proposizione esposta nell’esempio n.2, ricordando però che la soluzione trovata non è unica, ma appartiene ad un insieme delle soluzioni.
Riassumiamo brevemente il procedimento: data l’equazione
ax+by=c
i) cerchiamo d=MCD(a,b);
ii) verifichiamo se d|c;
iii) in caso di risposta negativa, possiamo affermare che l’equazione non è risolubile, altrimenti cerchiamo s,t interi tali che d=sa+tb;
iv) poiché d|c, allora possiamo scrivere c=d·c’, con c’ intero e una soluzione dell’equazione è data da x0 = s·c’, y0 = t·c’, mentre ogni altra soluzione è del tipo
x = x0+b’·z, y = y0-a’·z per qualche z intero.
1) 273x + 225y =84.
Applicando il procedimento sopra, troviamo che
273 = 225·1 + 48,
225 = 48·4 + 33,
48 = 33·1 + 15,
33 = 15·2 + 3,
15 = 3·5 + 0,
quindi MCD(273, 225)=3.
Ora, poiché 3 divide 84, esistono delle soluzioni per l’equazione data, perciò procediamo cercando s,t tali che 3=273·s+225·t (avendo preso dimestichezza con le iterazioni, possiamo concederci di saltare il passaggio intermedio, dove isoliamo i resti delle divisioni):
3 = 33 - 15· 2 = 33 – (48 - 33·1) ·2= 33·3 - 48·2 ,
3 = (225 - 48·4) ·3 - 48·2 = 225·3 - 48·14,
3 = 225·36 – (273 - 225·1) ·14 =225·17 - 273·14,
da cui s=-14 e t=17.
Essendo 84 = 28· MCD(273, 225), una soluzione dell’equazione sarà quindi costituita da
x = -14·28=-392 e y = 17·28 = 476.
2) 210x + 175y = 264.
Analogamente, troviamo d = MCD(210,175) e verifichiamo che d divida 264 :
210 = 175·1 + 35,
175 = 35·5 + 0.
Essendo MCD(210,175)=35 e poiché 35 non divide 264, possiamo affermare che l’equazione non ammette soluzioni in numeri interi.
3) 231x + 225y = 162.
Utilizziamo ancora l’algoritmo euclideo per trovare il d=MCD(231,225):
231 = 225·1 + 6,
225 = 6·37 + 3,
6 = 3·2 + 0
da cui abbiamo che d=3 e, siccome 3 divide 162, possiamo procedere con la ricerca delle soluzioni:
3 = 225 - 6·37 = 225 – (231 - 225·1) ·37 = 225·38 - 231·37.
Quindi prendendo s=-37, t=38 ed essendo 3=54·MCD(231,225), abbiamo
x = -37·54 = 1998 e y = 38·54 =2052
come una soluzione dell’equazione data.
4) Cerchiamo il d=MCD(455,126):
455 = 126·3 + 77,
126 = 77·1 + 49,
77 = 49·1 + 28,
49 = 28·1 + 21,
28 = 21·1 + 7,
21 = 7·3 + 0,
da cui sappiamo che d=7, cioè l’ultimo resto diverso da zero.
Ora, siccome 7 divide 308, l’equazione ammette soluzioni e si può procedere cercando i valori s,t interi per cui 7 è combinazione lineare di 455 e 126:
7 = 28 - 21·1 = 28 – (49 - 28·1) ·1 = 28·2 - 49·1,
7 = (77 - 49·1) ·2 - 49·1 = 77·2 - 49·3,
7 = 77·2 – (126 - 77·1) ·3 = 77·5 - 126·3,
7 = (455 - 126·3) ·5 - 126·3 = 455·5 - 126·18.
Prendiamo c’=308/7=44 e poniamo s=5, t=-18, avremo che
x = 5·44=220, y = 18·44=792
sono una coppia di soluzioni per l’equazione data.
Esercizio n. 4
Trovare le soluzioni delle seguenti congruenze:
1)
207x
º 12
(mod 6);
2)
36x
º 10
(mod 12);
3)
211x
º 5 – 2x (mod 7);
4)
415x
º 21
(mod 18);
5)
132x
º 20
(mod 8).
Soluzione.
1) E’ immediato calcolare che MCD(207,6)=3 e, poiché 3 divide 12, allora dalla teoria studiata sappiamo che l’equazione iniziale è equivalente alla congruenza:
69x º 4 (mod 2),
e, presa x0 una soluzione, l’insieme delle soluzioni è del tipo
S={x0 +2k, con kÎZ e 0£x0<6}.
Grazie alla semplicità dei calcoli, possiamo procedere per tentativi:
per x0 = 0, si ha che 4 º 0 (mod 2),
per x0 = 1, si ha che 65 non è divisibile per 2.
A questo punto, abbiamo che l’insieme delle soluzioni è dato dalle classi di equivalenza
S ={[0]6, [2]6, [4]6}.
2) L’equazione non ammette soluzione perché il MCD(36,12)=12 e 10 non è divisibile per 12.
3) La congruenza iniziale è equivalente a
213x º 5 (mod 7)
e poiché 213 e 7 sono numeri relativamente primi fra loro, l’equazione ha una ed una sola classe di soluzione del tipo
S={x0 +mk, con m,kÎZ },
con x0 una soluzione dell’equazione.
Ora troviamo s,t interi tali che 1 si possa scrivere come combinazione lineare di 213 e 7:
213 = 7·30 + 3,
7 = 3·2 + 1,
3 = 3·1 + 0,
da cui risulta
1 = 7 - 3·2 = 7 – (213 - 7·30) ·2 = 7·61 - 213·2.
Quindi si ha che s = -2 e t = 61.
Dal fatto che 1 = 213·(-2) + 6·7. abbiamo come conseguenza che
213·(-2) º 1 (mod 7)
che, moltiplicato per il termine noto della congruenza di partenza, abbiamo
213·(-2·5) º 1·5 (mod 7).
Siccome -2·5 º 4 (mod 7), si ha che x=3 è la soluzione cercata e l’insieme delle soluzioni è
S = {[4]7}.
4) Cerchiamo il MCD(415,18) per vedere se la congruenza ammette soluzioni e, in caso affermativo, individuiamo da quante classi di congruenza è composto l’insieme delle soluzioni:
415 = 18·23 + 1,
18 = 1·18 + 0.
Essendo i due numeri relativamente primi fra loro, si ha che, , presa x0 una soluzione, l’insieme delle soluzioni S è composto dalla sola classe di congruenza [x0]18.
E’ immediato che, essendo 1 = 415·1 - 18·23, risulta
415·1 º 1 (mod 18)
che, moltiplicato per il termine noto 21, diventa
415·(1·21) º 1·21 (mod 18),
da cui otteniamo che 21 º 3 (mod 18).
Presa x=3 la soluzione cercata, avremo S = {[3]18}.
5) Poiché è facile trovare che MCD(132,20) = 4 e 4 divide 28, possiamo direttamente considerare la congruenza equivalente
33x º 7 (mod 2).
Quindi, presa x0 una soluzione, l’insieme delle soluzioni è del tipo
S={x0 +2k, con kÎZ e 0£x0<8}.
Grazie alla semplicità dei calcoli, possiamo procedere per tentativi:
per x0 = 0, si ha che 7 non è divisibile per 2,
per x0 = 1, si ha che 33-7 = 26 è congruo a 2,
perciò, abbiamo che l’insieme delle soluzioni è dato dalle classi di equivalenza
S ={[1]8, [3]8, [5]8, [7]8}.
Esercizio n. 5
Dimostrare che se p è primo, p>3, allora pº1 (mod 6) oppure pº5 (mod 6).
Soluzione.
Lo spazio Z6 è costituito dalle seguenti classi di congruenza:
Z6 = {[0]6, [1]6, [2]6, [3]6, [4]6, [5]6}.
Preso p primo diverso da 2 e da 3, necessariamente il MCD(p,6)=1, quindi le uniche classi di congruenza che potrebbero costituire lo spazio delle soluzioni in Z6 di una congruenza sono [1]6 o [5]6.
Esercizio n. 6
Provare che 7x º x (mod 4) se e solo se x è pari.
Soluzione.
Dimostriamo questa affermazione verificando separatamente le due implicazioni.
Attraverso pochi scambi logici, proviamo che se 7x º x (mod 4) allora x è pari:
[7]4 [x]4 = [x]4
[3]4[x]4
- [x]4 = [0]4
[2x]4 = [0]4.
L’ultima espressione è verificata quando 4 divide 2x, cioè quando x è un numero divisibile per 2, quindi pari.
Viceversa, dimostriamo che se x è pari, allora 7x º x (mod 4).
Se x è pari, allora si può esprimere come x=2k, con k intero, quindi per le proprietà delle congruenze avremo che
[7]4[x]4 = [7]4[2k]4
= [3]4[2k]4 = [3]4[2]4[k]4
=
= [6]4[k]4 = [2]4[k]4
= [2k]4 = [x]4,
quindi 7x sono congrue a x modulo 4.
Esercizio n. 7
Provare che per ogni intero x, x2 º x (mod 2).
Soluzione.
Verifichiamo che l’equazione è verificata sia che x sia pari, sia che sia dispari.
Prendiamo x pari, allora potremo scrivere x=2k, con k intero e avremo che
4k2 º 2k (mod 2),
che è verificato se e solo se 2 divide 4k2-2k, che è sempre vero perché, raccogliendo un 2 al secondo membro, otteniamo che 2 divide 2(2k2-k).
Inoltre, se x è dispari, allora x=2k+1, con k intero e avremo che
(2k+1)2 º 2k+1 (mod 2),
4k2+4k+1 º 2k+1 (mod 2),
verificata se 2 divide 4k2+4k+1 - 2k-1.
Svolgendo i calcoli, quest’ultima è equivalente a 2(2k2+k), sempre divisibile per 2.
Esercizio n. 8
Si prenda un numero m=an..a0 in rappresentazione decimale tale che m abbia tutte le cifre ai , per i = 0,..,n uguali. E’ vero che m è sempre divisibile per 11?
Soluzione.
Ricordiamo che un numero m=an..a0 in rappresentazione decimale è divisibile per 11 se e solo se 11 divide la somma a0-a1+a2-..+(-1)nan.
Quindi la successione (a2n-a2n-1) dei coefficienti di m deve essere divisibile per 11, e questo è verificato se m ha un numero pari di coefficienti, mentre se m contiene un numero dispari di coefficienti non è divisibile per 11.
Ad esempio, prendiamo l’intero 9 come coefficiente di m,
se n=2, m=99 è divisibile per 11,
se n=3, m=999 non è divisibile per 11,
se n=4, m=9999 è divisibile per 11, e così via.