Lezione 9 (26 marzo 2001 h. 9.30-10.30)

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 n=m=-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 mnon 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\hbox{\rm { e }}c\mathrel{\big\vert} ... ...{c\in\mathbb Z\mid c\mathrel{\big\vert}m\hbox{\rm { 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$

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 \vbox{\hsize... ...goritmo di Euclide a $m,r$ .} \kern5pt}\kern5pt\hrule }\vrule}$$