Bezout e diofantee

# 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 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\ge0$ (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\ge1$, $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 deﬁnizione è 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 ﬁnito. 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 ﬁnito, perché possiamo concludere subito che $|b| = MCD(|a|,|b|) = MCD(a,b)$ > > Altrimenti proseguiamo con delle divisioni euclidee successive ﬁnché 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_2q_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_nq_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) =\ldots $$ 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) \neq (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 coeﬃcienti 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 inﬁnite scelte possibili di una coppia ($m$,$n$) tale che $MCD(a,b) = am + bn$. ###### Dimostrazione Consideriamo l'insieme $CL^+(a,b)$ di tutte le possibili combinazioni lineari positive a coefficienti interi di $a$ e $b$, ossia $$ CL^+(a,b) =\{ar+bs\;\;|\;\;r\in\mathbb{Z}, s\in\mathbb{Z}, ar+bs >0\} $$ Tale insieme è non vuoto. Infatti supponiamo che $a\neq 0$ (altrimenti si fa lo stesso ragionamento con $b$). Allora si trovano degli elementi dell'insieme $CL^+(a,b)$ per esempio scegliendo $s= 0$ e $r$ tale che $ra >0$. Già così abbiamo esibito infiniti elementi nell'insieme $CL^+(a,b)$. Inoltre $CL^+(a,b)\subseteq\mathbb{N}$. Dunque, per il principio del buon ordinamento, $CL^+(a,b)$ ammette minimo. Sia $d$ tale minimo: in particolare, dato che $d\in CL^+(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 CL^+(a,b)$ per definizione di $CL^+(a,b)$. Questo non può succedere perché $0\le r < d$ e $d$ era stato scelto come minimo elemento di $CL^+(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) \neq (0,0)$, se $c|a$ e $c|b$, allora non solo $c \leq MCD(a,b)$ ma più precisamente vale che $c|MCD(a,b)$ ###### Teorema Dati due numeri interi $a$ e $b$ con $(a,b) \neq (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' = {a \over MCD(a,b)} \qquad b' = {b \over 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′$ e $b′$, 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′m+b′n $$ e dunque $1$ è il più piccolo numero intero positivo ottenibile come combinazione lineare intera di $a′$ e di $b′$. ###### 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: $$ 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 $$ 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: $$ 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 $$ Ora ripercorriamo l'algoritmo "a rovescio": cominciamo da $3 = 12−9 \cdot 1$. Ricordiamo che come obiettivo ﬁnale 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 $ Inﬁne, 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 = −32 e n = 93$: $3 = 1020(−32) + 351\cdot 93$ ###### Osservazione Come abbiamo già detto, quando questa è solo una delle inﬁnite 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 $(\bar x,\bar y) ∈\mathbb{Z}\times\mathbb{Z}$ tali che $$ a\bar x + b\bar 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 inﬁnite soluzioni. Presa una soluzione particolare $(\bar x,\bar y)$, l'insieme $S$ di tutte le soluzioni può essere descritto così: $S = \{(\bar x + \gamma,\bar y + \delta)|(\gamma,\delta) \text{ è soluzione dell'equazione omogenea associata}\}$ ###### Dimostrazione Le argomentazioni esposte poco sopra dimostrano che $$ \{(\bar x+γ,\bar y+\delta)|(γ,\delta) \text{ è soluzione dell'equazione omogenea associata }\} \subseteq S $$ Resta da dimostrare l’inclusione opposta, ossia che ogni soluzione dell'equazione diofantea è della forma $(\bar x,\bar y) + \text{una soluzione dell'equazione omogenea associata}$ Questo segue osservando che, se $(\alpha,\beta)$ è una soluzione dell'equazione diofantea, allora $(\alpha−\bar x,\beta−\bar y)$ è una soluzione della equazione omogenea associata.