Calcul sur Mathematica du PGCD de a et b entiers naturels et d’un couple de
 coefficients entiers relatifs (u , v) tels que d = au +bv.

On utilise les seules opérations supposée connues : +, –, Max, Min, multiplication traduite par un espace blanc,
Quotient et Mod respectivement quotient et reste de la division euclidienne.
If est l’instruction conditionnelle, elle s’effectue exclusivement pour r >
 0, sinon, il ne se passe rien. Do répète k fois le programme situé à gauche
de la virgule dans son crochet. Le PGCD est à la fin dans d.

On pourra comparer avec le commentaire du 15 novembre 2010 de l’article : Quel
langage de progammation pour l’algorithmique en classe de seconde.

n m’excusant de ne pouvoir transmettre le document mathematica original

d=Max[a,b] ; r=Min[a,b] ; k=r ; u=1 ; v=0 ; w=0 ; t=1 ;
Do[If[r>0,(x=u ; u=w ; w=x–w Quotient[d,r] ; y=v ; v=t ; t=y–t Quotient[d,r] ; z=d ; d=r ; r=Mod[z,r])],k] ;

If[b<a, Print[« d= », d, « = », v, «  a+( »,u,« ) b »]] 

Exemple 1

a=1 ; b=8 ;
d = 1 = 1 a + (0)b

Exemple 2

a=8 ; b=1 ;
d = 1 = 0 a + (1) b

Exemple 3

a=0 ; b=0 ;
d = 0 = 0 a + (1) b

Exemple 4

a=5 ; b=0 ;
 d = 5 = 1 a + (0) b

Exemple 5

a=9 ; b=6 ;
d = 3 = 1 a + ( –1) b 

Exemple 6

a=345 ; b=960 ;
d = 15 = –25 a + (9) b

Exemple 7

a=6321 ; b=4256 ;
d = 7 = –169 a + (251) b

Exemple 8

a=5437 ; b=8531 ;
d = 1 = 2749 a + (–1752) b

Exemple 9. Entrée d’un nombre strictement négatif

a=–3 ; b=5 ;
d = 5 = 0 a + (1) b

Noter que la boucle Do tourne 0 fois pour k < 0, le programme s’arrête, même s’il ne donne pas le PGCD

Ce commentaire concerne le cours d’arithmétique Terminale S de Jean Claude Lise, plus précisément les axiomes dits fondamentaux.

Toute partie non vide de N admet un plus petit élément.

Toute partie non vide et majorée de N admet un plus grand élément.

A noter au passage que le deuxième énoncé est une conséquence facile du premier.

Ces axiomes sont utilisés à trois reprises dans le dit cours :
premier axiome en vue du théorème de la division euclidienne (p.2) ; deuxième axiome dans la définition (qui est en fait un théorème et définition) du PGCD (p.6). Dans ces deux cas, l’appartenance à la partie de N dont il est question est testable, c’est ainsi qu’elle conduit à un algorithme : algorithme de la division euclidienne, algorithme de recherche du PGCD conforme à la définition de plus grand commun diviseur à ne pas confondre avec l’algorithme d’Euclide qui fournit une autre méthode.

On rencontre la troisième utilisation dans le Théorème précédent le Théorème de Bézout (p.7). La partie E dont il est queston est définie comme le sous-ensemble des éléments y de N*pour lesquels il existe u et v éléments de Z tels que a u + b v = y.
Le « Il existe » dans Z ensemble de cardinal infini a pour effet de ne pas permettre de tester l’appartenance à ce sous-ensemble. Le résultat obtenu à ce stade de l’exposé est purement théorique, il permet toutefois de démontrer le théorème de Gauss dont la principale application est l’unicité dans la décomposition en produit de facteurs premiers, (on se demande pourquoi s’être donné tant de mal pour en admettre l’unicité conformément aux instructions du programme !). Ce même résultat ne permet pas de résoudre les équations diophantiennes (p.9), la deuxième méthode remontant l’algorithme d’Euclide (p.7) présentée sous forme d’exemple immédiatement avant l’identité de Bézout est indépendante de la démonstration précédente, elle pourrait être traitée dans le cas général, elle conduit à un algorithme facile à traiter sur un exemple mais moins évident à programmer.

En conclusion, les axiomes dits fondamentaux ne sont nullement évidents, leur démonstration à partir des axiomes de Péano s’appuierait sur le tiers-exclu. Il sont algorithmiquement acceptables lorsque le « non-vide » est démontré directement (aucun problème ici) et l’appartenance à la partie de N est testable.

Ce commentaire concerne la division euclidienne dans le cours de JC Lise.

Il y a une légère faute dans la démonstration de Conséquence de la propriété d’Archimède. Quand on a trouvé le plus petit entier p dans N tel que a < bp il n’est pas certain que q défini par q = p – 1 soit dans N. Il est facile d’y rémédier en recherchant directement le plus petit entier q dans N tel que a < b(q + 1) ...

Il y a aussi quelques fautes de frappe.

Dans la démonstration du Théorème de la division euclidienne dans N.
Démonstration de existence, fin de la première ligne :

qb ≤ a < q (b + 1) au lieu de qb C a ...

Dans la Division euclidienne dans Z, on lit Théorème puis
Définition : ... a  ∈ Z et non Î, de même b ∈ Z ~... et non Î ~....

Il est d’usage dans les cours d’arithmétique, y compris dans celui de Jean Claude Lise présenté ici, de parler de division euclidienne (p. 3) et d’algorithme d’Euclide pour la recherche du PGCD (p. 6).

En fouillant dans les Eléments d’Euclide, livres VII à IX consacrés à l’Arithmétique, je trouve bien les nombres premiers entre eux, la notion de PGCD mais aucune trace de division euclidienne au sens moderne du terme, celle-ci est remplacée par des soustractions successives, ce qui permet d’atteindre le reste mais non le quotient. En particulier, la recherche du PGCD de deux nombres entiers naturels se fait par soustractions successives le plus petit du plus grand.