Inscription / Connexion Nouveau Sujet
PGCD deux nombres et équation
salut
si possible de m aider a résoudre la question suivante en utilisant la congruence pour déterminer le pgcd
voici l énoncé de l exercice
On considère dans ZZ , l'équation ( E ) : 2x + 3y = 12 .
Les solutions de (E) x= -3k+6 et y=2k
Déterminer les couples (x,y) solutions de (E) pour chaque valeurs de PGCD(x,y)=d
d=1ou 2 , 3, 4,6,12
j ai essayé ça
si possible de me vérifier la démarché suivante
d=2 ( xcongru a 0mod 2 et x non congru a 0mod 12 ) et (y=0mod 2 et ynoncongru a 012)
d=3( xcongru a 0mod3 et x non congru a 0mod 12 ) et (y=0mod3 et ynoncongru a 012)
d=6( xcongru a 0mod 6 et x non congru a 0mod 12 ) et (y=0mod 6 et ynoncongru a 012)
d=12( xcongru a 0mod1 2 ) et (y=0mod 12 )
d=4
d=1 ??
merci bien
salut
une fois que tu as ::
x = 6 - 3k
y = 2k
il faut ensuite une condition sur k !!!!
d = 1
y est pair
x est multiple de 3
donc k est impair non multiple de 3
donc k = 6u + 1 ou k = 6u + 5
x = 6 - 3(6u + 1) = 6 - 18u - 3 = 3(1 - 6u)
y = 2(6u + 1)
d = 2
x = 3(2 - k)
y = 2k
puisque 2 ne divise pas 3 alors d doit diviser 2 - k donc k
k = 2u
x = 3.2(1 - u)
y = 4u
or u et 1 - u non pas même parité (ils sont même premier entre eux) donc la condition est nécessaire et suffisante ...
on en conclut que d = 4 est impossible ....
je te laisse finir les autres cas ...
merci pour votre réponse carpediem
mais j aime bien comprendre pourquoi d=4 est impossible
pour les cas d=6 d= 3 d= 12 comment faire car je n est pas bien compris votre méthode
est il possible de raisonner avec les congruences
merci bien
en plus j'ai dit une bêtise ... pour d = 4
il suffit de prendre k = 4u + 2 et u impair
alors
x = 3(2 - 4u - 2) = -12u
y = 4(2u + 1)
ensuite il faut que 3u et 2u + 1 soient premiers ... à finir ....
raisonner avec les congruences ne me semble pas suffisant ...
enfin faut voir ...
x = 0 [4] <=> 2 - k = 0 [k]
y = 0 [4] <=> k = 0 [2]
mais ensuite faut poursuivre ....
Bonsoir,
Une idée parmi d'autres.
pgcd ( x , y ) = pgcd ( 6 - 3 k , 2 k ).
En utilisant la propriété pgcd ( a , b ) = pgcd ( a , b + m a ) , ou bien par divisions successives, on peut obtenir par exemple pgcd ( x , y ) = pgcd ( k + 6 , 12 ).
On peut alors considérer les 12 cas : k = 0 ( 12 ) , k = 1 ( 12 ) , ... , k = 11 ( 12 ) et on obtient pgcd ( k + 6 , 12 ).
salut Lancaster et carpediem
j ai essayé
on partant du pgcd ( x , y ) = pgcd ( k + 6 , 12 )
1er cas si 12 divise k+6 alors pgcd ( x , y )=12
2em cas si 6 divise k+6 et 12 ne divise pas k+6 alors pgcd ( x , y )=6
3em cas si 4 divise k+6 et 3 ne divise pas k+6 alors pgcd ( x , y )=4
4em cas si 3 divise k+6 et 2 ne divise pas k+6 alors pgcd ( x , y )=3
5em cas si 2 divise k+6 et 4 ne divise pas k+6 et 3 ne divise pas k+6 alors pgcd ( x , y )=2
6em cas si 2 ne divise pas k+6 et 3 ne divise pas k+6 alors pgcd ( x , y )=1
est il possible de traiter avec les congruences
par exemple pour d=2 il suffit d avoir x congro a 0 modulo 2 et x non congru 0 mod 12 ( ou bien xnon congru a 0mod 3 et xnon congru a 0mod 4
de meme pour y
si possible de me donner une solution avec les congruences
merci bien amicalement
Bonsoir,
r est un entier compris entre 0 et 11.
Si k = r ( 12 ) alors k = r + 12 n avec n entier.
pgcd ( k + 6 , 12 ) = pgcd ( r + 6 + 12 n , 12 ) = pgcd ( r + 6 , 12 ).
si r = 0 alors pgcd ( k + 6 , 12 ) = pgcd ( 6 , 12 ) = 6
si r = 1 alors pgcd ( k + 6 , 12 ) = pgcd ( 7 , 12 ) = 1
etc ...
salut
merci pour votre réponse
il possible de traiter avec les congruences
par exemple pour d=2 il suffit d avoir x congro a 0 modulo 2 et x non congru 0 mod 12 ( ou bien xnon congru a 0mod 3 et xnon congru a 0mod 4
de même pour y
pour les autres valeurs du pgcd j aime bien savoir comment écrire les conditions avec des symboles de congruence
si possible de me donner une solution avec les congruences
merci bien
Annuler
connectez vous