Bezout e diofantee

tags: md

Divisione euclidea

Teorema

Teorema della divisione euclidea
Dati

$a,b$ interi con

$b>0$ esistono, e sono unici, due interi

$q$ (quoziente) ed

$r$ (resto), con

$$a=bq+r$$

$$0\le r<b$$

Osservazione

Facciamo ancora un altro esempio. Se

$a=-15$ e

$b=7$, la divisione euclidea di

$a$ per

$b$ è:

$$-15=7(-3)+6$$

con quoziente

$q=-3$ e resto

$r=6$.

L'uguaglianza

$-15=7(-2)-1$ per quanto vera, non è la divisione euclidea.

Dimostrazione

Consideriamo il caso

$a\ge 0$ (se

$a<0$ la dimostrazione è analoga). Possiamo utilizzare il principio del minimo. Consideriamo l'insieme

$$Q=m\in \mathbb{N}|mb\ge a$$
Tale insieme è un sottoinsieme di

$\mathbb{N}$ non vuoto (visto che

$b>0$ e dunque

$b\ge 1$,

$Q$ contiene infiniti interi maggiori di

$a$). Per il principio del minimo

$Q$ ammette un minimo, appunto,che chiameremo

$q$.
Ora, se

$qb=a$ abbiamo già trovato la nostra divisione euclidea:

$$a=bq+0$$
Se invece

$qb>a$ allora deve valere

$(q-1)b<a$, altrimenti il minimo di

$Q$ sarebbe

$q-1$ e non

$q$. La differenza

$r=a-(q-1)b$ soddisfa

$0<r<b$ e dunque la divisione euclidea che cercavamo è

$$a=(q-1)b+r$$
Il procedimento che abbiamo seguito dimostra in realtà anche l'unicità del quoziente e del resto. Per una qualunque altra scelta del quoziente diversa da

$q$, infatti, si osserva facilmente che il resto ottenuto non soddisferebbe la richiesta

$0\le r<b$.

MCD

Notazione

Ricordiamo che, dati due numeri interi

$c$ e

$d$, diciamo che

$c$ divide

$d$ se esiste un numero intero

$k$ tale che

$ck=d$. In tal caso scriviamo

$c|d$ o

$c/d$

Definizione

Siano

$a,b\in \mathbb{Z}$, con almeno uno dei due diverso da

$0$ (questo si può scrivere così:

$(a,b)\in \mathbb{Z}\times \mathbb{Z}-\{(0,0)\}$). Allora il “massimo comun(e) divisore” di

$a$ e

$b$ è l'unico intero positivo d tale che:

• $d|a$ e
  $d|b$

• $d$ è più grande di ogni altro divisore comune di
  $a$ e
  $b$:
  se
  $c|a$ e
  $c|b$, allora deve essere
  $c\le d$

Indicheremo il massimo comun divisore di

$a$ e

$b$ come

$MCD(a,b)$
Talvolta, quando è chiaro che stiamo considerando il massimo comun divisore, ometteremo

$MCD$ e scriveremo soltanto

$(a,b)$
Se vale che

$MCD(a,b)=1$ diremo che

$a$ e

$b$ sono primi tra loro o coprimi.

Osservazione

La definizione è ben posta. Infatti almeno un divisore comune positivo di

$a$ e

$b$ esiste sempre (il numero

$1$) e dunque l'insieme di tutti i divisori comuni positivi è un sottoinsieme di

$\mathbb{N}$ non vuoto e finito.
Si noti a questo proposito che i suoi elementi sono tutti minori o uguali al minimo fra

$|a|$ e

$|b|$.
Allora esiste unico il massimo di tale insieme, che è appunto il

$MCD(a,b)$

Si vede subito che:

$$MCD(a,b)=MCD(b,a)=MCD(|a|,|b|)$$

e anche che:

$$MCD(a,a)=MCD(a,0)=|a|$$

Algoritmo di Euclide

Supponiamo di voler trovare il

$MCD$ di due numeri

$a,b\in \mathbb{Z}$ non entrambi nulli.
Se uno dei due numeri (per esempio

$a$) è

$0$, allora sappiamo subito dire che

$MCD(0,b)$ è uguale al valore assoluto

$|b|$ di

$b$.
Occupiamoci dunque del caso in cui entrambi i numeri sono diversi da zero.
Se vale per esempio che

$|a|\ge |b|>0$ applichiamo l'algoritmo direttamente al calcolo di

$MCD(|a|,|b|)$.

Cominciamo con la divisione euclidea di

$|a|$ per

$|b|$:

$|a|=|b|q+r_1$ con

$0\le r_1<|b|$

Se

$r_1=0$ abbiamo finito, perché possiamo concludere subito che

$|b|=MCD(|a|,|b|)=MCD(a,b)$
Altrimenti proseguiamo con delle divisioni euclidee successive finché non si trova un resto uguale a

$0$:

$|a|=|b|q+r_1$ con

$0<r_1<|b|$

$|b|=r_1\cdot q_1+r_2$ con

$0<r_2<r_1$

$r_1=r_2{q}_2+r_3$ con

$0<r_3<r_2$

$\cdots \cdots \cdots$

$r_{n-2}=r_{n-1}{q}_{n-1}+r_n$ con

$0<r_n<r_{n-1}$

$r_n-1=r_n{q}_n+0$

A questo punto concludiamo che

$r_n=MCD(|a|,|b|)=MCD(a,b)$

Dimostrazione

Per dimostrare che il metodo dell'algoritmo funziona, dobbiamo rispondere a due domande.

1. Perché l'algoritmo termina sempre entro un numero finito di passi? Perché ad ogni passo otteniamo un resto
   $r_j$ che è un numero naturale ed è strettamente minore del resto precedente. Se potessimo continuare all'infinito, l'insieme dei resti contraddirebbe il principio del minimo (sarebbe un sottoinsieme di
   $\mathbb{N}$ non vuoto senza minimo).
2. Perché
   $r_n$ è proprio il MCD che cercavamo? Il punto cruciale, é dato dal seguente teorema

Teorema

Dati

$a,b,c,d\in \mathbb{Z}$ con almeno uno fra

$a,b$ non nullo e almeno uno fra

$b,d$ non nullo, che soddisfano

$$a=bc+d$$
allora vale che

$MCD(a,b)=MCD(b,d)$.

Dimostrazione

La strategia è la seguente: mostreremo che l'insieme

$DIV(a,b)$ dei divisori comuni positivi di

$a$ e

$b$ è uguale all'insieme

$DIV(b,d)$ dei divisori comuni positivi di

$b$ e

$d$. A quel punto avremo finito, perché

$MCD(a,b)$ è il massimo elemento di

$DIV(a,b)$ e

$MCD(b,d)$ è il massimo elemento di

$DIV(b,d)$, ossia dello stesso insieme. Dimostriamo dunque che

$DIV(a,b)\subseteq DIV(b,d)$ (l'inclusione opposta si di-mostra in maniera analoga). Prendiamo un elemento

$\gamma \in DIV(a,b)$. Visto che

$\gamma |a$ e

$\gamma |b$ allora

$\gamma$ divide anche

$a-bc$ ovvero

$\gamma$ divide

$d$. Dunque

$\gamma \in DIV(b,d)$, come volevamo dimostrare.

Applicando questo lemma ai vari passaggi del nostro algoritmo di Euclide otteniamo:

$$MCD(|a|,|b|)=MCD(|b|,r_1)=MCD(r_1,r_2)=MCD(r_2,r_3)=\dots$$
e così via (questo "così via" nasconde una facile induzione!) fino a

$$...=MCD(r_{n-2},r_{n-1})=MCD(r_{n-1},r_n)$$
Ma

$MCD(r_{n-1},r_n)$ è proprio

$r_n$, visto che

$r_n|r_{n-1}$. Ripercorrendo tutta la catena di uguaglianze scopriamo di aver dimostrato che

$$MCD(|a|,|b|)=r_n$$
e dunque ora sappiamo perché l'algoritmo di Euclide funziona!

Identità di Bezout

Teorema

Lemma di Bezout o Identità di Bezout
Dati due numeri interi

$a$ e

$b$ con

$(a,b)\ne (0,0)$, esistono due numeri interi

$m$ e

$n$ tali che

$$MCD(a,b)=am+bn$$

Si dice che

$MCD(a,b)$ può essere espresso come combinazione lineare a coefficienti interi di

$a$ e di

$b$

Osservazione

Il teorema dice che esistono

$m$ ed

$n$ tali che

$MCD(a,b)=am+bn$, ma non dice che sono unici. Infatti, come risulterà dalla teoria delle equazioni diofantee lineari, ci sono infinite scelte possibili di una coppia (

$m$,

$n$) tale che

$MCD(a,b)=am+bn$.

Dimostrazione

Consideriamo l'insieme

$C{L}^{+}(a,b)$ di tutte le possibili combinazioni lineari positive a coefficienti interi di

$a$ e

$b$, ossia

$$C{L}^{+}(a,b)=\{ar+bs|r\in \mathbb{Z},s\in \mathbb{Z},ar+bs>0\}$$
Tale insieme è non vuoto. Infatti supponiamo che

$a\ne 0$ (altrimenti si fa lo stesso ragionamento con

$b$). Allora si trovano degli elementi dell'insieme

$C{L}^{+}(a,b)$ per esempio scegliendo

$s=0$ e

$r$ tale che

$ra>0$. Già così abbiamo esibito infiniti elementi nell'insieme

$C{L}^{+}(a,b)$. Inoltre

$C{L}^{+}(a,b)\subseteq \mathbb{N}$.
Dunque, per il principio del buon ordinamento,

$C{L}^{+}(a,b)$ ammette minimo.
Sia

$d$ tale minimo: in particolare, dato che

$d\in C{L}^{+}(a,b)$, esistono un

$m\in \mathbb{Z}$ ed un

$n\in \mathbb{Z}$ tali che

$$d=am+bn$$
La dimostrazione del teorema si conclude ora mostrando che

$d=MCD(a,b)$. Infatti

$d$ soddisfa le proprietà del massimo comune divisore, ossia:

• $d|a$ e
  $d|b$
• se
  $c|a$ e
  $c|b$ allora
  $c\le d$

Per il primo punto, facciamo la divisione euclidea fra

$a$ e

$d$. Sarà

$a=qd+r$ con

$0\le r<d$. Allora

$$a=q(am+bn)+r$$
da cui

$$r=(-qm+1)a+(-qn)b$$
Ma allora

$r$ si esprime come combinazione lineare a coefficienti interi di

$a$ e di

$b$. Se fosse

$r>0$ avremmo che

$r\in C{L}^{+}(a,b)$ per definizione di

$C{L}^{+}(a,b)$. Questo non può succedere perché

$0\le r<d$ e

$d$ era stato scelto come minimo elemento di

$C{L}^{+}(a,b)$. Dunque deve essere

$r=0$. Questo vuol dire che

$a=qd+0$, ossia che

$d|a$. Allo stesso modo si dimostra che

$d|b$.
Il secondo punto è immediato. Infatti se

$c|a$ e

$c|b$ allora

$c|am+bn$ cioè

$c|d$, in particolare

$c\le d$.

Corollario

Dati due numeri interi

$a$ e

$b$ con

$(a,b)\ne (0,0)$, se

$c|a$ e

$c|b$, allora non solo

$c\le MCD(a,b)$ ma più precisamente vale che

$c|MCD(a,b)$

Teorema

Dati due numeri interi

$a$ e

$b$ con

$(a,b)\ne (0,0)$,

$MCD(a,b)$ è il più piccolo numero intero positivo ottenibile come combinazione lineare intera di

$a$ e di

$b$.

Corollario

Presi due numeri interi

$a$ e

$b$ non entrambi nulli, se li dividiamo per il loro massimo comun divisore

$MCD(a,b)$ otteniamo due numeri

$$a^{\prime }=\frac{a}{MCD(a,b)}{b}^{\prime }=\frac{b}{MCD(a,b)}$$

che sono primi fra loro.

Dimostrazione

Si può vedere in due modi, entrambi molto semplici.
Il primo modo è il seguente: se ci fosse un divisore comune

$d>1$ di

$a\prime$ e

$b\prime$, allora

$d\cdot MCD(a,b)$ dividerebbe sia

$a$ sia

$b$ e sarebbe più grande di

$MCD(a,b)$, assurdo.
Il secondo parte dall'identità di Bezout

$$MCD(a,b)=am+bn$$
Dividendo per

$MCD(a,b)$ si ottiene

$$1=a\prime m+b\prime n$$
e dunque

$1$ è il più piccolo numero intero positivo ottenibile come combinazione lineare intera di

$a\prime$ e di

$b\prime$.

Teorema

Siano

$a,b,c\in \mathbb{Z}$. Se

$a|bc$ e

$MCD(a,b)=1$ allora

$a|c$.

Dimostrazione

Visto che

$MCD(a,b)=1$ allora per l'Identità di Bezout possiamo trovare

$m,n\in \mathbb{Z}$ tali che

$$1=an+bm$$
Moltiplicando entrambi i membri per

$c$ otteniamo:

$$c=acn+bcm$$
Questo ci permette di concludere che

$a|c$. Infatti

$a|acn$ (ovviamente) e

$a|bcm$ (visto che

$a|bc$ per ipotesi), dunque

$a$ divide la somma

$acn+bcm$ che è uguale a

$c$

Osservazione

La dimostrazione precedente è breve ma non è banale. Il teorema è alla base del fatto che la fattorizzazione in prodotto di primi di un numero intero è unica.

Ottenere l'Identità di Bezout

Prendiamo per esempio

$a=1020$ e

$b=351$ e calcoliamo

$MCD(a,b)$ tramite l'algoritmo di Euclide:

$$\begin{gathered} 1020=351\cdot 2+318 \\ 351=318\cdot 1+33 \\ 318=33\cdot 9+21 \\ 33=21\cdot 1+12 \\ 21=12\cdot 1+9 \\ 12=9\cdot 1+3 \\ 9=3\cdot 3+0 \end{gathered}$$

Dunque abbiamo trovato che

$MCD(1020,351)=3$. Scriviamo adesso di nuovo tutte le equazioni dell'algoritmo (tranne l'ultima) ponendo a sinistra i resti:

$$\begin{gathered} 318=1020-351\cdot 2 \\ 33=351-318\cdot 1 \\ 21=318-33\cdot 9 \\ 12=33-21\cdot 1 \\ 9=21-12\cdot 1 \\ 3=12-9\cdot 1 \end{gathered}$$

Ora ripercorriamo l'algoritmo "a rovescio": cominciamo da

$3=12-9\cdot 1$. Ricordiamo che come obiettivo finale vogliamo trasformare questa equazione in una del tipo

$3=1020m+351n$

Cominciamo utilizzando l'equazione

$9=21-12\cdot 1$. Possiamo usarla per sostituire il

$9$ ed ottenere

$3$ espresso come combinazione lineare di

$12$ e di

$21$:

$3=12\cdot 2-21=(33-21\cdot 1)\cdot 2-21=33\cdot 2-21\cdot 3$
Continuando,

$3=33\cdot 2-21\cdot 3=33\cdot 2-(318-33\cdot 9)\cdot 3=33\cdot 29-318\cdot =$
$= 33\cdot 29−318\cdot 3 = (351−318\cdot 1)\cdot 29−318\cdot 3 = 351\cdot 29−318\cdot 32 $
Infine, chiamando in causa

$318=1020-351·2$:

$3=351\cdot 29-318\cdot 32=351\cdot 29-(1020-351\cdot 2)\cdot 32=1020(-32)+351\cdot 93$
Abbiamo dunque trovato

$m=-32en=93$:

$3=1020(-32)+351\cdot 93$

Osservazione

Come abbiamo già detto, quando questa è solo una delle infinite possibili coppie

$(m,n)$ che soddisfano l'identità di Bezout

Equazioni diofantee

Una equazione del tipo

$$ax+by=c$$

dove

$a,b,c$ sono numeri interi e

$x,y$ sono le variabili, si chiama equazione diofantea.

Risolverla vuol dire trovare una coppia di numeri interi

$(\overline{x},\overline{y})\in \mathbb{Z}\times \mathbb{Z}$ tali che

$$a\overline{x}+b\overline{y}=c$$

Teorema

L'equazione diofantea

$ax+by=c$
(con

$a$ e

$b$ non entrambi nulli) ha soluzione se e solo se

$MCD(a,b)$ divide

$c$,
quindi

$MCD(a,b)|c$

​ omessa dimostrazione pagina 114-115

Teorema

Se l'equazione diofantea ammette soluzione, allora ammette infinite soluzioni.
Presa una soluzione particolare

$(\overline{x},\overline{y})$, l'insieme

$S$ di tutte le soluzioni può essere descritto così:

$S=\{(\overline{x}+\gamma ,\overline{y}+\delta )|(\gamma ,\delta )\text{ è soluzione dell'equazione omogenea associata}\}$

Dimostrazione

Le argomentazioni esposte poco sopra dimostrano che

$$\{(\overline{x}+\gamma ,\overline{y}+\delta )|(\gamma ,\delta )\text{ è soluzione dell'equazione omogenea associata }\}\subseteq S$$
Resta da dimostrare l’inclusione opposta, ossia che ogni soluzione dell'equazione diofantea è della forma

$(\overline{x},\overline{y})+\text{una soluzione dell'equazione omogenea associata}$
Questo segue osservando che, se

$(\alpha ,\beta )$ è una soluzione dell'equazione diofantea, allora

$(\alpha -\overline{x},\beta -\overline{y})$ è una soluzione della equazione omogenea associata.