Arithmétique (PGCD)

par **marius1986** » 25 Aoû 2009, 21:27

Bien le bonjour à vous, j'ai eu à traiter un exercice et j'ai besoin de votre aide pour l'achever

Voici l'exercice en question:
Exercice: Soient a et b deux entiers naturels et d=pgcd(a,b).
Déterminer pgcd(x,y) dans chacun des cas
a. x=4a+3b, y=5a+4b
b. x=3a+5b, y=7a+12a
c. x=pa+qb, y=ra+sb où ps-qr=1

Solution
J'ai pu trouver les questions a. et b. En effet en utilisant la propriété pgcd(a,b)=pgcd(a,b+am) j'ai pu montrer dans les deux premiers cas que pgcd(x,y)=pgcd(a,b)=d.
Mais quant à la question c. je n'ai pas pu, mais je remarque que les deux premiers cas vérifient la condition donnée en c.
J'ai donc beoion de votre aide
Merci d'avance

par **Zavonen** » 26 Aoû 2009, 06:17

Tu peux déjà voir que tout diviseur commun à x et y divise py-rx.
D'où une première conclusion.
En outre l'autre condition dit que p et q sont premiers entre eux d'une part et que r et s le sont également.

par **mathelot** » 26 Aoû 2009, 07:33

marius1986 a écrit:Exercice: Soient a et b deux entiers naturels et d=pgcd(a,b).
Déterminer pgcd(x,y) dans chacun des cas
a. x=4a+3b, y=5a+4b

bonjour,
si l'on considère les deux égalités comme un système linéaire d'inconnues a et b (et de paramètres x et y) , que dire du déterminant du système ?

que peux-tu en conclure ?

marius1986 a écrit: b. x=3a+5b, y=7a+12a
c. x=pa+qb, y=ra+sb où ps-qr=1

idem pour les deux autres systèmes.

par **abcd22** » 26 Aoû 2009, 12:08

À mon avis, vu la façon dont l'exercice est posé, on attend d'appliquer la même technique que pour a) et b) mais en remplaçant 3, 5, 7, 12 (si je pars de b) par p, q, r, s plutôt que d'appliquer des résultats plus généraux.

par **mathelot** » 26 Aoû 2009, 12:18

bah, ce n'est pas sorcier. :doh:

x=4a+3b
y=5a+4b

comme le déterminant vaut 1 , ça équivaut à
a=4x-3y
b=-5x+4y

par **marius1986** » 26 Aoû 2009, 21:28

Zavonen a écrit:Tu peux déjà voir que tout diviseur commun à x et y divise py-rx.
D'où une première conclusion.
En outre l'autre condition dit que p et q sont premiers entre eux d'une part et que r et s le sont également.

Bien j'ai retenu mais je ne vois pas vraiment où il faut en venir

par **mathelot** » 27 Aoû 2009, 20:04

marius1986 a écrit:Bien j'ai retenu mais je ne vois pas vraiment où il faut en venir

re,
on inverse les trois systèmes de déterminant 1 avec les formules
habituelles

a et b sont combinaison linéaires de x et y et réciproquement,
donc pgcd(a,b)=+- pgcd(x,y)

Arithmétique (PGCD)

Arithmétique (PGCD)

Qui est en ligne