Siano e relativamente primi. Allora: =
Considero la lista dei numeri numeri minori e relativamente primi con :
La lista (1) ha proprio numeri per come è definita la funzione di Eulero Considero ora la lista di resti:
Per come è definita la lista (2) ha ancora numeri ed essi sono ancora compresi tra 0 e essendo resti nella divisione per .
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 per la proprietà 1.3.2 avremo che = (mod n), cioè che n| Raccogliendo abbiamo che n|a() ma gcd()=1 per ipotesi quindi per la proprietà 1.5.10 abbiamo che | che per definizione di congruenza: = ma e sono nella lista (1) e quindi compresi tra 0 e , per questo l'unica possibilità è avere: oppure . Ma per come erano stati presi e non possono essere uguali quindi , cioè avevo preso due volte lo stesso numero:
2)gcd()=gcd() per il primo passo dell' algoritmo di Euclide. Ma gcd()=1 per ipotesi e , essendo un elemento della lista (1), è relativamente primo ad . Allora per la proprietà 1.5.11 ii) abbiamo che anche gcd()=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: 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 |() Dato che tutti gli sono relativamente primi con essendo della lista (1), per la proprietà 1.5.10 |() cioè: =
C.V.D.
Due interi sono relativamente primi sse gcd(a,n)=1
gcd(m,n)=1 sse
Se | e gcd()=1 allora |
i)Se |, | e gcd()=1 allora | ii)Se gcd()=1 e gcd()=1 allora gcd()=1
L'unico numero che soddisfa = è chiamato massimo comun divisore di ed e si scrive:
gcd()
Siano . Allora
Siano allora: i)gcd()= se ii)gcd()=gcd()
gcd(0,0)=0 Siano Se gcd()=1 ed si dicono relativamente primi
Algoritmo di Euclide calcola facilmente il gcd() e per calcolare anche e bisogna utilizzare l'Algoritmo Esteso di Euclide
Sia /*=/tale che per . = |/*|
Siano relativamente primi.
Sia tale che divide
e div(n)=div(-n) per ogni
Siano con .Allora e sono chiamati congrui modulo se divide . Ossia se hanno lo stesso resto nella divisione per , o anche . E si scrive come: =
i) = (mod ) ii)a= () sse
Se = ( () ) e = (mod ) allora: i)= (mod ) ii)= (mod )
le congruenze hanno un buon comportamento per somma e prodotto:
Se a= (mod 0) significa che
Sia con per ogni c'è un unico resto tale che:
dove e
Il resto si può scrivere anche come
Se allora si dice che divide .
Sia /| per ogni
Se con si può dire che c'è un divisore di ( divide ) e si scrive:
|
ossia il resto della divisione è zero, oppure
Se con e i)se | e | allora | ii)se | e | allora | iii)se | e | allora | Cioè se divide due tra i termini necessariamente divide anche il terzo.
Utilizzando il risultato della proprietà 1.5.1 ii) e per la definizione di resto abbiamo che: gcd()=gcd()=gcd() 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 bisogna utilizzare l'algoritmo esteso di Euclide.
Per calcolare il gcd() insieme ai bisogna ultilizzare la seguente tablella:
dove le prime due righe corrispondono all'algoritmo di Euclide: Gli elementi delle ultime due righe sono calcolati come: Infine =gcd()
TESTO LINK