Esempi
Esempio n.1
Trovare l’intero d=MCD(a,b) delle seguenti coppie di interi:
1) a=12765, b=4768;
2) a=11368, b=3430;
e gli interi s,t tali che d si possa scrivere come combinazione lineare di a e b, cioè tali che d=sa+tb.
Svolgimento.
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
12765 : 4768 = 2 con resto 3229,
quindi possiamo scrivere
12765 = 4768·2 + 3229.
Iterando questo procedimento più volte fino ad ottenere un resto nullo, otteniamo la seguente serie di divisioni:
4768 = 3229·1 + 1539,
3229 = 1539·2 + 151,
1539 = 151·10 + 29,
151 = 29·5 + 69,29 = 6·4 + 5,
6 = 5·1 + 1,
5 = 1·5 + 0.
L’ultimo resto non nullo è 1, quindi MCD(12765,4768)=1, cioè i due numeri sono relativamente primi fra loro.
Per la seconda parte dell’esercizio, riprendiamo i passaggi ottenuti applicando l’algoritmo euclideo isolando il resto di ogni divisione e, 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:
3229 = 12765 - 4768·2,
1539 = 4768 - 3229·1,
151 = 3229 - 1539·2,
29 = 1539 - 151·10,
6 = 151 - 29·5,
5 = 29 - 6·4,
1 = 6 - 5·1.
Sostituiamo la penultima nella precedente, si ha:
1 = 6 – (29 - 6·4) ·1 = 6·5 -29 ·1
e iteriamo questo procedimento:
1 = (151 - 29·5) ·5 - 29·1 = 151·5 - 29·26,
1 = 151·5 – (1539 - 151·10) ·26 = 151·265 - 1539·26,
1 = (3229 - 1539·2) ·265 – 1539·26 = 3229·265 - 1539·556,
1 = 3229·265 – (4768 - 3229·1) ·556 = 3229·821 - 4768·556,
1 = (12765 – 4768·2) ·821 – 4768·556 = 12765·821 - 4768·2198.
Quindi i valori cercati sono s=821 e t=-2198, infatti 1 = 12765·s+4768·t.
2) a=11368, b=3430.
Procedendo in modo analogo all’esempio precedente, abbiamo:
12804 = 3432·3 + 2508,
3432 = 2508·1 + 924,
2508 = 924·2 + 660,
924 = 660·1 + 264,
660 = 264·2 + 132,
264 = 132·2 + 0.
L’ultimo resto diverso da zero è 132, quindi si ha che MCD(12804, 3432)=132.
Ora calcoliamo i valori di s,t tali che 132 = 12804·s+3432·t procedendo come nel caso precedente.
Avremo:
2508 = 12804 - 3432·3,
924 = 3432 - 2508·1,
660 = 2508 - 924·2,
264 = 924 - 660·1,
132 = 660 - 264·2
e sostituiamo i resti calcolati nelle uguaglianze precedenti:
132 = 660 – (924 - 660·1) ·2 = 660·3 - 924·2,
132 = (2508 - 924·2) ·3 - 924·2 = 2508·3 - 924·8,
132 = 2508·3 – (3432 - 2508·1) ·8 = 2508·11 - 3432·8,
132 = (12804 - 3432·3) ·11 - 3432·8 = 12804·11 - 34732·41
da cui avremo che s=11 e t=-41.
Esempio n.2
Trovare, se esiste, una delle soluzioni in interi delle equazioni
1) 216x + 117y = 27,
2) 108x + 60y = 55.
Svolgimento.
Per risolvere l’esercizio dobbiamo applicare la seguente proposizione:
Proposizione. Dati a,b,c interi, l’equazione
ax+by=c
ha soluzione in numeri interi se e solo se MCD(a,b) divide c.
Ora, posto d=MCD(a,b), dalla teoria studiata sappiamo che d|a e d|b, quindi esistono due interi p e q tali che a=p·d e b=q·d e, se d|c, esiste anche un r intero tale che c=r·d.
Poiché possiamo esprimere d come combinazione lineare di a e b, ne segue che, se d|c, abbiamo:
d = sa+tb , e quindi c=r×d=r× sa+r× tb
da cui risulta che una soluzione dell’equazione è data da x0 = s·r, y0 = t·r, mentre ogni altra soluzione è del tipo
x = x0+b·z, y = y0-a·z per qualche z intero.
1) 216x + 117y =27.
Applicando questa proposizione al nostro esempio, otteniamo che
216 = 117·1 + 99,
117 = 99·1 + 18,
18 = 9·2 +0,
quindi MCD(216, 117)=9.
Ora, poiché 9|27, esistono delle soluzioni per l’equazione data, perciò procediamo cercando s,t tali che 9=216·s+117·t:
99 = 216 - 117·1,
18 = 117 - 99·1,
9 = 99 - 18·5.
Svolgendo i calcoli, otteniamo che
9 = 99 – (117 - 99·1) ·5 = 99·6 - 117·5,
9 = (216 - 117·1) ·6 - 117·5 = 216·6 - 117·11,
da cui s=6 e t=-11.
Essendo 27 = 3· MCD(216, 117), una soluzione dell’equazione sarà quindi costituita da
x = 6·3=18 e y = -11·3 = -33.
2) 108x + 60y = 55.
Analogamente, troviamo d = MCD(108,60) e verifichiamo che d divida 55 :
108 = 60·1 + 48,
60 = 48·1 + 12,
48 = 12·4 + 0.
Essendo MCD(108,60)=12 e poiché 12 non divide 55, possiamo affermare che l’equazione non ammette soluzioni in numeri interi.
Esempio n.3
Trovare le soluzioni delle seguenti congruenze:
1) 12x º 7 (mod 3);
2) 313x º 12 – 2x (mod 16);
3) 10x º 2 (mod 6).
Svolgimento.
1) Poiché si ha [12]3= [0] 3 , l‘equazione e’ equivalente a 0x º 7 (mod 3); che ovviamente non ammette soluzioni.
2) L’equazione è equivalente a
315x º 12 (mod 16)
e siccome MCD(315,16)=1, allora l’equazione ha una ed una sola classe di soluzioni del tipo
S = {x0 + 16z tali che zÎZ}
con x0 una soluzione dell’equazione.
Troviamo gli interi s,t tali che 1 = 315·s+16·t:
315 = 16·19 + 11,
16 = 11·1 + 5,
5 = 5·1 + 0,
da cui otteniamo i seguenti resti:
11 = 315 - 16·19,
5 = 16 - 11·1,
1 = 11 - 5·2,
che sostituiti nell’equazione danno
1 = 11 – (16 - 11·1) ·2 = 11·3 - 16·2,
1 = (315 - 16·19) ·3 - 16·2 = 315·3 - 16·59.
Quindi 1 = 315·3 - 16·59 che ha come conseguenza
315·3 º 1 (mod 16),
che, moltiplicato per il termine noto dell’equazione iniziale, si ha
315·(3·12) º 1·12 (mod 16) da cui 315·(3·12) º12 (mod 16) .
Allora, siccome 3·12 º 4 (mod 16), si ha che x=4 è la soluzione richiesta.
3)Poiché il MCD(10,6)=2 e 2 divide 2, allora l’equazione di partenza è equivalente alla congruenza
5x º 1 (mod 3)
e, presa x0 una soluzione, l’insieme delle soluzioni è del tipo
S={x0 + 3k, con kÎZ e 0£x0<6}.
Siccome la semplicità dei calcoli lo consente, possiamo trovare la soluzione procedendo per tentativi, quindi
per x0=0, abbiamo che 0-1=-1 non divisibile per 3,
per x0=1, abbiamo che 5-1=4 non divisibile per 3,
per x0=2, abbiamo che 10-1=9 che, essendo divisibile per 3, in quanto 9 º 0 (mod 3).
Quindi abbiamo che l’insieme delle soluzioni è dato dalle classi di equivalenza:
S={[2]6, [5]6}.
Teoria