Lezione 4 (1 marzo 1999 h. 9.30-10.30)

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

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

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

La proposizione precedente assieme all'osservazione che (n,0)=n per ogni $n\ne0$ 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}$$

Proprietà dei numeri coprimi e caratterizzazione dei numeri primi

Proposizione 4.2  

1.

se (n,m)=1 e $n\big\vert mq$ allora $n\big\vert q$.

2.

se (n,m)=1 e $n\big\vert q$ e $m\big\vert q$ allora $nm\big\vert q$.

Dim.  1. Se (n,m)=1 allora esistono $x,y\in\mathbb Z$ tali che 1=nx+mye quindi q=nqx+mqy. Ma allora se $n\big\vert mq$ esiste h tale che mq=nh e quindi q=nqx+nhy=n(qx+hy).

2. $n\big\vert q$ quindi q=nh, dato che $m\big\vert q=nh$ e (n,m)=1allora per la 1 si ha che $m\big\vert h$ ossia h=km e quindi q=nh=nmk, ovvero $nm\big\vert q$.     $\square$

Corollario 4.3   p è primo se e solo se per ogni $n,m\in\mathbb Z$ si ha che $p\big\vert nm\Rightarrow p\big\vert n$ oppure $p\big\vert m$.

Dim.  Supponiamo che $p\big\vert nm$, dato che p è primo, se $p\not\big\vert n$ allora (p,n)=1, per lo proposizione precedente si ha allora che $p\big\vert m$.

Viceversa supponiamo che per ogni $n,m\in\mathbb Z$ si ha che $p\big\vert nm\Rightarrow p\big\vert n$ oppure $p\big\vert m$, allora se p=dh allora $p\big\vert dh$ e quindi $p\big\vert d$, e quindi per 3.3 si ha che $d=\pm p$ e $h=\pm1$ oppure $p\big\vert h$ e quindi $h=\pm p$ e $d=\pm1$.     $\square$

Esercizio 4.1      Siano $n_1,\dots,n_k\in\mathbb Z$ e sia p un primo tale che $p\big\vert n_1n_2\dots n_k$. Si provi che allora esiste i tale che $p\big\vert n_i$.
Soluzione

Il minimo comune multiplo: definizione, esistenza e unicità

Definizione 4.4   Dati due interi $n,m\in\mathbb Z$ si dice che M è un minimo comune multiplo di n e m se

1.

$n\big\vert M$ e $m\big\vert M$;

2.

se $n\big\vert c$ e $m\big\vert c$ allora $M\big\vert c$.

Come nel caso del massimo comun divisore si dimostra che due minimi comuni multipli sono uguali a meno del segno e quindi si chiama il minimo comune multiplo quello positivo e sarà indicato con [n,m].

Teorema 4.5 (esistenza del m.c.m.)   Siano $n,m\in\mathbb Z$ non entrambi nulli allora esiste il minimo comune multiplo tra n e m.

Dim.  Sia $M=\frac{nm}{(n,m)}=n'm'(n,m)$ dove si è posto n=n'(n,m) e m=m'(n,m). Chiaramente allora M=n m'=n' m e quindi $n\big\vert M$e $m\big\vert M$.

Se $n\big\vert c$ e $m\big\vert c$ allora $(n,m) \big\vert c$ e quindi posto c=c'(n,m) si ha che $n'\big\vert c'$ e $m'\big\vert c'$. Dato che (n',m')=1, per 4.2 si ha che $n'm'\big\vert c'$ e quindi che $M=n'm'(n,m)\big\vert c'(n,m)=c$.     $\square$