Teorema di Eulero

Home | Perchè la crittografia | Crittografia a chiave segreta | Crittografia a chiave pubblica | Numeri primi | Aritmetica modulare

L' algoritmo Euclideo è un metodo sistematico di calcolo che permette di determinare

 in modo efficiente il massimo comune divisore tra due numeri interi.


Dati due numeri interi esso consiste nell'effettuare:

  •  La divisione tra i due numeri assegnati;
  • Le successive divisioni tra i divisori e i resti che man mano si ottengono.

L'iterazione termina quando il resto della divisione tra i due numeri è zero.

Il M.C.D. corrisponde al resto non nullo della divisione tra i numeri assegnati.

Osservazioni:

  • due numeri interi,a e b, si dicono coprimi se M.C.D.(a,b)=1
  • M.C.D.(a,b)=M.C.D.(b,r1), dove rè il resto della divisione tra a e b
  • l'inverso dell'algoritmo di Euclide permette di scrivere il M.C.D. come somma di due multipli di a e b , ossia

     

     detta  identità di Bezout

  • i resti delle divisioni -mod 10-eseguite con l'algoritmo di Euclide, letti dal basso verso l'alto, forniscono la rappresentazione del numero in base 10

Applicazioni con Excel 

Applicazioni con Excel 


Home | Teorema di Eulero | Algoritmo di Euclide | Piccolo teorema di Fermat | Numeri Casuali