Lezione 10 (28 marzo 2001 h. 10.30-11.30)

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+mye 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)=1allora 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₁d₂ con 1<d₁,d₂<n tali che n=d₁d₂. 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₁ è primo ogni q_j=1 oppure q_j=p₁. Poiché per ipotesi ogni q_j>1 allora q_j=p₁ 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₁=p₁.

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_kche 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)=\cases{ k &se $i=j$\cr\delta(i)&se $i\ne j$ }$$

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 iprimi. 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