Lezione 3 (25 febbraio 1999 h. 10.30-11.30)

Divisibilità e sue prime proprietà

Definizione 3.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\big\vert m$ (si legge n divide m).

Esempio 3.2   $n\big\vert0$ per ogni n mentre se $n\ne0$ allora $0\not\big\vert n$, si ha inoltre che $\pm1\big\vert n$ e $\pm n\big\vert n$ per ogni n.

Proposizione 3.3  

1.

  Se $n\big\vert m$ e $m\big\vert q$ allora $n\big\vert q$.

2.

  Se $n\big\vert m$ e $m\big\vert n$ allora $n=\pm m$.

Dim.  1. Se m=kn e q=hm allora q=hkm=(hk)m ossia $n\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 3.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 3.5   Dati due interi n,m non entrambi nulli, si dice che d è un massimo comun divisoretra n e m se:

1.

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

2.

Se $c\big\vert n$ e $c\big\vert m$ allora $c\big\vert d$.

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

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

Definizione 3.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 3.8   Dati due numeri $n,m\in\mathbb Z$ non entrambi nulli esiste il massimo comun divisore di n ed m.

Dim.  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\big\vert n$ e $c\big\vert m$ allora n=ck e m=ch, quindi d=nx+my=ckx+chy=c(kx+hy) ossia $c\big\vert d$. Dimostriamo ora che $d\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\big\vert n$. In modo analogo si prova che $d\big\vert m$.     $\square$

Osservazione 3.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 3.10   $n,m\in\mathbb Z$ non entrambi nulli si dicono coprimi se (n,m)=1.

Osservazione 3.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 3.12   Sia d=(n,m), allora $(\frac nd,\frac md)=1$.

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