Théorie > Théorie des nombres > Algorithme d'Euclide

Prérequis

Résumé

Les notions de plus grand commun diviseur (PGCD) et plus petit commun multiple (PPCM) sont fondamentales en théorie des nombres, et ce chapitre commence par leur définition. Nous présentons ensuite l'algorithme d'Euclide permettant justement de calculer le PGCD de deux nombres entiers, aussi grands soient-ils. Outre cette possibilité, cet algorithme est également très utile d'un point de vue théorique. En effet, il nous permettra notamment par la suite de démontrer le théorème de Bézout et de calculer l'inverse d'un nombre en arithmétique modulaire.

Ce chapitre a été écrit par N. Radu et mis en ligne le 8 décembre 2014.

Pour pouvoir accéder aux exercices de ce chapitre et ainsi le compléter, vous devez d'abord compléter : Divisibilité et nombres premiers