Wikipedia

Algoritmo di Euclide: differenze tra le versioni

Naviga nella cronologia in modo interattivo
← Differenza precedenteDifferenza successiva →
Contenuto cancellato Contenuto aggiunto
VisualeWikitesto
m →‎Altri progetti: aggiunta preposizione articolata
Riga 17:
Per definizione di resto nella divisione, ''b''<sub>n+1</sub> < ''b''<sub>n</sub> per ogni ''n'', quindi la successione dei ''b''<sub>n</sub> è strettamente decrescente, e quindi esiste un ''N'' tale che ''b''<sub>N</sub> = 0.
Vogliamo dimostrare che ''d'' = ''a''<sub>N</sub>.
Infatti, per induzione si ha che per ogni ''n'', che ''d'' | ''a''<sub>n</sub> = ''b''<sub>n-1</sub> = ''a''<sub>n-2</sub> - ''q''<sub>n-2</sub>''b''<sub>n-2</sub>. Inoltre, sempre per induzione, ''a''<sub>N</sub> divide ''a''<sub>n</sub> per ogni ''n'' ≤ ''N'', quindi divide anche ''b''<sub>n</sub> per ogni ''n'' < ''N'', quindi ''a''<sub>N</sub> = ''d''.
 
==Tempo di calcolo==
Estratto da "https://it.wikipedia.org/wiki/Algoritmo_di_Euclide"