Plus grand commun diviseur

(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)





Posted by: Non inscrit

bonjour,
il parait que le pgcd est au programme de 4è mais désolée moi je n'ai jamais entendu parler de ça alors pouvez-vous m'aider sur ce pb svp??

trouvez tous les couples (x,y) d'entiers naturels et les ranger dans l'ordre du x croissant.

xy=7776
pgcd(x,y)=18

merci d'avance


Posted by: khivapia

Citation:
il parait que le pgcd est au programme de 4è mais désolée moi je n'ai jamais entendu parler de ça alors pouvez-vous m'aider sur ce pb svp??




le message est sans doutes à poster dans la section collège...



Pour t'aider : le pgcd de x et y est le plus grand des diviseurs communs à x et y.

Une méthode : regarder tous les couples (x,y) de diviseurs de 7776 tels que xy = 7776 et pour chacun, écrire la liste de leurs diviseurs et parmi ceux qui sont en communs à x et y, vérifier que 18 est le plus grand. Eliminer les couples x,y qui ne conviennent pas id est ceux dont le pgcd n'est pas 18...

Par exemple : (1,7776) qui ont pour pgcd 1 ne conviennent pas... Mais (432, 18) convient !


Posted by: Chimerade

Citation:
Posté par Non inscrit
bonjour,
il parait que le pgcd est au programme de 4è mais désolée moi je n'ai jamais entendu parler de ça alors pouvez-vous m'aider sur ce pb svp??

trouvez tous les couples (x,y) d'entiers naturels et les ranger dans l'ordre du x croissant.

xy=7776
pgcd(x,y)=18

merci d'avance


D'accord avec Khivapia ! C'est définitivement à placer dans la rubrique "collège" !

Etablir la liste de tous les couples de nombres dont le produit fait 7776 et pour chaque couple établir la liste de tous les diviseurs de chacun des deux nombres du couple, déterminer le plus grand diviseur commun aux deux nombres et vérifier que c'est bien 18, me paraît très long. Il y a 18 couples différents de facteurs dont le produit fait 7776 ! Je propose plutôt la méthode suivante.


On veut que le pgcd soit 18.

Cela signifie donc que x=18*p et y = 18*q et que p et q sont premiers entre eux. Le produit xy est donc égal à 18*p*18*q=324*pq
Mais on sait que xy=7776. Donc pq=7776/324 soit 24.

On décompose 24 en produits de facteurs premiers.
On divise 24 par 2 autant de fois que possible :
24 = 2 * 12
12 = 2 * 6
6 = 2 * 3

Donc \Large 24 = 2^3 \times 3
Ne pouvant plus diviser par 2, on essaie de diviser par 3 :

3 = 3 * 1

Donc \Large 3 = 3^1 et \Large 24 = 2^3 \times 3^1

Pour choisir les valeurs de p et q, on doit répartir les quatre facteurs 2,2,2 et 3 parmi les deux nombres p et q, par exemple p=2*2 et q=2*3, ou encore p=2 et q=2*2*3, etc, mais il y a une autre condition : c'est que p et q soient premiers entre eux, c'est-à-dire qu'il n'aient pas de facteurs communs. Cela impose de mettre tous les facteurs "2" sur l'un des deux : p ou q, et tous les facteurs "3" sur l'un des deux. Dans les deux exemples ci-dessus, les facteurs "2" sont répartis sur les deux nombres p et q et par conséquent p et q ne sont pas premiers entre eux et cela ne convient pas.

De combien de façons peut on alors répartir ces facteurs premiers parmi les p et q ? Eh bien, c'est extrêmement simple : soit les deux groupes (le groupe de facteurs "2" et le groupe de facteurs "3") sont ensemble, soit ils sont séparés. Il n'y a donc que deux façons :

Façon 1 : \Large p = 2^3 \times 3^1 et \Large q = 1
Façon 2 \Large p = 2^3 et \Large q = 3^1

Pour la façon 1 :

p=24 q=1
donc x=18*24 = 432 et y=18*1 = 18 ! Premier couple (18,432)

Pour la façon 2 :

p=8 q=3
donc x=18*8 = 144 et y=18*3 = 54 ! Deuxième couple (54,144)

Et c'est fini !










-