Siano \(a \in \mathbb{Z}\) e \(n \in \mathbb{N}\) relativamente primi. Allora: \(a^{\varphi (n)}\) = \(1\pmod{n}\)
Considero la lista dei numeri numeri minori e relativamente primi con \(n\) :
La lista (1) ha proprio \(\varphi(n)\) numeri per come è definita la funzione di Eulero Considero ora la lista di resti:
Per come è definita la lista (2) ha ancora \(\varphi(n)\) numeri ed essi sono ancora compresi tra 0 e \(n-1\) essendo resti nella divisione per \(n\).
A questo punto dimostro che le liste (1) e (2) sono in realtà la stessa lista in due passi.
1)Mostro che tutti i numeri nella lista (2) sono diversi: Se avessimo che\(\left[aa_i \right]_n=\left[aa_j \right]_n\) per la proprietà 1.3.2 avremo che \(aa_i\)=\(aa_j\) (mod n), cioè che n|\(aa_i-aa_j\) Raccogliendo \(a\) abbiamo che n|a(\(a_i-a_j\)) ma gcd(\(a,n\))=1 per ipotesi quindi per la proprietà 1.5.10 abbiamo che \(n\)|\(a_i-a_j\) che per definizione di congruenza: \(a_i\)= \(a_j \pmod{n}\) ma \(a_i\) e \(a_j\) sono nella lista (1) e quindi compresi tra 0 e \(n-1\), per questo l'unica possibilità è avere: \(a_i=a_j\) oppure \(i=j\). Ma per come erano stati presi \(a_i\) e \(a_j\) non possono essere uguali quindi \(i=j\), cioè avevo preso due volte lo stesso numero: \(\left[aa_i \right]_n\neq \left[aa_j \right]_n\)
2)gcd(\(\left[aa_i \right]_n,n\))=gcd(\(aa_i,n\)) per il primo passo dell' algoritmo di Euclide. Ma gcd(\(a,n\))=1 per ipotesi e \(a_i\), essendo un elemento della lista (1), è relativamente primo ad \(n\). Allora per la proprietà 1.5.11 ii) abbiamo che anche gcd(\(aa_i,n\))=1 quindi la lista (1) e la lista (2) sono uguali a meno dell'ordine.
Se le due liste sono uguali a meno dell'ordine allora: \(\prod_{i=1}^{\varphi(n)} a_i=\prod_{i=1}^{\varphi(n)} \left[aa_i \right]_n\) Per la proprietà 1.3.4 ii) e per la proprietà 1.3.2 i) posso riscrivere, raccogliendo a:
Per definizione di congruenza:
e raccogliendo ho che \(n\)|(\(a^{\varphi(n)}-1\))\(a_1 a_1 \cdots a_{\varphi(n)}\) Dato che tutti gli \(a_i\) sono relativamente primi con \(n\) essendo della lista (1), per la proprietà 1.5.10 \(n\)|(\(a^{\varphi(n)}-1\)) cioè: \(a^{\varphi (n)}\) = \(1\pmod{n}\)
C.V.D.
Due interi \(a,n \in \mathbb{Z}\) sono relativamente primi sse gcd(a,n)=1
gcd(m,n)=1 sse \(\exists \lambda,\mu \in \mathbb{Z} tali che \lambda m+\mu m=1\)
Se \(a\)|\(bc\) e gcd(\(a,b\))=1 allora \(a\)|\(c\)
i)Se \(a\)|\(c\), \(b\)|\(c\) e gcd(\(a,b\))=1 allora \(ab\)|\(c\) ii)Se gcd(\(ab\))=1 e gcd(\(a,c\))=1 allora gcd(\(a,bc\))=1
L'unico numero \(d \in \mathbb{N}\) che soddisfa \(\operatorname{div}(d)\)=\(\operatorname{div}(m)\cap \operatorname{div}(n)\) è chiamato massimo comun divisore di \(m\) ed \(n\)e si scrive:
gcd(\(m,n\))
Siano \(m,n \in \mathbb{Z}\). Allora \(\exists \lambda,\mu \in \mathbb{Z} tali che \lambda m+\mu m=\operatorname{gcd}(m,n)\)
Siano \(m,n \in \mathbb{Z}\) allora: i)gcd(\(m,0\))=\(m\) se \(m \in \mathbb{N}\) ii)gcd(\(m,n\))=gcd(\(m-qn,n\)) \(\forall q \in \mathbb{Z}\)
gcd(0,0)=0 Siano \(m,n \in \mathbb{Z}\) Se gcd(\(m,n\))=1 \(m\) ed \(n\) si dicono relativamente primi
Algoritmo di Euclide calcola facilmente il gcd(\(m,n\)) e per calcolare anche \(\lambda\) e \(\mu\) bisogna utilizzare l'Algoritmo Esteso di Euclide
Sia \((\)\(\mathbb{Z}\)/\(N\)\()\)*=\(\{X \in \mathbb{Z}\)/\(N\)tale che \(\operatorname{gcd}\)\((X,N)=1 \}\) per \(N \in \mathbb{N}\). \(\varphi (n)\) = |\((\mathbb{Z}\)/\(N)\)*|
Siano \(m,n \in \mathbb{N}\) relativamente primi. \(\varphi(mn)=\varphi(n)\varphi(n)\)
Sia \(\operatorname{div}(n)=\{d \in \mathbb{N}\) tale che \(n\)divide \(d \}\)
\(\operatorname{div}(0)= \mathbb{N}\) e div(n)=div(-n) per ogni \(n \in \mathbb{Z}\)
Siano\(a, b,c \in \mathbb{Z}\) con \(c>0\).Allora \(a\) e \(b\) sono chiamati congrui modulo \(c\) se \(c\) divide \(b-a\). Ossia se hanno lo stesso resto nella divisione per \(c\) , o anche \(a=b+kc\). E si scrive come: \(a\)= \(b \pmod{c}\)
i) \(a\)= \(\left[a \right]_c\) (mod \(c\) ) ii)a=\(b\) (\(\pmod{c}\)) sse \(\left[a \right]_c=\left[b \right]_c\)
Se \(x_1\)=\(x_2\) (\(b\) (\(\pmod{c}\)) ) e \(y_1\)=\(y_2\) (mod \(d\)) allora: i)\(x_1+y_1\)= \(x_2+y_2\) (mod \(d\)) ii)\(x_1 y_1\)= \(x_2 y_2\) (mod \(d\))
le congruenze hanno un buon comportamento per somma e prodotto: \(\left[a(b+c) \right]_d=\left[\left[a \right]_d (\left[b \right]_d +\left[c \right]_d) \right]_d\)
Se a= \(b\)(mod 0) significa che \(a=b\)
Sia \(d \in \mathbb{Z}\) con \(d>0\) per ogni \(x \in \mathbb{Z}\) c'è un unico resto \(r \in \mathbb{N}\) tale che:
\(x=qd+r\)
dove \(q \in \mathbb{Z}\) e \(0 \leq r < d\)
Il resto \(r\) si può scrivere anche come \(\left[x \right]_d\)
Se \(r=0\) allora si dice che \(q\) divide \(x\).
Sia \(\mathbb{Z}\)/\(N= \{X \in \mathbb{N}\)|\(0\leq X
Se \(a=bc\) con \(a,b,c \in \mathbb{Z}\)si può dire che c'è un divisore di \(a\) (\(c\) divide \(a\)) e si scrive:
\(a\)|\(a\)
ossia il resto della divisione è zero, oppure \(c \in \operatorname{div}(a)\)
Se \(a=b+c\) con \(a,b,c \in \mathbb{Z}\)e i)se \(d\)|\(a\) e \(d\)|\(b\) allora \(d\)|\(c\) ii)se \(d\)|\(a\) e \(d\)|\(c\) allora \(d\)|\(b\) iii)se \(d\)|\(b\) e \(d\)|\(c\) allora \(d\)|\(a\) Cioè se \(d\) divide due tra i termini \(a,b,c\) necessariamente divide anche il terzo.
Utilizzando il risultato della proprietà 1.5.1 ii) e per la definizione di resto abbiamo che: gcd(\(m,n\))=gcd(\(m-qn,n\))=gcd(\(\left[m \right]_n,n\)) L'algoritmo procede iterando le divisioni e riutilizzando i resti come nuovo input, fino a che non si trova un resto uguale a zero. Il resto precedente sarà quindi il massimo comun divisiore.
34=2*13+8 13=1*8+5 8=1*5+3 5=1*3+2 3=1*2+1 2=2*1+0
Per calcolare i \(\lambda,\mu \in \mathbb{Z} tali che \lambda m+\mu m=\operatorname{gcd}(m,n)\) bisogna utilizzare l'algoritmo esteso di Euclide.
Per calcolare il gcd(\(m,n\)) insieme ai \(\lambda,\mu \in \mathbb{Z} tali che \lambda m+\mu m=\operatorname{gcd}(m,n)\) bisogna ultilizzare la seguente tablella:
dove le prime due righe corrispondono all'algoritmo di Euclide:\(r_i=r_{i-2}-q_i r_{i-1}\) Gli elementi delle ultime due righe sono calcolati come: \(a_i=a_{i-2}-q_i a_{i-1}\)\(b_i=b_{i-2}-q_i b_{i-1}\) Infine \(r_n\)=gcd(\(m,n\))
TESTO LINK