Lezione 10

Proprietà dei numeri coprimi e caratterizzazione dei numeri primi

Proposizione 10.1  

1. se $(n,m)=1$ e $n\mathrel{\big\vert}mq$ allora $n\mathrel{\big\vert}q$.
2. se $(n,m)=1$ e $n\mathrel{\big\vert}q$ e $m\mathrel{\big\vert}q$ allora $nm\mathrel{\big\vert} q$.

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

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

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

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

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

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

Il minimo comune multiplo: definizione, esistenza e unicità

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

1. $n\mathrel{\big\vert}M$ e $m\mathrel{\big\vert}M$;
2. se $n\mathrel{\big\vert}c$ e $m\mathrel{\big\vert}c$ allora $M\mathrel{\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 10.4 (esistenza del m.c.m.)   Siano $n,m\in\mathbb{Z}$ non entrambi nulli allora esiste il minimo comune multiplo tra $n$ e $m$.

Dimostrazione.  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\mathrel{\big\vert}M$ e $m\mathrel{\big\vert}M$.

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

Esercizio 10.2   Si generalizzino al caso di più di due interi le definizioni di MCD e mcm tra due interi, e se ne dimostrino esistenza e unicità.
Soluzione

Esercizio 10.3   Denotando con $(n_1,n_2,\dots,n_k)$ e con $[n_1,n_2,\dots,n_k]$ rispettivamente il massimo comun divisore ed il minimo comune multiplo tra gli interi $n_1,n_2,\dots,n_k$ (cfr. esercizio precedente), si provi che:

1. $(n_1,\dots,n_k,n_{k+1})=((n_1,\dots,n_k),n_{k+1})$
2. $[n_1,\dots,n_k,n_{k+1}]=[[n_1,\dots,n_k],n_{k+1}]$

Soluzione

Il teorema fondamentale dell'Aritmetica

Teorema 10.5 (Teorema fondamentale dell'aritmetica)   Per ogni $n\in\mathbb{Z}$, $n\ge2$ esistono numeri primi $p_1,p_2,\dots,p_k>0$ tali che $n=p_1p_2\dots p_k$. Se anche $q_1,\dots,q_h$ sono primi positivi tali che $n=q_1q_2\dots q_h$, esiste una bigezione $\sigma:\{1,2,\dots,h\}\to\{1,2,\dots,k\}$ tale che $q_i=p_{\sigma(i)}$.

In altre parole, ogni intero maqggiore di $1$ si scrive in modo unico, a meno dell'ordine, come prodotto di numeri primi positivi.

Dimostrazione.  Procediamo per induzione su $n$. Se $n=2$ non c'è nulla da dimostrare in quanto $2$ è primo. Supponiamo $n>2$ e che la tesi sia vera per ogni $k<n$. Se $n$ è primo non c'è nulla da dimostrare, se $n$ non è primo allora esistono due numeri $d_1d_2$ con $1<d_1,d_2<n$ tali che $n=d_1d_2$. Per ipotesi di induzione esistono dei primi positivi $p_i$ e $q_j$ tali che $d_1=p_1\dots p_{k_1}$ e $d_2=q_1\dots q_{k_2}$, ma allora $n=p_1\dots p_{k_1}q_1\dots q_{k_2}$ è prodotto di primi positivi.

Unicità. Sia $n=p_1\dots p_k=q_1\dots q_h$ con $p_i$ e $q_j$ primi positivi e $k\le h$. Procediamo per induzione su $k$. Se $k=1$ allora $n=p_1=q_1\dots q_h$, quindi $q_j\mathrel{\big\vert}p_1$ per ogni $j$, e dato che $p_1$ è primo ogni $q_j=1$ oppure $q_j=p_1$. Poiché per ipotesi ogni $q_j>1$ allora $q_j=p_1$ per ogni $j$. Se ora fosse $h>1$ si avrebbe $n=q_1\dots q_h\ge q_1q_2=p_1^2>p_1=n$ e questo è assurdo, e quindi $h=1$ e $q_1=p_1$.

Sia $k>1$, allora $p_k\mathrel{\big\vert}n=q_1\dots q_h$, quindi per l'esercizio 10.1 esiste un $j$ tale che $p_k\mathrel{\big\vert}q_j$. Dato che sia $p_k$ che $q_j$ sono primi positivi, allora $p_k=q_j$. Ma allora $p_1\dots p_{k-1}=q_1\dots q_{j-1}q_{j+1}\dots q_h$, per ipotesi di induzione possiamo allora dire che le due fattorizzazioni hanno lo stesso numero di elementi, ossia $k-1=h-1$, e che esiste una bigezione $\delta:\{1,\dots,j-1,j+1,\dots,k\}\to\{1,\dots,k-1\}$ tale che $q_i=p_{\delta(i)}$ per ogni $i$. Definendo allora $\sigma:\{1,2,\dots,n\}\to\{1,2,\dots,n\}$

$$\sigma(i)= \begin{cases} k &\text{se }i=j\\ \delta(i)\text{se }i ne j \end{cases}$$

si ottiene una bigezione tale che $q_i=p_{\sigma(i)}$ per ogni $i$.     $\square$

Esistenza di infiniti numeri primi

Corollario 10.6   I numeri primi sono infiniti.

Dimostrazione.  Per assurdo supponiamo che $p_1,p_2,\dots,p_n$ siano tutti i primi. Si consideri $n=p_1p_2\dots p_n+1$. Chiaramente $n>1$ e non è divisibile per nessun $p_i$ e quindi $n$ sarebbe un numero maggiore di $1$ che non è divisibile per nessun primo e ciò contraddice il teorema fondamentale dell'aritmetica.     $\square$

Esercizio 10.4   [Calcolo del M.C.D. e del m.c.m. usando la fattorizzazione in primi] Se $a,b\in \mathbb{N}$ denotiamo con $a\vee b=\max\{a,b\}$ e con $a\wedge b=\min\{a,b\}$.

Siano $n=\prod _{i=1}^s p_i^{k_i}$, $m=\prod _{i=1}^s p_i^{h_i}$ con $p_i$ numeri primi, allora $(n,m)=\prod _{i=1}^s p_i^{k_i\wedge h_i}$ e $[n,m]=\prod _{i=1}^s p_i^{k_i\vee h_i}$.
Soluzione