Pouvez vous me donner une méthode simple pour calculer le plus grand diviseru commun?
2006-12-09 06:27:55 · 11 réponses · demandé par Olivier 1 dans Sciences et mathématiques ➔ Mathématiques
On cherche le PGCD de 15 et 12.
Les diviseurs positifs de 15 sont : 1, 3, 5, 15.
Les diviseurs positifs de 12 sont : 1, 2, 3, 4, 6, 12.
On obtient donc d12,15 = {1,3}
On en déduit pgcd(12, 15) = 3.
Dans la pratique, on utilise l'algorithme d'Euclide
Soient deux entiers naturels a et b, dont on cherche le PGCD. Le cas où a ou b est nul ne nécessite aucun algorithme ; on l'exclut. Une suite d'entiers (an)n est définie par récurrence de pas 2, plus précisément par divisions euclidiennes successives ; la suite est initialisée par a0 = a,a1 = b, puis propagée par la règle de récurrence : tant que an + 1 est non nul, an + 2 est défini comme le reste de la division euclidienne de an par an + 1.
On commence donc par calculer le reste de la division de a par b, qu'on note c ; puis on remplace a par b, puis b par c, et on réapplique le procédé depuis le début.
On obtient ainsi une suite, qui vaut 0 à un certain rang ; le PGCD cherché est le dernier reste non nul.
Exemple [modifier]
Calculons, par exemple, le pgcd de 1071 et 1029 (égal à 21) par cet algorithme avec les étapes suivantes :
a b c
1071 1029 42
1029 42 21
42 21 0
21 0
2006-12-09 06:33:59 · answer #1 · answered by Pulsar 6 · 4⤊ 0⤋
alors pour le pgcd par exemple t'a deux nombre très grand comme 5789 et 3146.
pour trouver le pgcd tu soustrait le plus petit au plus grand
ex:5789-3146=2643
puis tu recommance avec le resultat
3146-2643=503
2643-503=2140
2140-503=1637
1637-503=1134
1134-503=631
631-503=128
503-128=375
375-128=247
247-128=119
128-119=9
119-9=110
110-9=101
101-9=92
92-9=83
83-9=74
74-9=65
65-9=56
56-9=47
47-9=38
38-9=29
29-9=20
20-9=11
11-9=2
9-2=7
7-2=5
5-2=3
3-2=1
2-1=1
donc le pgcd est 1
2006-12-11 14:16:32 · answer #2 · answered by Anonymous · 1⤊ 1⤋
voila comment faire:
apres avoir divisé chaque nombre en un produit de puissence de facteurs premiers , le PGCD des nombres s'obtient en multipliant les facteurs communs chacun d'eux affecté de son plus petit exposant.
j'espere que t'a compri car on voit ca en primaire
2006-12-11 13:22:57 · answer #3 · answered by honneur 3 · 0⤊ 0⤋
pour trouver le pgcd le plus facilement possible tu divise le plus grand des deux par le plus petit jusqu'a obtention de deux meme nombre .
2006-12-11 09:59:50 · answer #4 · answered by morgane p 1 · 0⤊ 0⤋
Prends un exemple et on t'aidera.
Essaie de trouver toi même le PGCD de 27 et de 81. Tu factorises chacun en nombres premiers élevés à une puissance convenable. Et reviens nous voir.
2006-12-10 08:36:56 · answer #5 · answered by frenchbaldman 7 · 0⤊ 0⤋
prenez plusieurs nombres
Décomposer les en facteurs communs
Garder les facteurs communs ^à la plus petite puissabce commune
EX A = a^3 b^5 c^2 d
B = a^7 b^4 c^7
c=a^2 bç8 c^4 e
on voit pour a la plus petite puissance commune est a^2
on voit pour b la plus petite puissance commune est b^4
on voit pour c la plus petite puissance commune est c^2
d et e n'étant pas commun ne sont pas facteurs du PGCD
pour le reste on a PGCD = a^2b^4c^2
2006-12-10 02:57:54 · answer #6 · answered by riceau 7 · 0⤊ 0⤋
par exemple, on peut prendre 2 nombres : 5 et 7 :
7 = 5 x 1 + 2
5 = 2 x 2 + 1
2 = 1 x 2 + 0
voilà !
2006-12-09 16:13:08 · answer #7 · answered by didile 3 · 0⤊ 0⤋
attention au indice Algorytme d Euclide
tu cherches le pgcd de a et b alors
supposons que l on a appele a le plus grand nbre des deux
tu divises a par b et tu trouve le reste entier que tu appelle r1
tu divises b par r1 et tu trouve r2
tu divises r1 par r2 et tu trouve r3
ainsi de suite
tu divise r n par r n+1 jusqu a que tu trouves un reste nul
donc le pgcd est le dernier reste non nul
à +++
2006-12-09 15:20:00 · answer #8 · answered by M^3-momo 3 · 0⤊ 0⤋
Prenons 2 nombres : par exemple 18 et 24
18 = 1x18 ou 2x9 ou 3x6,
24 = 1x24 ou 2x12 ou 3x8 ou 4x6,
Diviseurs communs à ces deux nombres entiers :
Les diviseurs de 18 sont : 1, 2, 3 , 6, 9, 18
Les diviseurs de 24 sont : 1, 2, 3, 4, 6, 8, 12, 24
On remarque que :
1 et 6 sont des diviseurs communs de 18 et 24.
6 est le Plus Grand Commun Diviseur de 18 et 24.
6 est le PGCD de 18 et 24
Compris ?
Il suffit de rechercher tous les diviseurs des nombres proposés, et de voir ensuite les DIVISEURS COMMUNS en retenant le plus GRAND
D'accord ?
2006-12-09 14:52:56 · answer #9 · answered by Bitingowl 3 · 0⤊ 1⤋
tu ecrit tes nombres sous la forme de nombres premeirs(que tu peux pas diviser: (2,3,5,7,9,11,13,...) et après tu n'a plus qu'a prendre ceux qui apparaissent dans les deux.
2006-12-09 14:30:40 · answer #10 · answered by boum 4 · 0⤊ 1⤋