Numeri primi e congruenze

# Numeri primi e congruenze ###### tags: `md` #### MCD ###### Definizione Dati due numeri interi $a, b$ non entrambi nulli, il loro massimo comun divisore $MCD(a, b)$ è il più grande numero intero positivo che divide sia $a$ sia $b$. ###### Lemma Dati due numeri interi $a, b$ non entrambi nulli, $MCD(a, b) = MCD(a -b, b)$. ###### Dimostrazione Se un intero divide due numeri divide anche la loro somma e la loro differenza. Quindi se $x$ divide $a$ e $b$, alloar divide anche $a-b$ e $b$. Viceversa se x divide $a-b$ e $b$ allora divide anche $a$ e $b$. L'insieme dei numeri che dividono sia $a$ sia $b$ coincide quindi con l'insieme dei numeri che dividono sia $a-b$ sia $b$. ###### Corollario Se $a \equiv a' \ mod \ b$ allora $MCD(a, b) = MCD(a', b)$. #### Algoritmo di Euclide L'algoritmo di Euclide per calcolare $MCD(a, b)$ consiste nell'applicare ripetutamente la regola $MCD(b, a) = MCD(a, b) = MCD(a-kb, b)$ per ricondurmi a numeri sempre più piccoli finché uno dei due è $0$ e l'$MCD$ è l'altro numero. #### Numeri primi ###### Definizione Un numero intero $p \ge 2$ si dice primo se gli unici suoi divisori interi positivi sono 1 e $p$ stesso. Si mette in evidenza il fatto che i numeri primi sono elementi irriducibili di $\mathbb{Z}$. Cerco un'altra caratterizzazione dei numeri primi: ###### Teorema Sia $p$ un numero primo. Supponiamo che, dati due numeri interi $b, c$ valga $p | bc$: allora possiamo concludere che o $p|b$ o $p|c$. ###### Dimostrazione Se $p|b$ abbiamo finito. Se $p$ non divide $b$, allora $MCD(p, b) = 1$. Sapendo che la fattorizzazione in prodotto di primi di un numero intero è unica (per Teorema), e visto che $p|bc$ e che $MCD(p, b)=1$, allora $p|c$. Abbiamo dimostrato che o $p|b$ o $p|c$. ###### Teorema ###### Esistenza della fattorizzazione in prodotto di primi Ogni numero intero $\ge 2$ o è primo o si può scrivere come prodotto di numeri primi. ###### Dimostrazione Si può dimostrare per induzione. Consideriamo il predicato $P(n)$: "il numero n o è primo o si può scrivere come prodotto di numeri primi" e sia $S$ l'insieme dei numeri interi $m \ge 2$ tali che la proposizione $P(m)$ sia falsa. Bisogna dimostrare che $S$ è vuoto. Possiamo supporre per assurdo che $S$ non sia vuoto, ed essendo un sottoinsieme non vuoto di $\mathbb{N}$, allora ha un elemento minimo per il principio del minimo, $s$. Questo valore è un intero $\ge 2$ tale che $P(s)$ è falsa, ovvero non è né primo né prodotto di primi. Non essendo primo si può scrivere come prodotto di due numeri $a$ e $b$, $s=ab$, dove $1<a<s$ e $1<b<s$. Quindi $a$ e $b$, essendo $\ge 2$ e strettamente minori di $s$, sono tali che le proposizioni $P(a)$ e $P(b)$ sono vere. Quindi $a$ e $b$ o sono primi, o sono prodotto di primi, e la loro prodotto ci fornisce la decomposizione in primi di $s$. Abbiamo ottenuto un assurdo, perchè $s$ non può ammettere una decomposizione in primi. ###### Teorema ###### Unicità della fattorizzazione in prodotto di primi Siano $$ a=p_1p_2p_3 ... p_r \\ a=q_1q_2q_3...q_s $$ due fattorizzazioni del numero intero $a \ge 2$ dove i numeri $p_i$ ($i =1, 2,...,r$) e $q_j$ ($j = 1,2,...,s$) sono primi. Supponiamo di aver scritto le fattorizzazioni in modo che $p_1 \le p_2 \le ... \le p_r$ e $q_1 \le q_2 \le ... \le q_s$. Allora vale che $r = s$ e, per ogni $i = 1, 2,...,s$, $p_i = q_i$. ###### Dimostrazione Sia $r \le s$ e dimostro per induzione su $r$. PASSO BASE: $r = 1$. Il valore $s$ deve essere uguale a 1 altrimenti il numero $a$ sarebbe sia primo che non primo. $a=p_1=q_1$. PASSO INDUTTIVO: suppongo che l'enunciato sia vero quando la fattorizzazione ha $r-1$ fattori primi. Considero $p_1$. Dato che $p_1$ divide $q_1q_2...q_s=q_1(q_2...q_s)$ per Teorema o $p_1|q_1$ oppure $p_1|(q_2...q_s)$. Se valre $p_1|q_1$ allora $p_1 = q_1$ (essendo entrambi primi). Se così non fosse, allora $p_1|(q_2...q_s)$ da cui, iterando, si arriva dopo un numero finito di passi i $p_1 = q_i > q_1$. Quindi $q1$, essendo strettamente minore di $p_1$, è strettamente minore di tutti i primi $p_i$. Ma sappiamo che $q_1$ divide $p_1(p_2...p_r)$. Con un ragionamento analogo, possiamo trovare un j tale che $q_1 = p_j$, ma è assurdo dato ceh $q_1$ è strettamente minore di tutti i primi $p_i$. Dunque deve valere $p_1 = q_1$. Dividendo l'uguaglianza per $p_1$ otteniamo $p_2...p_r = q_2...q_s$, dove a sinistra abbiamo il prodotto di $r-1$ fattori, e a destra abbiamo $s-1$ fattori. Per ipotesi induttiva sappiamo che $r-1=s-1$ e che i primi presenti nelle due fattorizzazioni sono uguali. ###### Teorema L'insieme $\mathcal{P}$ dei numeri primi è infinito. ###### Dimostrazione Supponiamo per assurdo che $\mathcal{P}$ sia finito e siano dunque $$ p_1, p_2,...p_N $$ tutti i numeri primi. Consideriamo allora il numero $$ a = (p_1 \cdot p_2 \cdot ... \cdot p_N) + 1 $$ per il teorema dell'esistenza della fattorizzazione in prodotto di primi, esiste un numero primo che divide $a$. Vuol dire che uno dei $p_i$ deve dividere $a$. Ma nessuno dei numeri $p_i$ divide $a$, visto che, per ogni $i=1,2,...,N$ da $a=(p_1 \cdot p_2 \cdot ... \cdot p_N)+1$ si deduce che il resto della divisione euclidea di $a$ per $p_i$ è 1. #### Congruenze ###### Definizione Fissato un numero intero positivo m, diremo che due numeri interi $a$ e $b$ sono "congrui fra loro modulo m" se quando facciamo la divisione euclidea di $a$ per $m$ otteniamo lo stesso resto di quadno facciamo la divisione euclidea di $b$ per $m$. Scriveremo: $$ a \equiv b \ (m) $$ oppure $$ a \equiv b \ mod \ m $$ Se due interi $a$ e $b$ sono congrui fra loro modulo $m$, possiamo scrivere le loro divisioni euclidee per $m$ $$ a=mq+r \qquad b=ms+r $$ ###### Proposizione Dato un intero positivo $m$, due interi $a$ e $b$ sono congrui fra loro modulo $m$ se e solo se $m$ divide $a-b$ (questo equivale a dire che $m$ divide $b-a$). ###### Osservazione La condizione "$m$ divide $a-b$" poteva essere presa come definizione di congruenza fra i numeri interi $a$ e $b$. ###### Teorema Le congruenze "rispettano" somme e prodotti. se $a \equiv a' \ mod \ m$ e $b \equiv b' \ mod \ m$, allora $a+b \equiv a'+b' \ mod \ m$ e $ab \equiv a'b' \ mod \ m$. #### Inverso di un numero modulo un intero positivo Gli unici numeri che ammettono un inverso moltiplicativo in $\mathbb{Z}$ sono $+1$ e $-1$. Nell'aritmetica modulare, invece, esistono vari numeri che ammettono un inverso. ###### Definizione Un inverso di un intero $a$ modulo $m$ è un intero $x$ tale che $ax \equiv 1 \ mod \ m$. ###### Teorema Un numero $a$ ha un inverso modulo $m$ se e solo se $MCD(a, m) = 1$. ###### Dimostrazione Se $MCD(a, m) = 1$, per il teorema di Bezout possiamo trovare $u$, $v$ interi tali the $au+mv=1$ con $u$, $v$ interi. Questa uguaglianza, letta modulo $m$, diventa $au \equiv 1 \ mod \ m$. Quindi $u$ è un inverso di $a$ modulo $m$. ###### Teorema Dato $m \in \mathbb{N} - \{0\}$, per ogni $a \in \mathbb{Z}-\{0\}$, $b_1,\ b_2 \in \mathbb{Z}$ vale: $$ ab_1 \equiv ab_2 \ (m) \Leftrightarrow b_1 \equiv b_2 \ \Bigg(\frac{m}{MCD(a, m)}\Bigg) $$ ###### Osservazione Se c'è un parametro $a$ che divide entrambi i membri di una congruenza , si può "semplificare", a patto di dividere anche il modulo $m$ per $MCD(a, m)$.