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


Général

Introduction Chapitre entier

Points théoriques

PGCD et PPCM Algorithme d'Euclide

Exercices

Exercice 1 Exercice 2 Exercice 3 Exercice 4 Exercice 5 Exercice 6

Prérequis


Introduction

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.



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