SunuLab
Notre savoir
Retour au module Maths
À manipuler

L'algorithme d'Euclide

Pave un rectangle de carrés : le plus petit a pour côté le PGCD.

30181266

On pave le rectangle 48×30 avec les plus grands carrés possibles. Le plus petit carré a pour côté le PGCD.

a48
b30
PGCD(48, 30)
6
Divisions successives
48=1×30+1848 = 1 \times 30 + 18
30=1×18+1230 = 1 \times 18 + 12
18=1×12+618 = 1 \times 12 + 6
12=2×6+012 = 2 \times 6 + 0
L'algorithme d'Euclide

On remplace (a,b)(a, b) par (b,  a mod b)(b, \; a \bmod b) jusqu'à ce que le reste soit nul. Le dernier reste non nul est le PGCD. C'est l'un des plus vieux algorithmes connus (≈ 300 av. J.-C.).