PGCD : 4 MÉTHODES. Quelle sera ta préférée ?
Вставка
- Опубліковано 1 чер 2024
- 🎯 Tu veux la solution pour devenir solide en maths 💪 ? C'est ici : hedacademy.fr/p/notre-methode
On apprend à calculer des PGCD avec 4 méthodes différentes.
PGCD : Plus Grand Diviseur Commun.
Méthode 1: on liste les diviseurs de chaque nombre.
Méthode 2 : les soustractions successives.
Méthodes 3 : l'algorithme d'Euclide.
Méthode 4 : décomposition en facteurs premiers.
Plan de la vidéo :
00:00 Introduction et enjeux
00:29 C'est quoi le PGCD ?
01:05 Méthode 1 : on liste
02:49 Méthode 2: les soustractions
04:52 Méthode 3 : l'algorithme d'Euclide
08:389 Méthode 4 : ma préférée
15:59 Morale de la vidéo
Le PGCD provient de l'anglais : il note le plus grand diviseur commun GCD (pour "Greatest Common Divisor"). Les français se sont donc basé dessus en rajoutant le P au début car le superlatif anglais est à la fin de "Great".
Et vive l'algorithme d'Euclide, car très rapide une fois pris en main et plus fiable que la décomposition en facteurs premiers :)
La première et la 4ème méthode m'était connues. En revanche, j'ai découvert les deux autres. Merci beaucoup.
Salut merci encore, je pratique tout le temps la décomposition en nombres premiers pour moi aussi c'est ma méthode préférée
En informatique la méthode par la soustraction est la plus rapide. Mais pourquoi pas la méthode par division qui en moyenne à moins d'étapes. Tous simplement parce que soustraction coute moins cher qu'une division. entre 3 ou 4 fois moins. Dans cette vidéo, il aurait été intéressant de démontrer les méthode 2 et 3.
Bonjour,
Merci beaucoup pour ces explications, nous avons fait un TP en programmation langage C avec la méthode 2 (soustractions successives).
À mon avis c'est plus simple à programmer.
Bonne journée
Je me souviens avoir vu ces méthodes en classe de 5ème. Plus tard en math sup, on a parlé de nombres, pas forcément premiers, mais premiers entre eux, c'est à dire dont que PGCD est 1.
Ça m'a plu. Et j'ai un penchant pour la méthode 3 😊
Toujours aussi magnifique 🎉 ma méthode favorite est la quatrième 💯
merci pour tes expliquations grace a toi je pourrais peut etre reussir mon ceb grace a toi
Eyant fait ma scolarite en Suisse, dans le canton de Vaud, j'ai bien apris par les terme de PGDC et PPMC.
C'est le cas dans toute la partie francophone de Suisse.
C’est quoi ça? 😂
La méthode 3 me paraît la plus rapide.
Mais la méthode 4 est plus classe !
superbe vidéo merci professeur. :)
Bonjour,
je ne connaissais que la méthode quatre !
Il me serait agréable d’avoir la démonstration des autres méthodes !
Bonne journée
Un bon rappel ! Merci beaucoup
bonjour
à faire avec du papier et un crayon, la méthode 4 décomposition en facteur premier est la meilleure;
à coder dans un langage comme le C, les soustractions successives sont plus simples à écrire de façon récursive.
int pgcd(int a,int b){
if(a==0) return b;
if(b==0) return a;
if(a==b) return a;
if(a>b) return pgcd(a-b,b);
return pgcd(a,b-a);
}
Wouhaaaaaaa la méthode 4 est terriblement efficace et même jolie je dirais
L'algo d'Euclide étendu permet en plus d'obtenir les coeff d'une relation de Bezout. Pour des nombres premiers entre eux ce sont en plus des inversés multiplicatifs de chaque nombre modulo l'autre.
Bonjour,
La méthode utilisable de tête : on va essayer la décomposition en facteurs premiers : on regarde les 2 nombres : 390 finit par zéro. Merci, c'est sympa. Réflexe : 2 facteurs premiers donnés c'est 2 et 5. Il reste à décomposer 39 : autre réflexe mais là ça saute aux yeux 3 et 9 sont divisible par 3 donc 3+9 aussi donc selon la règle 39 aussi. Mais c'est 3 fois quoi ? c'est pas trop compliqué, c'est 13 et là on s'arrête : 13 est premier. Maintenant on va lister parmi cette petite liste de 4 nombres premiers, lesquels divise 728 :
2 ça marche puisque 728 est paire,
5 ça marche pas car 728 ne finit pas par 0 ou 5
3 ça marche pas car 7+2+8 = 17 qui n'est pas divisible par 3
il reste le plus compliqué : 13 : quand on fait l'opération de tête, c'est un peu la débrouille, il faut trouver des multiples sympas. Or 3 x 13 = 39 qui est proche de 40. Bon on regarde les dizaines de 728, c'est 72. Chouette car on sait depuis la primaire que
9 x 8 = 72. Si 8 divise 72 alors 4 aussi. Si on divise le 8 par 2 on doit surement multiplier le 9 par 2 et en effet
72 = 9 x 8 = 9 x 2 x 4 = 18 x 4. Ok, on a tout pour faire apparaître du 39 dans 728 :
728 = 720 + 8 = 40 *18 + 8 = (39 + 1) x 18 + 8 : d'ici, on sort le 1 x 18, ça fait :
728 = 39 x 18 + 1 x 18 + 8 = 39 x 18 +18 + 8 on sens poindre la fin : 18 + 8 ça fait 26 autrement dit 2 x 13 et on se rappelle
39 = 13 x 3 et donc
728 = 39 x 18 + 18 + 8 = 13 x 3 x 18 + 13 x 2 on factorise : 728 = 13 x (3 x 18 +2) donc peu importe ce que vaut 18 x 3 + 2 on a que 728 est divisible par 13
On a nos 2 diviseurs premiers communs 2 et 13 et donc le PGCD est 2 x 13 soit 26.
C'est très long à écrire mais il ne faut que quelques secondes pour le penser. Sinon il faut poser l'opération mais plus difficile à faire de tête et plus de risque d'erreur de calcul.
A bientôt
Méthode 4 pour moi, parce que j'ai appris comme ça. En 1976.
Merci !
J'avais oublié et j'aime énormément l'algorithme d'Euclide !
Mais j'ai cherché à comprendre la logique : POURQUOI passe-t-on d'un PGCD, donc de multiplications à un ensemble de soustractions / additions (avec le reste) et POURQUOI ça marche ^^
Et en fait la lumière m'est venue en voyant le tableau (c'est un peu long désolé mais passionnant !) :
Tout est dans la factorisation !
Comme 52 = 26 x 2
Alors 338 = 52 x 6 + 26
s'écrit 338 = (26 x 2) x 6 + 26
donc 338 = 26 x 13 => en factorisant
Miracle, la factorisation a enlevé l'addition !
Mais mieux que ça, elle nous dit que 338 est aussi divisible par 26 !
Et au départ on se dit qu'on s'en fout ! A tort ^^
Car 390 = 338 + 52
s'écrit 390 = (26 x 13) + (26 x 2)
donc 390 = 26 x 15
Et enfin 728 = 390 + 338
s'écrit 728 = (26 x 15) + (26 x 13)
donc 728 = 26 x 28
En fait, la redescente par division euclidienne jusqu'au reste nul permet de n'avoir que des "morceaux" divisibles par un même nombre inconnu, qui s'avère être 26 en fin de compte.
Tous nos résultats intermédiaires sont divisibles par 26 aussi (52 et 338).
Du coup, les quotients et les restes de toutes nos divisions euclidiennes sont divisibles par 26, ce qui est génial car en factorisant on peut virer ces additions qu'on ne saurait voir !
Il ne reste qu'à comprendre pourquoi c'est forcément le plus grand "morceau" possible pour diviser ces nombres, ça je ne l'ai pas encore ^^
Et je suis beaucoup trop hypé par une histoire de PGCD mais l'arithmétique je trouve ça juste trop bien ^^
PGCDDDDéééééééé !
Moi j'ai utilisé la méthode des décompositions successives, jusqu'à obtenir deux nombres premiers entre eux, ce qui correspond plutôt à la méthode 4 (il se trouve qu'avec 728 et 390, on ne tombe que sur des facteurs premiers - 2 puis 13 - mais j'ai cherché tous les facteurs communs et pas juste les nombres premiers, donc ce n'est pas la méthode 4 au sens strict - en sachant en plus que je me suis arrêté quand je suis tombé sur des nombres premiers en eux, mais pas des nombres premiers tout court - en l'occurrence 28 et 15).
Je préfère aussi la 4. Pas sûr que ce soit la plus rapide (quoique ça dépend de l'exercice), mais c'est la plus amusante !
Merci
Pour l’anecdote, ca me fait toujours rire de lire sous la plume des journalistes (ou d’entendre dans la bouche de politiques) l’expression « le plus _petit_ dénominateur commun » 😅
Personnellement je n'avais jamais vu les méthodes 1 et 2, la 4 est pour moi la plus puissante parce qu'elle peut servir à autre chose que le PGCD.
Notez que l'algo d'Euclide ne demande pas de connaitre les nombres premiers.
Pour les gros nombre (imaginez 1000 décimales) , c'est un avantage car vous n'avez pas la liste des nonbres premier jusqu'a 500 decimales.
Encore faut il pour une machine savoir calculer avec des entiers de 1000 décimales.
Rassurez vous , si votre machine sait faire avec 8 bits (3 decimales) , 16 (5), 32 (7-8?) ou 64 (16-17?), on y arrive assez facilement.
C'est pas très compliqué à faire. On travaille alors avec des tableaux d'entiers.
C'est comme ca qu'on donne des milliers de décimales à pi par exemple, c'est rien pour un ordinateur.
Notez que dans la vraie vie 17 décimales , c'est sans intérêt , on a pas de mesures assez fines pour ca.
Par contre , il y a quelques mois , sur un certain calcul , j'ai eu la surprise de voir qu'une précision de départ à moins de 9 décimales donnait des résultat complètement minables alors que j'attendais une précision de 3 chiffres en sortie (mesure classique).
J'ai compris que ma méthode , dans les faits était minable.
Un instrument de mesure à 9 décimale , ca court pas les rues et ca coute cher et des fois ca n'existe pas.
Des mecs ont des méthodes bien meilleures que la mienne sur le sujet.
J'aime toutes les méthodes même si j'ai le réflexe de faire la 4eme 😅
Dans le cas général la méthode 3 est plus rapide que la méthode 4 car la décomposition RAPIDE en facteurs premiers d'un GRAND nombre est un problème ouvert en informatique. Et le fonctionnement de nos cartes bleues et des sites Web en HTTPS dépendent du fait que cette décomposition est difficile à faire. Sinon vidéo intéressante; j'aime bien.
Totalement d'accord, surtout que la méthode 4 devient vite infaisable de tête quand il s'agit de connaître sa table de 211 ou de 1721 (des nombres premiers d'après Wikipedia je n'ai pas vérifié haha), ou même plus raisonnablement sa table de 17 ou de 43.
Soustraction est la meilleure hehe😅
Les méthodes 1 et 4 ont une logique évidente. Par contre dans les 2 et 3 il faudrait encore démontrer que le résultat est un PGCD.
moi je préfère la décomposition en facteurs premier car j'adore le calcul mental
Étant donné les nombres il faut un peu de temps pour expliquer la 4 je pense. Informatiquement parlant la 2 semble intéressante en raison d'une boucle itérative devant converger vers 0. Jamais essayé en pratique tout comme la 3.
Je vois pas trop la différence entre la méthode 1 et la 4.
Au final c'est pareil sauf qu'on réduit tous les diviseurs en nombres premiers.
moi j’aime bien la méthode directe pour obtenir les nombres de Bézout
Perso je fait la 4ème méthode car je la trouve beaucoup plus simple et c'est la seule que j'ai appris
team soustraction ici. La plus simple en fait.
J’aime bien que tu commences la vidéo en disant que pour des grands nombres on va pas le faire de tête et que ta première méthode ça soit de lister 😂 PS ta méthode 3 est l’équivalent de la 2 en plus alambiquée, au
lieu de faire des divisions et des soustractions, Autant ne faire des soustractions ! Pour ce qui est de la méthode 4, je t’avoue que s’agissant de nombre qui ont toujours un diviseur commun (par définition), il vaut mieux juste soustraire les nombres (1680 - 1512 = 168) et ça te donne déjà un indicateur car au plus les nombres sont grands, au plus le diviseur commun sera grand et la simple soustraction t’aide beaucoup, ton exemple non pris au hasard est gentil et en fait les maths c’est souvent : les gens simples appliquent la méthode jusqu’au bout et trouve et les autres voient directement l’astuce et passent à la question suivante (dixit ma pro de math de quand tu n’étais pas encore né ou presque)
Peux tu nous expliquer/démontrer pourquoi/comment l'algorythme d'Euclide fonctionne? Je ne comprends pas la logique derrière
Je n'ai appris que la méthode 4, mais pas de cette manière (qui me semble par trop compliquée)...
Nous, pour 1512, on nous montrait ainsi :
1512 | 2
756 | 2
378 | 2
189 | 3
63 | 3
21 | 3
7 | 7
0
Ca consiste à utiliser tous les nombres premiers qui fonctionnent jusqu'à tomber sur un reste nul.
Et on reporte la colonne de droite : 2^3 x 3^7 x 7
Ainsi, pas besoin de se casser la tête avec la division par 3 qui peut devenir 9, obligeant à réflechir plus que nécessaire.
Après avoir décomposer 1512. On divise 1680 par 7; si le reste =0 on a gagné sinon on utilises 3 puis 2 si nécessaire. Peut être plus rapide que de décomposer le second chiffre ?
On cherche le PGCD de 728 et de 390.
On va donc découper chaque terme en faisant une décomposition en facteurs premiers :
728 = 104 * 7
= 52 * 2 * 7
= 13 * 4 * 2 * 7
= 13 * 2 * 2 * 2 * 7
390 = 39 * 10
= 13 * 3 * 5 * 2
On garde que les diviseurs communs à cette décomposition :
PGCD ( 390 ; 728 )
= PGCD ( 13 * 3 * 5 * 2 ; 2 * 2 * 13 * 2 * 7 )
= 26, car seuls 13 et 2 sont communs.
J'adore votre enthousiasme. Hélas, ça me rappelle des mauvais souvenirs de collège 🤮, il y a... 54 ans 😱. Concrètement, ça sert à quoi, le PGCD et le PPCM ?
Sinon il est est important de rappeler le lien qu'il existe entre le PPCM, le PGCD et la multiplication (valeur absolue) de deux nombres , en effet PGCD(a,b)=|axb| / PPCM(a,b) ou PPCM(a,b)=|axb| / PGCD(a,b) , Par exemple, on veut savoir le PGCD de (30 et 4) et bien avec cette formule, cela donne PGCD(30,4)=|30x4| / PPCM(30,4) puis PGCD(30,4)=120 / 60= 2 , bon les calculs sont simples ici, c'était simplement pour montrer le lien qu'il y a entre ces 3 calculs.
Pourquoi ne pas avoir introduit la notation a^b qui est à présent la norme?
Le système d'algorithme d'Euclide paraît plus rapide
slt tu as oulblier les diviseur negatif
Ok super, mais à quoi cela sert il de connaitre le PGCD ?
Demande à chatgpt 😂
La décomposition en nombres premiers permet de simplifier des fractions pour ne pas trainer des calculs inutilement lourds on me fait régulièrement pour des nombres simples au quotidien on dit par exemple 1 personne sur 2 en France au lieu de 30 000 000 sur 60 000 000 par exemple
J'ai toujours du mal avec les nombres premiers. Du coup l'algorithme d'Euclide me parait plus simple.
Perso j'utilise toujours la décomposition en facteurs premiers. Les algos j'arrive jamais à m'en souvenir 😪
je prefere l algo d euclide
Un épisode bêtisier me paraît indispensable ! 😅
Le timing de la méthode 4 n'est pas pris en compte
Autre méthode: Chat gpt peut aussi calculer les pgcd. 😂
La décomposition en facteur premier est tellement mal expliquée alors qu'elle est si simple. Dommage. Pourquoi tout compliquer en voulant faire des raccourcis ?