Cryptographie: théorie des nombres

[entrecieletmer16]

Bonjour,

J'aimerais démontrer que l'algorithme d'Euclide et l'algorithme d'Euclide étendu sont correct mais je ne sais pas très bien comment m'y prendre.
Dans le cas de l'algorithme d'Euclide, je pense qu'il faut montrer que
pgcd (a,b)= pgcd (b, a mod b).

Pourriez-vous m'aider à démontrer ces algorithmes et cette égalité?
Merci de votre aide

Aurel'

[Lierre Aeripz]

Il faut effectivement montrer que pour tout n, pgcd(a, b) = pgcd(a - nb, b).
Quel niveau as-tu ?

[entrecieletmer16]

Je suis en 2ème baccalauréat de mathématique