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.

 

Esempi su come risolvere le equazioni in interi.

Esempi su come risolvere le congruenze.

  Teoria