Lezione 9

Divisibilità e sue prime proprietà

Definizione 9.1   Dati due interi $n,m$ si dice che $n$ è un divisore di $m$ (o che $m$ è un multiplo di $n$) se esiste un $k\in\mathbb{Z}$ tale che $m=nk$. Si indica con $n\mathrel{\big\vert}m$ (si legge $n$ divide $m$).

Esempio 9.2   $n\mathrel{\big\vert}0$ per ogni $n$ mentre se $n\ne 0$ allora $0\not\mathrel{\big\vert}n$, si ha inoltre che $\pm1\mathrel{\big\vert}n$ e $\pm n\mathrel{\big\vert}n$ per ogni $n$.

Proposizione 9.3  

1. Se $n\mathrel{\big\vert}m$ e $m\mathrel{\big\vert}q$ allora $n\mathrel{\big\vert}q$.
2. Se $n\mathrel{\big\vert}m$ e $m\mathrel{\big\vert}n$ allora $n=\pm m$.

Dimostrazione.  1. Se $m=kn$ e $q=hm$ allora $q=hkm=(hk)m$ ossia $n\mathrel{\big\vert}q$.

2. Se $n=mk$ e $m=nh$ allora $m=hkm$ e quindi $m(1-hk)=0$ e quindi o $m=0$ e quindi anche $n=0$, oppure $1-hk=0$ ma allora o $h=k=1$ e quindi $n=m$ oppure $h=k=-1$ e quindi $n=-m$.     $\square$

Definizione 9.4   Il numero $n$ si dice primo se i suoi unici divisori sono $\pm1,\pm n$.

Il massimo comun divisore: definizione, esistenza e unicità

Definizione 9.5   Dati due interi $n,m$ non entrambi nulli, si dice che $d$ è un massimo comun divisoretra $n$ e $m$ se:

1. $d\mathrel{\big\vert}n$ e $d\mathrel{\big\vert}m$;
2. Se $c\mathrel{\big\vert}n$ e $c\mathrel{\big\vert}m$ allora $c\mathrel{\big\vert}d$.

Proposizione 9.6   Se $d$ e $d'$ sono due massimi comun divisori tra $n$ e $m$ allora $d'=\pm d$.

Dimostrazione.  $d$ è un divisore comune di $n$ e $m$, quindi poiché $d'$ è un massimo comun divisore si ha che $d\mathrel{\big\vert}d'$. Scambiando i ruoli di $d$ e $d'$ si ha allora che anche $d'\mathrel{\big\vert}d$ e quindi per 9.3 si ha che $d'=\pm d$.     $\square$

Definizione 9.7   Diremo che $d$ è il massimo comun divisore di $n$ e $m$ se è un massimo comun divisore positivo. La proposizione precedente garantisce che se esiste il massimo comun divisore è unico. Esso verrà indicato con $(n,m)$.

Teorema 9.8   Dati due numeri $n,m\in\mathbb{Z}$ non entrambi nulli esiste il massimo comun divisore di $n$ ed $m$.

Dimostrazione.  Si consideri l'insieme $S=\{s\in\mathbb{Z}\mid s>0, \exists x,x\in\mathbb{Z}: s=nx+my\}$. $S\ne\varnothing$ dato che $nn+mm>0$ (dato che $n$ e $m$ non sono entrambi nulli). Sia $d=nx+my=\min S$, dimostriamo che $d$ è il massimo comun divisore. Se $c\mathrel{\big\vert}n$ e $c\mathrel{\big\vert}m$ allora $n=ck$ e $m=ch$, quindi $d=nx+my=ckx+chy=c(kx+hy)$ ossia $c\mathrel{\big\vert}d$. Dimostriamo ora che $d\mathrel{\big\vert}n$. Consideriamo la divisione euclidea tra $n$ e $d$ ossia $n=dq+r$ con $0\le r<d$, se $r>0$ allora $r=n-dq=n-(nx+my)q=n(1-qx)+(-m)y$ è un elemento di $S$. Ciò è assurdo perché $r<d$ e $d=\min S$. Quindi $r=0$ ossia $d\mathrel{\big\vert}n$. In modo analogo si prova che $d\mathrel{\big\vert}m$.     $\square$

Osservazione 9.9   Dalla dimostrazione precedente segue che dati $n,m\in\mathbb{Z}$ esistono $x,y\in\mathbb{Z}$ tali che $(n,m)=nx+my$ e che gli interi della forma $nx+my$ con $x,y\in\mathbb{Z}$ sono tutti e soli i multipli di $(n,m)$.

Definizione 9.10   $n,m\in\mathbb{Z}$ non entrambi nulli si dicono coprimi se $(n,m)=1$.

Osservazione 9.11   $(n,m)=1$ se e solo se esistono $x,y\in\mathbb{Z}$ tali che $nx+my=1$. Ad esempio $(n,n+1)=1$ per ogni $n$. Infatti $1=(n+1)1+n(-1)$.

Proposizione 9.12   Sia $d=(n,m)$, allora $(\frac nd,\frac md)=1$.

Dimostrazione.  $d=nx+my$ e quindi $1=\frac nd x+\frac md y$.     $\square$

L'algoritmo di Euclide per il calcolo del M.C.D.

Proposizione 9.13 (algoritmo di Euclide)   Siano $n,m\in\mathbb{Z}$, $m\ne 0$. Sia $n= mq + r$ la divisione euclidea di $n$ per $m$ allora $\{c\in\mathbb{Z}\mid c\mathrel{\big\vert}n$ e $c\mathrel{\big\vert} m\}=\{c\in\mathbb{Z}\mid c\mathrel{\big\vert}m$ e $c\mathrel{\big\vert}r\}$, in particolare quindi $(n,m)=(m,r)$.

Dimostrazione.  Se $c\mathrel{\big\vert}n$ e $c\mathrel{\big\vert}m$ allora $n=ch$ e $m=ck$ e quindi $r=n-mq=ch-ckq=c(h-kq)$ ossia $c\mathrel{\big\vert}r$ e $c\mathrel{\big\vert}m$. Viveversa se $c\mathrel{\big\vert}r$ e $c\mathrel{\big\vert}m$ allora $m=ch$ e $r=ck$ e quindi $n=mq+r=chq+ck=c(hq+r)$ ossia $c\mathrel{\big\vert}n$ e $c\mathrel{\big\vert}m$.     $\square$

Osservazione 9.14   La proposizione precedente assieme all'osservazione che $(n,0)=n$ per ogni $n\ne 0$ permette di costruire un algoritmo (algoritmo di Euclide) per il calcolo del M.C.D.

$$\hbox{\vrule \vbox{\hrule\kern5pt\hbox{\kern5pt \begin{minipage}{... ...l'algoritmo di Euclide a $m,r$. \end{minipage}\kern5pt}\kern5pt\hrule }\vrule}$$

tale algoritmo si può tradurre in un programma ricorsivo per la definizione di una funzione MCD che calcoli il M.C.D. tra due numeri naturali:

$$\hbox{\vrule \vbox{\hrule\kern5pt\hbox{\kern5pt \begin{minipage}{... ... MCD(m,r) END IF }\end{verbatim}\end{minipage}\kern5pt}\kern5pt\hrule }\vrule}$$