Arithmétique, PGCD, congruence, bezout etc...

par **G0rk4** » 05 Déc 2007, 20:16

Salut, j'ai un petit problème pour un exercice d'arithmétique bien complet que le prof nous a donné. Voila l'énoncé:

On considère l'équiation (E) :

, où x et y sont des entiers.
a) résoudre dans Z² l'équation: 17x=6y
b) Montrer que le couple (-1;-3) est solution particulère de l'équation : 17x-6y=1; en déduire un couple solution particulière de l'équation (E).
c) En déduire tous les couples de Z² solutions de l'équation (E)
d) Montrer que le PGCD des couples solutions de (E) est 1 ou 2
e) Déterminer les couples (x;y) de Z² solutions de (E) dont le PGCD est 2.
f) Déterminer le couple (x0;y0) solution de (E) tel que PGCD(x0;y0)=2 et y0 compris entre 100 et 150 (inclus)

je sèche à partir du d) , je sais que d'après Bezout, il existe deux entier u et v tels que au + bv = PGCD(a;b) donc ici (6k-2)u + (17k-6)v = PGCD(6k-2;17k-6) mais je ne vois pas comment montrer que ce pgcd est 1 ou 2...
Je ne peux donc pour l'instant pas faire le reste de l'exercice sans la réponse à cette question... Merci de m'aider

par **hellow3** » 05 Déc 2007, 21:36

Salut.

Moi je ferais:
d=pgcd(a;b)
Donc d/a et d/b; et d divise toute combinaison linéaire de a et b ...

par **G0rk4** » 06 Déc 2007, 13:24

Merci de ton aide, mais je ne vois pas en quoi on prouve que le PGCD = 1 ou 2 et surtout qu'il n'y en a pas d'autres :s
aidez-moi svp

par **hellow3** » 06 Déc 2007, 13:28

d=pgcd(a;b)
Donc d/a et d/b; et d divise toute combinaison linéaire de a et b ...

donc
d / 17a-6b
donc d/2
donc d=...

par **hellow3** » 06 Déc 2007, 14:19

Tu t'en sors?

par **G0rk4** » 06 Déc 2007, 15:59

ok je vois donc d= 1 ou 2 pour diviser 2 et il n'y a donc que ceux-là.
ensuite PGCD(x;y) = 2 signifie qu'il existe 2 entiers u et v tels que ux + vy = 2
donc x= 6k-2 et y = -17k+6 (est-ce juste ?)

par **G0rk4** » 06 Déc 2007, 16:04

et donc si c'est juste pour le f) -17k+6 est compris entre 100 et 150, donc k est compris entre -8 et -14
Besoin d'une correction, merci :)

par **G0rk4** » 06 Déc 2007, 19:04

help :)

par **hellow3** » 06 Déc 2007, 19:52

ok je vois donc d= 1 ou 2 pour diviser 2 et il n'y a donc que ceux-là.
ensuite PGCD(x;y) = 2 signifie qu'il existe 2 entiers u et v tels que ux + vy = 2
donc x= 6k-2 et y = -17k+6 (est-ce juste ?)

Plutôt, x=6k-2 et y=17k-6, d'ailleurs c'es tce que t'avais trouvé dans ton premier message?

Et pour le e., t'as quoi? ca va t'aider pour le f.

par **G0rk4** » 06 Déc 2007, 20:06

Ok merci hellow, donc pour le f) je reprends la question e) "y=17k-6"
donc 17k-6 est compris entre 100 et 150, donc k est compris entre 7 et 9 (comme c'est un entier)

par **hellow3** » 06 Déc 2007, 20:08

e) "y=17k-6"
T'as ca pour le e.?

Je croyais que c'etais le b.?

par **G0rk4** » 06 Déc 2007, 20:17

non pour le e) j'avais trouvé y = -17k+6, mais tu je croyais que c'était pas bon comme tu m'avais corrigé.

par **G0rk4** » 06 Déc 2007, 20:18

Voila ma question e) PGCD(x;y) = 2 signifie qu'il existe 2 entiers u et v tels que ux + vy = 2
donc x= 6k-2 et y = -17k+6 (est-ce juste ?)

par **hellow3** » 06 Déc 2007, 20:30

G0rk4 a écrit:Voila ma question e) PGCD(x;y) = 2 signifie qu'il existe 2 entiers u et v tels que ux + vy = 2
donc x= 6k-2 et y = -17k+6 (est-ce juste ?)

Je comprend pas comment tu trouves ça.

Moi j'ai dit que si d=2 pgcd de x et y, alors d/x et d/y, donc x et y sont paire.
x=6k-2 est toujours paire. Par contre pour que y=17k-6 soit paire,
il faut que 2/17k et 2/-6. 2/-6 OK. mais 2/17k ssi k paire.

T'en dis quoi?

par **G0rk4** » 06 Déc 2007, 20:54

ben ça me parrait juste
moi ce que je voyais c'était : PGCD(x;y) = 2 signifie d'après bezout qu'il existe 2 entiers u et v tels que ux + vy = PGCD(x;y) = 2 d'accord ?
on a l'équation (E) qui est : 17x - 6y = 2
donc si x = 6k-2 et y = -17k-6 ça marche quelque soit k appartenant à Z, non ?
Doit y avoir une ***** dans mon résonnement... Mais merci pour ta réponse. :)

par **hellow3** » 06 Déc 2007, 21:08

T'es sur que Bezout s'applique quand on a des nombres qui sont pas premiers?

par **G0rk4** » 06 Déc 2007, 21:15

Ben aussi sur que mon prof de math en tout cas :
Soient a et b deux entiers. p = PGCD(a;b)
Il existe deux entiers u et v tels que au + bv = pgcd(a;b)
démonstration: en remontant l'algorythme d'Euclide.

par **G0rk4** » 06 Déc 2007, 21:17

mais ta réponse semble aussi juste, c'est bizarre :s

par **hellow3** » 06 Déc 2007, 21:34

OK, merci.

Par contre:"on a l'équation (E) qui est : 17x - 6y = 2
donc si x = 6k-2 et y = -17k-6 ça marche quelque soit k appartenant à Z, non ?
"

17(6k-2) -6(-17k-6)=17*6k-34 +6*17k +36= 2*6*17k +2
? quel que soit k?

par **G0rk4** » 06 Déc 2007, 21:58

ralala j'ai du mal, excuse-moi c'est y = 17k-6 pour que les "k" s'annulent

Arithmétique, PGCD, congruence, bezout etc...

Arithmétique, PGCD, congruence, bezout etc...

Qui est en ligne