Much ado about $\mathbb Z _p$ [dispensa]
Inviato: 25 lug 2011, 13:01
Apro un topic per dispensare un po' di fatti utili sull'aritmetica modulare e argomenti collegati, che ovviamente serve sempre portarsi da casa. Le dimostrazioni sono lasciate a voi: non si spaventino i novizi, ché ho cercato di rimanere sul facile! Giusto gli ultimi teoremi servoniranno solo se avete gli occhi a mandorla. Orsù, cominciamo. Seguiranno (sperabilmente) molti esercizi; se pensate che abbia omesso qualche teorema senza il quale non si può vivere PMatemi senza remore e vedrò se aggiungerlo.
1. Introduzione, Fermat e ordini moltiplicativi
Questa lista è ben lungi dall'essere completa data la quantità di fatti e fattarelli che esistono su quest'argomento. Questi fatti possono essere poco attraenti e sembrare facili (scriverli è lungo ma va fatto...), ma sono basi indispensabili per ciò che vedremo dopo; sulle cose più facili sono andato più di fretta
Divisione con resto. Per $a,b \in \mathbb N ^\ast$ esistono unici $r, k$ tali che $b=ak+r$ e $0 \leq r<a$.
Definizione di congruenza. $a \equiv b \pmod n$ significa che $a$ e $b$ hanno lo stesso resto nella divisione per $n$.
Definizione degli interi modulo $n$. L'insieme $\mathbb Z _n$, o anche $\mathbb Z / n\mathbb Z$, è l'insieme degli interi modulo $n$, ovvero l'insieme degli interi da $0$ a $n-1$.
Teorema di Bézout. Dati $a, b \in \mathbb Z$ esistono $x, y \in \mathbb Z$ tali che $ax+by=\gcd(a, b)$.
Annullamento del prodotto modulo $p$. Se $p \in \mathbb P$ e $ab \equiv 0 \pmod p $ allora $p|a$ o $p|b$.
Divisione modulo $n$. Se $c \neq 0$ e $ac \equiv bc \pmod n$ allora $a \equiv b \pmod {\frac n {\gcd(n, c)}}$.
Riduzione delle congruenze. Se $\gcd(a, n)=\gcd(b, n)=1$, $a^k \equiv b^k \pmod n$ e $a^j \equiv b^j \pmod n$ allora $a^{\gcd(k, j)} \equiv b^{\gcd(k, j)} \pmod n$.
Definizione sulle classi di resto. Un sistema completo di classi di resto modulo $n$ è un insieme $\mathcal S \subset \mathbb N$ tale che $\mathcal S \mod n \cong \mathbb Z_n$ (dove per $\mathcal S \mod n$ s'intende $\{ k \mod n: k \in \mathcal S \}$).
Estensione dei sistemi completi di classi di resto. Se $\mathcal S$ è un sistema completo di classi di resto modulo $n$, e $a, b \in \mathbb N ^\ast$ sono tali che $\gcd(a, n)=1$ allora $a \mathcal S+b$ è anch'esso un sistema completo di classi di resto (dove per $a \mathcal S+b$ s'intende $\{ ak+b : k \in \mathcal S \}$).
Definizione di inverso. $a$ è l'inverso modulo $n$ di $b$ se $ab \equiv 1 \pmod n$.
Criterio per l'invertibilità. $a$ è invertibile modulo $n$ se e solo se $\gcd(a, n)=1$.
Teorema cinese del resto. Un sistema del tipo $$\begin{cases} x \equiv a_1 \pmod {n_1}\\ x \equiv a_2 \pmod {n_2} \\ \vdots \\x \equiv a_k \pmod {n_k} \end{cases}$$ se gli $n_i$ sono a due a due coprimi ha una soluzione, unica modulo $\prod_i n_i$.
Definizione di $\phi$. $\phi(n):=\#\{ 1 \leq k \leq n-1 : \gcd(k, n)=1 \}$.
Formula per $\phi$. $$ \phi(n)= n \prod _{p|n \atop p \in \mathbb P} \left (1- \frac 1 p \right ).$$
Somma su $\phi$. $$ \sum _{d|n} \phi (d)=n.$$
Teorema di Euler. Se $\gcd(a, n)=1$ allora $a^{\phi(n)} \equiv 1 \pmod n$.
Corollario (piccolo teorema di Fermat). $a^p \equiv a \pmod p$ per ogni $p \in \mathbb P$.
Teorema di Wilson. $\Gamma(p) \equiv -1 \pmod p$ se e solo se $p \in \mathbb P$.
Definizione di ordine moltiplicativo. $\text{ord} _n (a)=b$ significa che $b$ è il minimo intero positivo tale che $a^b \equiv 1 \pmod n$.
Divisibilità dell'ordine moltiplicativo. $\text{ord}_n (a) | \phi(n)$ se $\gcd(a, n)=1$.
Altra divisibilità dell'ordine moltiplicativo. Se $a^x \equiv a^y \pmod n$ allora $\text{ord}_n (a)|x-y$.
Definizione di generatore. $g \in \mathbb N ^\ast$ è un generatore modulo $n$ se ogni numero coprimo con $n$ è congruo a qualche potenza di $g$; inoltre $\text{ord} _n (g)=\phi (n)$.
Lemma degli ordini. Per ogni $d|p-1$ esistono $\phi(d)$ elementi di ordine $d$ in $\mathbb Z_p$.
Esistenza di generatori. Esistono generatori solo modulo $2$, $4$, $p^n$ e $2p^n$ con $p \in \mathbb P \setminus \{ 2 \}$.
Numero di generatori. Se esistono generatori modulo $n$ allora ne esistono $\phi (\phi (n))$.
Criterio per i generatori. Se $g$ genera $\mod p$ e $\mod p^2$ allora genera modulo ogni potenza di $p$.
Teorema di Vinogradov. Esiste $C \in \mathbb R^+$ tale che per ogni $p \in \mathbb P \setminus \{ 2 \}$ e ogni $\epsilon >0$ esiste un generatore modulo $p$ minore di $c p^{\frac 1 2+\epsilon}$.
1. Introduzione, Fermat e ordini moltiplicativi
Questa lista è ben lungi dall'essere completa data la quantità di fatti e fattarelli che esistono su quest'argomento. Questi fatti possono essere poco attraenti e sembrare facili (scriverli è lungo ma va fatto...), ma sono basi indispensabili per ciò che vedremo dopo; sulle cose più facili sono andato più di fretta
Divisione con resto. Per $a,b \in \mathbb N ^\ast$ esistono unici $r, k$ tali che $b=ak+r$ e $0 \leq r<a$.
Definizione di congruenza. $a \equiv b \pmod n$ significa che $a$ e $b$ hanno lo stesso resto nella divisione per $n$.
Definizione degli interi modulo $n$. L'insieme $\mathbb Z _n$, o anche $\mathbb Z / n\mathbb Z$, è l'insieme degli interi modulo $n$, ovvero l'insieme degli interi da $0$ a $n-1$.
Teorema di Bézout. Dati $a, b \in \mathbb Z$ esistono $x, y \in \mathbb Z$ tali che $ax+by=\gcd(a, b)$.
Annullamento del prodotto modulo $p$. Se $p \in \mathbb P$ e $ab \equiv 0 \pmod p $ allora $p|a$ o $p|b$.
Divisione modulo $n$. Se $c \neq 0$ e $ac \equiv bc \pmod n$ allora $a \equiv b \pmod {\frac n {\gcd(n, c)}}$.
Riduzione delle congruenze. Se $\gcd(a, n)=\gcd(b, n)=1$, $a^k \equiv b^k \pmod n$ e $a^j \equiv b^j \pmod n$ allora $a^{\gcd(k, j)} \equiv b^{\gcd(k, j)} \pmod n$.
Definizione sulle classi di resto. Un sistema completo di classi di resto modulo $n$ è un insieme $\mathcal S \subset \mathbb N$ tale che $\mathcal S \mod n \cong \mathbb Z_n$ (dove per $\mathcal S \mod n$ s'intende $\{ k \mod n: k \in \mathcal S \}$).
Estensione dei sistemi completi di classi di resto. Se $\mathcal S$ è un sistema completo di classi di resto modulo $n$, e $a, b \in \mathbb N ^\ast$ sono tali che $\gcd(a, n)=1$ allora $a \mathcal S+b$ è anch'esso un sistema completo di classi di resto (dove per $a \mathcal S+b$ s'intende $\{ ak+b : k \in \mathcal S \}$).
Definizione di inverso. $a$ è l'inverso modulo $n$ di $b$ se $ab \equiv 1 \pmod n$.
Criterio per l'invertibilità. $a$ è invertibile modulo $n$ se e solo se $\gcd(a, n)=1$.
Teorema cinese del resto. Un sistema del tipo $$\begin{cases} x \equiv a_1 \pmod {n_1}\\ x \equiv a_2 \pmod {n_2} \\ \vdots \\x \equiv a_k \pmod {n_k} \end{cases}$$ se gli $n_i$ sono a due a due coprimi ha una soluzione, unica modulo $\prod_i n_i$.
Definizione di $\phi$. $\phi(n):=\#\{ 1 \leq k \leq n-1 : \gcd(k, n)=1 \}$.
Formula per $\phi$. $$ \phi(n)= n \prod _{p|n \atop p \in \mathbb P} \left (1- \frac 1 p \right ).$$
Somma su $\phi$. $$ \sum _{d|n} \phi (d)=n.$$
Teorema di Euler. Se $\gcd(a, n)=1$ allora $a^{\phi(n)} \equiv 1 \pmod n$.
Corollario (piccolo teorema di Fermat). $a^p \equiv a \pmod p$ per ogni $p \in \mathbb P$.
Teorema di Wilson. $\Gamma(p) \equiv -1 \pmod p$ se e solo se $p \in \mathbb P$.
Definizione di ordine moltiplicativo. $\text{ord} _n (a)=b$ significa che $b$ è il minimo intero positivo tale che $a^b \equiv 1 \pmod n$.
Divisibilità dell'ordine moltiplicativo. $\text{ord}_n (a) | \phi(n)$ se $\gcd(a, n)=1$.
Altra divisibilità dell'ordine moltiplicativo. Se $a^x \equiv a^y \pmod n$ allora $\text{ord}_n (a)|x-y$.
Definizione di generatore. $g \in \mathbb N ^\ast$ è un generatore modulo $n$ se ogni numero coprimo con $n$ è congruo a qualche potenza di $g$; inoltre $\text{ord} _n (g)=\phi (n)$.
Lemma degli ordini. Per ogni $d|p-1$ esistono $\phi(d)$ elementi di ordine $d$ in $\mathbb Z_p$.
Esistenza di generatori. Esistono generatori solo modulo $2$, $4$, $p^n$ e $2p^n$ con $p \in \mathbb P \setminus \{ 2 \}$.
Numero di generatori. Se esistono generatori modulo $n$ allora ne esistono $\phi (\phi (n))$.
Criterio per i generatori. Se $g$ genera $\mod p$ e $\mod p^2$ allora genera modulo ogni potenza di $p$.
Teorema di Vinogradov. Esiste $C \in \mathbb R^+$ tale che per ogni $p \in \mathbb P \setminus \{ 2 \}$ e ogni $\epsilon >0$ esiste un generatore modulo $p$ minore di $c p^{\frac 1 2+\epsilon}$.
