Inscription / Connexion Nouveau Sujet
le PGCD
bonjour a tous, voila j ai un petit probleme c'est par rapport au PGCD est ce que quelqu'un pourrait m expliquer clairement ce que c'est s' il vous plait 
Bonjour,
Le PGCD est le ``Plus Grand Commun Diviseur''. 
Autrement dit, le PGCD de a et de b, noté PGCD(a,b), est le plus grand nombre qui divise à la fois a et b (a/PGCD(a,b) et b/PGCD(a,b) sont donc entiers).
Bonjour. Comme son nom ne l'indique pas exactement, le PGCD est le Plus Grand Commun Diviseur.
C'est-à-dire que ce nombre peut diviser deux nombres donnés (par l'énoncé), mais comme il y en a souvent d'autres, celui-là , c'est le plus grand ...
Et voici
... Et voici un exemple : Tu cherches le PGCD de 100 et 60 ...
Il y a beaucoup de diviseurs communs à ces deux nombres :
1, 2, 4, 5, 10, ...
Mais on veut le Plus Grand : en continuant la recherche, on trouve 20 qui peut diviser nos 2 nombres ( 100 = 20 * 5 ; 60 = 20 * 3 ), mais il n'y en n'a pas de plus grand !
Bonjour,
Le PGCD (plus grand commun diviseur) de deux entiers a et b, c'est le plus grand nombre entier possible qui soit à la fois diviseur de a et diviseur de b. Je pense que ce serait plus clair avec un exemple :
cherchons le PGCD des nombres 420 et 462.
Une méthode possible consiste à commencer par décomposer ces deux nombres en produits de facteurs premiers, et à repérer lesquels sont communs aux deux nombres :
420 = 2² * 3 * 5 * 7 = (2 * 3 * 7) * 2 * 5 = 42 * 10
462 = 2 * 3 * 7 * 11 = (2 * 3 * 7) * 11 = 42 * 11
le PGCD des bombres 420 et 462 est donc 42.
Bonjour
flo : en troisième, on ne connait pas les nombres premiers, seulement les nombres "premiers entre eux"
OK, Lafol, merci pour l'info
(je n'y connais rien en enseignement des maths, mais ça me paraît quand même bizarre d'étudier le PGCD avant les nombres premiers... je crois pourtant me souvenir d'avoir appris au collège la méthode que je viens de donner -c'était il y a environ un quart de siècle, il est vrai [mode 'vieux ronchon' off] 
)
flo : actuellement ils étudient le pgcd sans les nombres premiers, on leur fait vérifier que si d divise a et b, il divise aussi leur différence, donc à coup de différences successives, il divise aussi le reste de la division du plus grand par le plus petit, ce qui débouche sur l'algorithme d'Euclide : on remplace a et b par le plus petit et le reste de la division du grand par le petit, puis on recommence.
dans ton exemple, 420 et 462 : le pgcd de 420 et 462 est aussi pgcd de 420 et 462 - 420 = 42, et là, c'est fini : 42 divise 42 et 420 et c'est manifestement le plus grand diviseur possible de 42. le pgcd est donc 42
c'est bien plus rapide que la décomposition en facteurs premiers (surtout pour des nombres dont les facteurs premiers sont tous supérieurs à 100, par exemple)
Bonsoir Flo. Oui, c"est plus rapide, et plus savant !...
N'empêche que l'élève moyen de Troisième n'y comprend rien (la preuve !...), et ne sait pas à quoi correspond le terme PGCD (voir les exercices sur le choix des plus grands carreaux à mettre dans une salle de bains ...).
Ah , si on leur dit "algorithme d'Euclide" ... certains connaissent la méthode .. C'est tout ...
Pourquoi faire simple ?...
rebonjour (et désolée pour la réponse tardive)
Exemple : pgcd(4562, 5874) = ?
Dans ce cas précis, la décomposition en facteurs premiers donne :
5874 = 2 * 3 * 11 * 89
4562 = 2 * 2281
Le PGCD est donc 2.
Il m'a fallu environ 3 minutes pour vérifier avec une calculatrice que 2281 est bien un nombre premier.
je n'ai pas essayé la méthode du programme scolaire, mais procéder par soustractions successives pour arriver à 2 à partir de nombres aussi grands ne me paraît pas plus rapide, à première vue... (ce n'est qu'une opinion personnelle, bien sûr
)La méthode d'Euclide : pgcd(4562,5874) = pgcd(4562, 5874-4562=1312)
4562 divisé par 1312 : quotient 3, reste 626
donc pgcd = pgcd(1312,626)
1312 divisé par 626 : quotient 2, reste 60
donc pgdcd = pgcd(626, 60)
626 divisé par 60 : quotient 10, reste 26
donc pgcd = pgcd(60, 26)
60 divisé par 26 : quotient 2, reste 8
donc pgcd = pgcd(26, 8)
26 divisé par 8 : quotient 3, reste 2
donc pgcd = pgcd(8, 2) = 2 car 2 divise 8
/* Début du HS */
Si ça intéresse quelqu'un (pas forcément mitsuke, du moins pas forcément tout de suite 
), j'avais fait un petit programme qui calcule le PGCD d'un nombre en affichant les différentes étapes de l'algorithme d'Euclide (ce que ne fait malheureusement pas la commande gcd()).
C'est en Ti-Basic (testé sur Ti-83+) :
: ClrHome
: Input("X=",X
: Input("Y=",Y
: If Y>X
: Then
: Y->A
: X->Y
: A->X
: End
: Repeat R=0
: ClrHome
: int(X/Y)->Q
: X-Q*Y->R
: Disp X
: Disp "="
: Disp Y
: Disp "*"
: Disp Q
: Disp "+"
: Disp R
: Y->X
: R->Y
: Pause
: End
: Stop
/* Fin du HS */
je suis completement larguer . Si quelqu'un pourrait m'aider . Je ne c'est pas comment resoudre cet exercice .
1) Les nombres 682 et 352 sont-ils premiers entre eux ? Justifier.
2) Calculer le plus grand diviseur commun (PGCD) de 682 et 352.
Si quelqu'un pourrait m'aider . Merci :)
1) ils ne sont pas premiers entre eux puisqu'ils sont pairs tous les deux : il y a au moins 2 qui les divise les deux
2) 682 - 352 = 330, 352 - 330 = 22, or 330 = 11*30 = 22*15 .
le plus grand diviseur commun est 22.
682 = 22*31 et 352 = 22*16
Bonjour L-Lully,
Tu ne dois pas poster ton énoncé dans le sujet de quelqu'un d'autre, il faut que tu crées ton propre nouveau topic.
De cette manière, il ne restera pas dans la liste des messages qui n'ont pas reçu de réponses. Les personnes qui passent, ici, pour aider passent souvent par cette liste, pour apporter de l'aide à ceux qui en attendent.
En étant à la suite de quelqu'un qui a reçu déjà plusieurs réponses, tu risques d'attendre très longtemps !
Pour savoir comment fonctionne ce forum, il faut lire la FAQ = Foire Aux Questions ici : 
[lien]
ainsi que le message qui est en tête de toutes les liste des messages et qui a pour titre ""A LIRE AVANT de poster, merci""
Bonne lecture !
Flo08 :
5874 = 2 * 3 * 11 * 89
4562 = 2 * 2281
comment tu fais pour savoir par quoi on doit multiplier pour obtenir les resultats 5874 et 4562 ?
rebonjour
J'ai fait une décomposition en produits de facteurs premiers en opérant des divisions successives. Exemple :
5874 est pair, donc divisible par 2
---> 5874/2 = 2937 soit 5874 = 2 * 2937
2937 est divisible par 3 (la somme des chiffres est un multiple de 3)
---> 2937/3 = 979 soit 2937 = 3 * 979 soit 5874 = 2 * 3 * 979
979 n'est pas divisible par 7, mais il est divisible par 11.
---> 979/11 = 89 soit 979 = 11 * 89 soit 2937 = 3 * 11 * 89 soit 5874 = 2 * 3 * 11 * 89.
Et 89 est un nombre premier.
Bonsoir Mathecole.... C'est comme pour tout exo en maths, ...ou ailleurs, ... il faut chercher ! ... ça n'arrive pas tout cuit !...
Ici, on t'a montré une décomposition en facteurs premiers ... Donc il faut chercher les diviseurs qui conviennent à chaque nombre...
On commence par 5874 . On divise par 2, on obtient 2937
On ne peut pas diviser à nouveau par 2, alors on essaye par 3 : on obtient 979 .
On ne peut pas diviser encore par 3 , alors on essaye le diviseur (premier) suivant : 5 ... Cela ne va pas . On essaye 7 ... non plus . On essaye 11 : c'est bon, et ça donne 89 .
Et le prochain diviseur ce n'est ni 13, ni 17 ... il faut aller jusqu'à 89 ...
... Je suis d'accord avec toi, ce n'est pas un exercice qui sera donné au Brevet,- les deux nombres choisis, surtout 4562, ayant été apportés pour montrer que la seule méthode valable était celle d'Euclide ??? .
Salut à tous
Il en est de ça comme pour beaucoup de choses, les nouvelles méthodes ne sont pas toujours les meilleures.
A toutes fins utiles avec google, si on tape "nombres premiers", on peut obtenir la liste des nombres premiers inférieurs à 50000. Quand on a cette liste, pour ma part, je préfère la décomposition en nombres premiers à la méthode d'Euclide, surtout si on a une calculatrice.
Annuler
connectez vous