Discussion:Plus grand commun diviseur de nombres entiers

Je n'ai pas bien saisie la présentation de l'algorithme d'euclide qui est fourni et je ne l'ai pas appris ainsi. Ainsi voici le calcul selon ce que j'ai appris du PGCD de 30 et 48 :

48 = 30 * 1 + 18

30 = 18 * 1 + 12

18 = 12 * 1 + 6

12 = 6 * 2 + 0

Le reste est nul, le PGCD est donc 6.

Je pense que cela revient au meme mais c'est bien plus simple, d'autant plus lorsqu'on utilise cette méthode pour résoudre des equations du type 48x + 30y = 6.

Exemple : determination d'une solution particulière :

(48 = 30 * 1 + 18) * 2

(30 = 18 * 1 + 12) * -1

18 = 12 * 1 + 6

En additionnant on trouve donc : 48 * 2 = 30 * 3 + 6 <=> 48 * 2 + 30 * (-3) = 6

Bon bien sur c'est pas la seule méthode pour trouver une solution particuliere mais c'est juste pour dire que l'écriture telle que je l'ai appris est je pense plus agréable à manipuler et fait appel directement à la notion de division euclidienne.

--Max81 6 mai 2006 à 02:22 (CEST)

Moi aussi j'ai appris l'algorithme d'Euclide de cette manière. Je voulais ajouter que même si cet article se trouve dans "mathématiques élémentaires", il serait sans doute bon de justifier cet algorithme. Léna 16 mai 2006 à 21:15 (CEST)

Renommage ?

Ma nouvelle lubie, c'est de clamer que les mathématiques ne sont jamais vraiment élémentaires, et donc d'enlever cette expression des titres. Pour cette notion de PGCD, il est bon d'avoir deux articles, dont l'un "élémentaire" (en fait, dans Z), et on a en gros deux possibilités (titres "suffixés" à préciser éventuellement)

PGCD et PGCD de nombres entiers

où PGCD traiterait du PGCD "abstrait" dans un anneau, le "vrai" si on se place d'un point de vue mathématique. Un bandeau en haut renverrait les lecteurs intéressés vers PGCD de nombres entiers. Avantage : titres clairs et nets (pour des matheux) inconvénient : titre de PGCD surprenant pour un non-matheux, avec risque de faire peur aux collégiens qui, terrorisés, ne verront pas le bandeau.

PGCD et PGCD dans un anneau

où PGCD serait pour les entiers, respectant propablement le principe de moindre surprise pour la plupart des lecteurs. L'inconvénient est que des nouveaux contributeurs seraient tentés d'ajouter des considérations plus générales sur les anneaux, avec en partie raison.

Des avis ? ---- El Caro ^bla 14 février 2011 à 20:03 (CET)

Je ne suis pas convaincu qu'on ait besoin de deux articles - l'ouverture de en:Greatest common divisor (sans le regarder dans le détail) me laisse à penser qu'on peut monter doucement en puissance, même si ça manque manifestement d'exemples au début.

Quand je lis la page sur la page de discussions de laquelle nous sommes, elle ne me plaît pas, chose que je traitais pour l'instant en ne la regardant pas. Raté, par la faute à El Caro. Mon avis est : tu peux la renommer comme tu le souhaites, mais pas PGCD qui doit être réservé à un article général ayant à peu près la même tête que l'article de :en (sans exclure qu'il aille un peu plus lentement au démarrage, mais sans abuser). Au-delà de cette interdiction de principe de faire pointer le nom « PGCD » ici, je m'éloigne et laisse la gestion de cette page à ceux que ça intéresse de la gérer. Touriste (d) 14 février 2011 à 20:20 (CET)

Certes, même un article "général" peut être écrit avec un minimum de pédagogie et commencer par les entiers. Ce qui peut justifier deux articles, c'est surtout l'obligation du "résumé introductif" qui doit ressembler à l'article : si l'article est long et monte en puissance, le résumé aussi, ce qui fait qu'on doit parler de PGCD dans des anneaux dès ce résumé.

En regardant chez nos grands frères (et grandes sœurs), on constate aussi qu'ils se sont crus obligés de créer un en:Greatest common divisor of two polynomials spécialisé. ---- El Caro ^bla 14 février 2011 à 20:37 (CET)

Je suis complètement d'accord avec Touriste (même s'il a mal interprété mon intervention sur ce sujet sur le Thé). L'introduction doit effectivement se terminer par une phrase ou deux évoquant le fait que cette définition garde un sens dans le contexte plus général des anneaux factoriels. Ambigraphe, le 14 février 2011 à 21:26 (CET)

Si j'ai bien compris :

• On garde PGCD pour le cas "général". Ce qui n'empêche pas d'y évoquer les entiers comme prédécesseurs historiques et cas particulier essentiel ;
• On peut renommer celui-ci en PGCD de nombres entiers ;
• PGCD de polynômes est laissé à l'appréciation de qui voudra bien le créer. ---- El Caro ^bla 15 février 2011 à 08:10 (CET)

D'accord. Il reste la question des wikiliens, que tu éludes, alors qu'elle est plus importante que le titre à mon avis. Je constate que, par exemple, dans l'article Suite de Fibonacci, une phrase est wikiliée comme suit : « ... l'algorithme d'Euclide qui détermine le plus grand commun diviseur de deux entiers. », c'est-à-dire pointant sur le « gros » article. Sommes-nous d'accord pour ne pas réorienter ce wikilien et le laisser sur la page généraliste ? La présente page « élémentaire » est très peu wikiliée, en gros une fois depuis Fraction (mathématiques) dans la phrase : « Certaines fractions peuvent être simplifiées, c'est-à-dire que n et d peuvent être divisés par un même nombre mais le plus grand possible. Ce nombre s'appelle le PGCD (plus grand commun diviseur) de n et d. ». Idéalement, penses-tu qu'il faudrait la wikilier encore moins ? Davantage ? Touriste (d) 15 février 2011 à 08:17 (CET)

Amusant, pendant que vous discutiez du sort des deux articles pgcd et pgcd (mathématiques élémentaires) j'étais en train de créer anneau à pgcd et trouvait un peu triste le traitement du pgcd dans un anneau (intègre ?) dans l'article principal. Quitte à me renier moi-même, je trouve que l'article élémentaire n'est qu'un faible doublon du début de l'article principal. et j'aurais sans état d'âme accepté sa suppression (me voilà maintenant pervertie comme vous tous). L'idée est peut-être d'enrichir cet article en en faisant un vrai article, bien complet, sur le pgcd de deux entiers, en évoquant la problématique sur le plus grand, le cas de 0, la propriété de factorisation, la définition d'élément premiers entre eux, . bref en vidant en partie la première partie de l'article général dans celui-ci et de ne laisser dans l'article principal qu'un résumé avec article loupe. Ainsi on pourrait, quand il ne s'agit que de pgcd d'entiers renvoyer sur cet article. Ensuite on pourrait, à loisir compléter l'article principal sur sa partie pgcd dans un anneau et pgcd dans son corps des fractions (il parait que Bourbaki en parle). HB (d) 15 février 2011 à 09:04 (CET)

Oui, HB, l'idée, c'est ça. Plus généralement, ma remarque sur les articles en "mathématiques élémentaires" ne vise pas à les supprimer, mais au contraire à les appuyer sur des bases solides (mathématiques ou pédagogiques sourçables), et pourquoi pas, en créer plein d'autres...

@Touriste : Pour les liens, ce serait au cas par cas : dans l'exemple que tu cites, ce serait plutôt vers pgcd de nombres entiers. Disons que si on parle de pgcd d'entiers, on lie vers l'article loupe, mais si l'article en question parle d'anneaux avant le lien, on peut lier vers PGCD. Faudra voir le contexte. On pourra aussi placer les modèles {{Article introductif}} et {{Voir article introductif}} en en-tête des deux articles, pour renvoyer les lecteurs égarés. ---- El Caro ^bla 15 février 2011 à 09:20 (CET)

Mmouais ça m'embête de modifier les wikiliens tant que l'état actuel de l'article est ce qu'il est. Bien sûr si tu le retravailles, les suggestions d'HB sur le contenu possible montrent que ça prend sens. Mais en l'état... Enfin pas d'objection si ça concerne un état à l'heure actuelle hypothétique des articles. Touriste (d) 15 février 2011 à 09:25 (CET)

Je ne suis vraiment pas d'accord pour ramener dans un article loupe le pgcd des entiers. J'ai croyais que Touriste partageait mon avis en écrivant « Je ne suis pas convaincu qu'on ait besoin de deux articles ». Ambigraphe, le 15 février 2011 à 18:29 (CET)

Je n'approuve pas non plus franchement la réponse d'El Caro, sans qu'elle me scandalise. Je vois mal des circonstances où wikilier vers le présent article est judicieux, mais puis en imaginer : en gros les contextes où on est dans des mathématiques très faciles et on a l'impression que plein d'exemples aideront. Et encore. Mais comme je l'exprimais, la question de la modification des wikiliens ne se pose pas encore, et la présente page n'est pour l'instant pas un "article-loupe" mais un "article à recycler". Je ne veux pas empêcher El Caro de le faire s'il le souhaite, je n'ai pas l'impression que ce soit une grosse bêtise ; après il faudra peut-être discuter de nouveau après ce recyclage, s'il se fait, mais les modifs faites jusqu'à présent ne me posent pas problème. Touriste (d) 15 février 2011 à 23:27 (CET)

j'ai l'impression que vous parlez de deux choses proches mais légèrement différentes.

Touriste, tu sembles penser que wikilier sur cet article est prématuré et tu doutes de l'avenir de cet article s'il n'y a pas un recyclage profond

Ambigraphe, tu ne souhaite pas que l'article PGCD soit vidé d'une partie de sa substance au bénéfice de celui-ci

Vous semblez d'accord sur le point qu'on ne perdrait rien à la disparition de cet article.

Je vois les choses un peu autrement. Il faut conserver une section sur le pgcd de deux entiers dans l'article PGCD mais sans la diluer à l'excès, sans prendre le lecteur par la main, indiquer que c'est la première rencontre avec la notion, parler des éléments d'Euclide, citer les propriétés, les méthodes de recherche, mais renvoyer sur des articles dédiés pour des explications ou des exemples. Mais l'article PGCD devrait avoir pour objectif de montrer comment cette première approche a conduit à définir des PGCD dans d'autres ensembles, d'exposer les difficultés rencontrées ailleurs : changement de définition, existence de plusieurs pgcd, transfert relativement facile des propriétés à l'ensemble des polynômes sur un corps K, expliquer que si tout se passe bien c'est qu'il existe une division euclidienne. Parler de l'effort de généralisation à d'autres ensemble (anneaux intègres) montrer ce qui se conserve et ne se conserve pas. Enfin évoquer le PGCD sur le corps des fractions. Bref, dans l'article PGCD, la section sur le pgcd de deux entiers devrait servir de tremplin pour aborder le reste et pas de marécage où l'on s'embourbe en vain. A contrario, l'article pgcd de deux entiers peut prendre son temps, développer les points, citer des exemples d'où l'idée d'alléger le premier pour remplir le second. Cependant, "les conseilleurs ne sont pas les payeurs", donc comme je laisse la charge à El Caro de traiter ce doublon, je n'ai pas à lui donner de conseils trop directifs sur les contenus, c'est juste une orientation possible. HB (d) 16 février 2011 à 10:20 (CET)

J'approuve complètement et sans réserve ce message de HB. Ambigraphe, le 16 février 2011 à 13:41 (CET)

J'ai un peu étoffé l'ébauche. La tournure des événements vous convient-elle ? ---- El Caro ^bla 16 février 2011 à 15:23 (CET)

C'est déjà plus riche. Mais pour ma part, j'aurais mis la recherche de PGCD avant les propriétés. D'une part pour une question de logique, si on ne sait pas trouver des pgcd on ne voit pas l'utilité d'en chercher des propriétés. D'autre part, les différentes propriétés sont très fortement liées à l'algorithme de soustractions successives donc, même si on ne fait pas les démonstration, il est bon que, dans le mesure du possible, les propriétés soient démontrables avec uniquement les informations qui les précèdent. Il reste a évoquer plus clairement le cas de 0, et l'autre définition : d divise a et b et si d' divise a et b alors d' divise d. Qu'en penses-tu ? HB (d) 17 février 2011 à 13:33 (CET)

On peut aussi démontrer les techniques de calcul par les propriétés, non ? Dans un souci "encyclopédique", il me semble que la partie "applications" devrait se trouver le plus haut possible, pour répondre à la question "pourquoi cette notion ?". La partie "technique" étant plutôt à réserver à la fin, il me semble que c'est ce qui est souvent fait dans les AdQ de maths, comme déterminant (mathématiques). Mais si tu préfères un autre ordre, n'hésite pas à changer, je m'y opposerai pas. ---- El Caro ^bla 18 février 2011 à 15:52 (CET)

PGCD (0,0) et sens du mot de l'expression « plus grand »

Je sais que nous sommes dans un article introductif sur le PGCD et que, dans le sens habituel (celui d'Euclide) il s'agissait du sens « plus grand » pour la relation d'ordre usuelle. Cependant dans l'article Plus grand commun diviseur il existe une section Plus grand commun diviseur#Quelques précisions sur « plus grand », où on indique bien que le PGCD en général est défini à partir du préordre « divise ». On trouve aussi dans la littérature la définition du pgcd de deux entiers avec la relation «divise» [1]. Ne pourrait-on pas en glisser deux mots ici du genre :

La convention, PGCD(0,0) = 0, contredit la notion du "plus grand diviseur commun" puisqu'il n'existe pas de plus grand diviseur de 0 mais elle cohérente avec la définition si l'on envisage une autre façon d'être plus grand : a est plus grand que b quand a est un multiple de b. C'est cette nouvelle approche qui est envisagée dans la définition générale du PGCD.

Qu'en pensez-vous? HB (discuter) 14 janvier 2014 à 21:35 (CET)

Très bien, à la fois comme guide de lecture et comme bouclier. Anne (discuter) 15 janvier 2014 à 10:22 (CET)

Cette convention pgcd(0,0)=0 est très cohérente avec le Théorème de Bachet-Bézout. D'ailleurs, si on veut que l'énoncé de ce théorème (tel qu'il est actuellement sur Wikipédia) soit correct, il faut définir pgcd(0,0), et la seule valeur qui rende la chose cohérente est 0. 109.217.165.33 (discuter) 26 décembre 2017 à 18:12 (CET)

Incohérence

L'article indique que « Un entier n s'écrit de manière unique à l'ordre près des facteurs et au signe près comme un produit fini de nombres premiers. » La même chose est répétée plus loin : « Tout nombre entier s'écrit de façon unique comme produit de nombres premiers. » Or, c'est faux : 0 n'est pas un produit de nombre premiers, et c'est pourtant un entier. L'article Décomposition en produit de facteurs premiers ne semble pas commettre cette erreur.

109.217.165.33 (discuter) 26 décembre 2017

C'est rectifié. Anne, 28/6/2018

Accessibilité de l'article au profane et petit rappel d'histoire wikipédienne

Je réagis à ce commentaire de diff où Proz souhaiterait une présentation plus élémentaire d'une section.

• l'article Plus grand commun diviseur de nombres entiers est issu au départ d'un article de mathématiques dit élémentaire, dont la présentation sommaire était celle-ci
• en 2011, après l'abandon du projet mathématiques élémentaire, il a été décidé de donner plus de consistance à cet article et de changer son titre. On arrive alors à la version suivante [2]. A ce moment là déjà, je regrettais que la recherche de pgcd vienne en fin d'article[3]
• ce qui devait arriver s'est ensuite produit : les contributeurs ont enrichi la section propriété et la partie recherche de pgcd s'est logiquement adaptée à la section propriété, rendant ainsi l'article progressivment inaccessible à ceux ayant un bagage élémentaire en mathématiques. L'introduction, dans les propriétés, de la notion de valuation p-adique a sonné le glas d'une présentation élémentaire de la notion
• voir aussi la première section de l'article plus grand commun diviseur en 2016 [4].

Je ne vois qu'une alternative

• se résoudre à avoir un article illisible au profane
• concevoir une section approche élémentaire à mettre avant la section propriétés inspirée de ce que l'on trouve dans La Petite Encyclopédie des mathématiques p. 27-28 dans laquelle on se limiterait à des entiers naturels non nuls, on présenterait la recherche par l'ensemble des diviseurs, par la décomposition en facteurs premiers et par les soustractions successives (on laisserait l'algorithme d'Euclide en fin d'article à cause de sa plus grande complexité ou on enverrait plus simplement les lecteurs vers l'article détaillé).

Pour ma part, comme ces valses hésitations finissent par me fatiguer, je ne bougerai pas tant qu'un consensus fort ne se dégagera pas sur le niveau auquel doit se situer cet article. HB (discuter) 27 septembre 2021 à 09:13 (CEST)

Bonjour HB  ; tout à fait d'accord avec ta proposition de section "approche élémentaire", qui pourrait d'ailleurs figurer dans nombre d'articles correspondant au défunt projet "mathématiques élémentaires" ; je pense d'ailleurs qu'il y a un consensus fort (mais tacite) pour cela ; on lance un sondage ?--Dfeldmann (discuter) 27 septembre 2021 à 12:04 (CEST)

* Pour préciser ma remarque en commentaire de diff., je ne pense pas qu'il soit utile de parler de valuation p-adique pour une méthode qui est ou était enseignée au collège (et je ne pense pas trop au delà du secondaire, en tant que méthode), et n'a en fait pas de réel intérêt algorithmique. Un exposé sur un exemple suffit.

* je précise les raisons et le sens de mes interventions d'hier : l'article était factuellement redondant, avec des redites peu compréhensibles, mais aussi par exemple et en vrac un bout de définition dans la section propriété, le même résultat démontré dans deux sections différentes (complètement hors sujet dans l'une), rien sur le théorème de Bezout dans la partie combinaisons linéaires, mais démontré sans que ce soit explicite, une remarque assez dénuée de sens sur l'algo d'Euclide par soustraction, etc. J'ai essentiellement supprimé les redondances, et réordonné, sans modifier ou en modifiant à la marge, avec de rares ajouts, dans l'idée d'avoir un point de départ pour faire évoluer l'article. Par exemple la variante que j'ai déplacée dans la sous-section "Détermination du PGCD">"Décomposition en facteurs premiers" m'a paru à supprimer (algo pas efficace et compliqué à expliquer), mais je n'ai pas voulu le faire sans avis. La généralisation à plus de deux entiers est évidemment à améliorer (définition directe).

* je suis tout à fait d'accord pour commencer par une "approche élémentaire", je ne suis pas trop sûr que ce soit nécessaire d'en faire un titre de section, car cela risque de conduire à nouveau à des redondances. Je proposerai plutôt comme titre pgcd de deux entiers naturels non nuls avec une définition simple, (et donc ok pour les conséquences que ça a pour la suite d'avoir deux entiers naturels non nuls).

* Dans la proposition de HB ci-dessous il y a quelques "retours en arrière' qui me gênent :

** anthyphérèse : c'est vraiment employé par Deledicq ? Je ne l'ai jamais vu qu'en histoire de sciences. En math c'est plutôt appelé "algorithme d'Euclide" quand c'est cité (au minimum certains l'appellent ainsi), et en factorisant les soustractions, on a l'algorithme d'Euclide par division euclidienne (remarque peut-être pas complètement inutile, même si elle est assez triviale, en cherchant 5 mn je la trouve dans Riesel 1994, prime numbers ans computer methods for factorization, tout ça reste élémentaire même si la source ne l'est pas). Cet algo est peut-être conceptuellement un peu plus délicat que celui par la décomposition en facteurs premiers (pour des collégiens), mais par soustractions successives on fait bien finalement des divisions. J'ai du mal à comprendre en quoi l'algo par divisions serait plus compliqué : ce n'est pas plutôt que l'algo de la division en base 10 n'est pas forcément maîtrisé par les collégiens ?

** la mise au même niveau des diverses méthodes de recherche : là, c'est une des rares choses qui ne soit pas de la simple réorganisation que j'avais modifiée, et je regretterais un retour en arrière. Seul l'algo d'Euclide et ses variantes fournissent une méthode efficace (au moins parmi celles présentées). Si les sources de HB ne le disent pas on trouvera ailleurs.

** Recherche d'un PGCD par simplifications successives : telle que présentée, ça n'est pas une méthode systématique, ce qui ne me gêne pas du tout, mais il faudrait que ce soit explicite (si on connait déjà un diviseur commun de ... et ...), et introduire la propriété utilisée (comme c'est fait pour l'algo d'Euclide au dessus).

Il faudrait aussi du coup adapter le reste de l'article, restreindre la définition à la première actuelle dans le seul cas non nuls, donc réintroduire ensuite les deux définitions, etc. Je pense d'ailleurs que l'article "Plus grand commun diviseur de nombres entiers" devrait correspondre à l'article en:Greatest common divisor. L'article Plus grand commun diviseur, est dans un triste état actuellement. Il est naturel de présenter la notion pour les entiers, et de généraliser ensuite à partir de celle-ci (en fin d'article !). Il peut y avoir peut-être besoin d'article(s) spécialisé(s) pour certaines généralisations. Proz (discuter) 27 septembre 2021 à 18:18 (CEST)

Réponses sur quelques points

• Anthyphérèse : mes sources n'utilisent pas le terme mais je trouvais que cela ne coutait rien de faire cette petite ouverture (dispensable)
• Algorithme d'Euclide : les deux sources la présente sur un exemple avec division euclidienne. Initialement, j'avais envisagé de ne pas la mettre avant de m'apercevoir qu'il est possible de la présenter sans tout l'arsenal actuellement dans l'article (schéma algorithmique, pseudo-code, démonstration...) d'où sa présence dans ma proposition
• Mise au même niveau des méthode de recherche. Deledick présente d'abord l'ensemble des diviseurs, puis l'algorithme d' Euclide, puis la décomposition en facteurs premiers sans porter de jugement de valeur - La petite encyclopédie présente de front l'ensemble des diviseurs et la décomposition en facteur premiers puis l'algorithme d'Euclide en précisant que la décomposition en facteurs premiers peut se révéler fastidieuse. Je pense que ce parti-pris de mise au même niveau provient du fait que l'on se place dans le cadre des maths élémentaires avec des petits nombres. Ailleurs on devrait pouvoir trouver qu'en pratique, l'algorithme d'Euclide est la méthode la plus performante.
• Sur les définitions : Le RI ne parle en fait déjà que des entiers non nuls (presque sous-entendus positifs car l'exemple ne traite que le cas positif). En glissant la section approche élémentaire entre la section notation et la section Définition on se laisse la liberté d'élargir et d'affiner la définition (élémentaire) justement dans la section définition qui est amha bien faite et n'aurait pas besoin d'être modifiée.

Ce qu'il y a de bien avec une proposition c'est qu'elle peut servir de support de réflexion sans se retrouver in fine dans l'article. Réflexion à prolonger donc. Tu sembles avoir une idée plus précise que moi sur ce que tu comptes mettre dans l'article, je te laisse les rênes, je donnerai mon avis si tu me sollicites. HB (discuter) 27 septembre 2021 à 19:38 (CEST).

Le RI actuel est autant voire plus une introduction, qu'un résumé introductif. On ne peut bien évidemment pas avancer sans avoir une définition, qu'elle soit ou non dans le RI. Je ne vois pas de divergence entre nous là-dessus.

Anthyphérèse : je propose juste de citer le terme, comme actuellement dans l'article (dans la section "élémentaire" ou ailleurs), pas de le faire disparaître.

Algo d'Euclide : autant présenter le même exemple pour les deux versions, mais avec une version soustractive où le reste n'est pas toujours la différence, sinon ça n'est pas très instructif (il suffirait d'adapter l'exemple actuel, en changeant la condition de terminaison, qui devrait être l'égalité dans le cas soustractif, puisqu'on ne fait pas appel à la division). Sinon je suis d'accord qu'on peut se passer de l'organigramme (ça ne se fait plus trop d'ailleurs), et même de pseudo-code (dont on se passe déjà dans la version actuelle).

Efficacité : ne pas dire quelque chose d'utile et simple à comprendre (à développer plus loin bien-sûr) ça m'échappe un peu. Une autre hypothèse est que ce sont des livres sans trop de préoccupation algorithmique (d'ailleurs la "petite encyclopédie" n'est pas exactement un livre de math. élémentaires).

Me laisser les rênes, peut-être... Mais je n'ai pas accès au livre de Deledicq. La "méthode de recherche par divisibilité" est-elle dans Deledicq par exemple ? Proz (discuter) 27 septembre 2021 à 22:41 (CEST)

• Ce qui n'est pas sourcé par Deledicq n'est pas dans Deledicq (le livre en question n'est pas à proprement parler un livre de math mais un survol synthétique de tout ce qu'un jeune de 1993 allait apprendre au lycée, c'est ce qui m'a paru le plus proche d'une encyclopédie spécialisée de niveau élémentaire). Concernant la simplification, il en fait seulement une conséquence de PGCD(kx,ky)=kPGCD (x,y) dans un exemple pgcd(36000, 63000)= 1000×pgcd(36,63)=9000
• très bonne idée de partir du même exemple pour la méthode par soustraction et celle d'Euclide
• Efficacité d'Euclide, nous sommes d'accord
• Laisser les rênes... les sources sont là pour montrer qu'une telle présentation est sourçable, tu peux de confiance prendre l'affirmation et sa source, tu dois aussi pouvoir trouver d'autres sources... et me poser des questions en cas de doute. HB (discuter) 28 septembre 2021 à 07:49 (CEST)

Proposition d'une section «Approche élémentaire»

Bon je propose cette version de section approche élémentaire, qui se placerait après la notation et avant la section Définition et aurait vocation à remplacer la section 5. Comme je l'ai déjà dit, c'est la démarche mise en place dans les deux ouvrages que j'ai mis en source. Ce faisant, j'ai conscience d'empiéter sur le travail de Proz de ces derniers jours et de faire un retour en arrière. D'où ma demande de validation. HB (discuter) 27 septembre 2021 à 15:19 (CEST)

Introduction à la notion

Si on considère deux entiers naturels non nuls, a et b, on peut s'intéresser à leurs diviseurs respectifs et à l'ensemble des diviseurs communs aux deux nombres.

Par exemple, les diviseurs de 24 sont {1, 2, 3, 4, 6, 8, 12, 24} et ceux de 30 sont {1, 2, 3, 5, 6, 10, 15, 30}. Les diviseurs communs à 24 et 30 sont {1, 2, 3, 6}. C'est l'intersection des deux ensembles précédents.

Le plus grand de ces diviseurs communs, appelé plus grand commun diviseur, est 6.

On écrira donc : PGCD(24, 30) = 6

Le nombre 1 est diviseur de tout nombre, il sera donc toujours diviseur commun de deux nombres a et b. Il arrive que ce soit le seul. C'est alors le plus grand diviseur commun des deux nombres et ces nombres sont appelés nombres premiers entre eux.

Par exemple, le seul diviseur commun à 35 et à 24 est 1, PGCD (35, 24) = 1 et 35 et 24 sont premiers entre eux.

La recherche de diviseurs communs et du plus grand d'entre eux est un outil utile dans les simplifications de fractions.

Ainsi, puisque 24 et 30 ont pour PGCD 6, on peut simplifier la fraction

${\frac {24}{30}}={\frac {6\times 4}{6\times 5}}={\frac {4}{5}}$

La notion se généralise à la recherche du plus grand diviseur de plus de deux nombres et permet alors de simplifier des équations.

Le pgcd de deux entiers relatifs non nuls est le pgcd de leurs valeurs absolues.

Recherche d'un PGCD par soustractions successives et algorithme d'Euclide

Si a > b, un diviseur commun à a et b est aussi un diviseur commun a a-b et b, et inversement. Donc PGCD (a, b) = PGCD (a-b, b).

Cette propriété fournit une méthode de recherche de PGCD en diminuant la taille des nombres. C'est la méthode d'anthyphérèse.

Exemple :

Ainsi

PGCD(42, 24) = PGCD (42 - 24, 24) = PGCD (18, 24) = PGCD (24-18, 18) = PGCD(6, 18)

Comme 6 est un diviseur de 18, c'est bien le plus grand diviseur de 6 et 18 et donc de 42 et 24

Une méthode plus efficace consiste à prendre, non pas le résultat d'une soustraction mais le reste par la division euclidienne. Cette méthode s'appelle l'algorithme d'Euclide.

Exemple :

Ainsi, pour cherche le PGCD de 138 par 60, on divise 138 par 60 :

138 = 2 × 60 + 18

PGCD (138, 60} = PGCD (60, 18}

On divise 60 par 18

60 = 3 × 18 + 6

PGCD (138, 60} = PGCD (60, 18} = PGCD (18, 6}

Comme 6 est un diviseur de 18, c'est bien le plus grand diviseur de 6 et 18, et donc de 138 et 60

Recherche d'un PGCD à l'aide de la décomposition en facteurs premiers

La décomposition en facteurs premiers d'un entier facilite la découverte de ses diviseurs: les diviseurs de a n'ont dans leur décomposition en facteurs premiers que les nombres figurant dans la décomposition de a avec un exposant au plus égal à leur exposant dans la décomposition de a.

Un diviseur commun à a et b ne peut avoir dans sa décomposition que des facteurs apparaissant à la fois dans les décompositions de a et de b et l'exposant ne peut pas dépasser le plus petit des exposants rencontrés

Exemple :

Ainsi

360 = 2×2×2×3×3×5 = 2³×3²×5

et

48 = 2×2×2×2×3 = 2⁴×3

On remarque que les facteurs premiers communs sont 2 et 3. Le nombre 2 apparaît avec les exposants 3 et 4, donc son plus petit exposant rencontré est 3. Pour 3, le plus petit exposant rencontré est 1 (puisque 3 = 3¹). Le PGCD de 360 et 48 est donc 2³×3 = 24.

S'il n'existe aucune facteur premier commun aux deux décompositions, le PGCD des deux nombres est 1.

Recherche d'un PGCD par simplifications successives

Si d est un diviseur commun à a et b, on peut simplifier a et b par d et rechercher le PGCD des nouveaux nombres

PGCD (a, b = d × PGCD (a/d, b/d)

Exemple :

Ainsi

PGCD(360, 48) = 6 × PGCD (60, 8) = 6 × 2 × PGCD (30, 4) = 6 × 2 × 2 × PGCD (15, 2)

Comme 15 et 2 sont premiers entre eux, on a

PGCD(360, 48) = 6 × 2 × 2 = 24

Bibliographie

• André Deledicq, Mathématiques Lycée : tout le programme de la seconde à la terminale, Éditions de la Cité, 1998
• W. Gellert, H. Küstner, M. Hellwich et H. Kästner (trad. de l'allemand par un collectif, sous la direction de Jacques-Louis Lions), Petite encyclopédie des mathématiques [« Kleine Enzyklopädie der Mathematik »], Didier, 1980