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()
Sia e sia , allora: = con e primi distinti.
Se è dispari e pseudoprimo forte relativamente ad e sia allora
Per calcolare si scrive l'esponente in binario con e si calcola Per il buon comportamento nel prodotto si inizia a calcolare la potenza più piccola e la si riutilizza nel calcolo delle successive.
, quindi
Se allora non è pseudoprimo relativamente alla base perchè: se allora tale che | e | con se fosse pseudoprimo relativamente ad avrei | ma per la proprietà del "non c'è due senza tre | e | e avrei che |, impossibile.
Se è primo non divide e allora = ed è una conseguenza del Teorema di Eulero in quanto
Sia con Esiste un che risolve il seguente sistema di congruenze: = = = e se è una soluzione allora è soluzione se e solo se =
Under construction...