Recherche d un PGCD et équation

[YASMIN2016]

Salut
je n arrive a utiliser les congruences pour pouvoir repondre a la question 2 de l exercice suivant

Soit l équation (E) 5x + 4y = 360.

1) Résoudre l équation (E)

2) En utilisant les congruences déterminer l’ensemble des couples (x ; y) d’entiers relatifs solutions de l équation tels que le PGCD(x,y)= 6

Réponse

1) J ai trouvé comme ensemble de solutions F= { (x=44 + 4k ; y=35 − 5k) ou k entier relatif }.



2) Je n est pas trouvé une solution de la question

comment résoudre la question et donner moi une solution
merci

[Ben314]

Salut,
Il faut utiliser le fait que pgcd(a,b)=pgcd(a,b+ka) pour diminuer les coeffs qu'il y a devant les k jusqu'à en faire disparaitre un :
pgcd( 44+4k , 35-5k ) = pgcd( 44+4k , (35-5k)+(44+4k) ) = pgcd( 44+4k , 79-k ) = pgcd( (44+4k)+4(79-k) , 79-k ) = ...

[YASMIN2016]

Salut Ben314
donc d après votre méthode en trouve pgcd(x,y)=pgcd(360,79-k) = 6. pgcd(60,q) il faut que le pgcd (60,q)=1
mais la question demande d utiliser les congruences comment je dois repondre

merci

[nodgim]

5 x0 + 4 y0 = 360
il faut x0 multiple de 4 et y0 multiple de 5, car 360 est multiple de ces 2 nombres.
x0 = 4 x1 et y0 = 5 y1
20 ( x1 + y1 ) = 360
x1 + y1 = 18
L'ensemble des solutions (x0, y0) est (4a, 90-5a)

Si on veut PGCD (4a, 90-5a) = 6 il faut a=6b.
===> (24b, 90-30b)
mais si b impair, PGCD=12. Il faut b pair donc : (48b, 90-60b)

L'ensemble des solutions est (48b, 90-60b) avec b premier avec 3 et 5.
Si b est multiple d'un autre p premier, 48b l'est, mais pas 90-60b. Cette précision permet de dire que, quel que soit b, le PGCD sera 6 et pas un multiple de 6.

[Ben314]

donc d après votre méthode en trouve pgcd(x,y)=pgcd(360,79-k) = 6. pgcd(60,q) il faut que le pgcd (60,q)=1

Déjà, pour écrire que pgcd(360,79-k) = 6. pgcd(60,q), il faut que 79-k=6q, donc que k soit de la forme k=79-6q pour un certain entier q.
A la limite (pas obligatoire), on peut écrire ça un peu différemment en écrivant 79-6q=1+6(13-q)=1+6q' donc k doit être de la forme k=1+6q' pour un certain entier q' ce que tu peut écrire si tu veut "k doit être congru à 1 modulo 6".
Dans ce cas, pgcd(x,y)=pgcd(360,79-k)=pgcd(360,78-6q')=6.pgcd(60,13-q') et il reste à regarder pour quelles valeurs de q' on a pgcd(60,13-q')=1.
Vu que pgcd(60,13-q')=pgcd(60,13-q'+60k) pour tout k, on a pgcd(60,13-q')=pgcd(60,r) où r est le reste de la division de 13-q' par 60 c'est à dire 13-q'=60j+r avec j entier quelconque (si tu tient absolument à utiliser des congruence, tu peut écrire que, si a congru à b modulo 60 alors pgcd(a,60)=pgcd(b,60))
Il reste à regarder quels sont les r appartient à {0,1,2,...,59} tels que pgcd(r,60)=1. Comme 60=2²x3x5 ce sont les r non divisible par 2, ni par 3 ni par 5 et avec un peu de courage on peut en dresser la liste (il y en a 16).
Tu termine en disant que k doit être de la forme k=1+6q'=1+6(13-60j-r)=-360j+79-6r avec j entier quelconque et r dans la liste trouvée ci dessus.
Si tu comprend bien la preuve ci dessus, une autre façon de donner le résultat pourrait consister à dire qu'il faut (et qu'il suffit) que k-1 soit divisible par 6, mais que ne soit divisible ni par 2, ni par 3, ni par 5.

[YASMIN2016]

Salut Ben314
merci pour les explications
j aime bien comprendre la deuxième façon (une autre façon de donner le résultat pourrait consister à dire qu'il faut (et qu'il suffit) que k-1 soit divisible par 6, mais que ne soit divisible ni par 2, ni par 3, ni par 5.)
comment tu as trouvé cette façon et surtout d ou provient k-1 divisible par 6 et je n est compris la condition ne soit divisible ni par 2 ni par 3 ni par 5

si possible de m expliquer votre méthode vers une autres valeur du PGCD par exemple pgcd(x,y)=90 ou pgcd(x,y)=120

merci

[YASMIN2016]

Salut nodgim
merci pour ton aide
j aime bien comprendre pourquoi en cherche de nouveaux les solutions de l équation
j ai trouvé les solutions de l équation
ma question c est comment en utilisant les congruences peut on trouvé les solutions avec la conditions PGCD(x,y)=6
donc 6 divise x et 6 divise y équivaut à x=0 mod6 et y =0 mod 6 (= congru)
mais il faut ajouter des conditions car je peux avoir des multiples de 6 donc un PGCD non égale a 6
ma question comment a partir de la décomposition en facteurs premiers de 360=3^2. 2^3. 5 je peux ajouter les conditions qui manquent .
si possible de m expliquer votre méthode sur une autre valeur du PGCD(x,y)=10 et PGCD(x,y)=4

merci

[ayarajaayassmine]

x congru y modulo 6 veut dire : x-y est divisible par 6 (car si x est divisible par 6 et y divisible par 6 alors x-y est divisible par 6

Il existe k de Z telque x-y=6k




si alors et
pour trouver les autres solutions dans Z on prend k= multiples de 3

[YASMIN2016]

Salut ayarajaayassmine
je n est pas compris votre méthode car les solutions contiennent un quotient et on travail dans Z

x=( 8/3)k+40 et y=(-10/3)k+50


si possible de m expliquer votre méthode pour un PGCD(x,y)=180

merci

[Ben314]

comment tu as trouvé cette façon et surtout d ou provient k-1 divisible par 6 et je n est compris la condition ne soit divisible ni par 2 ni par 3 ni par 5

Réponse (en bleu) :

...donc k doit être de la forme k=1+6q' pour un certain entier q' <=> k-1 doit être un multiple de 6 et le q' dont on parle dans la suite est q'=(k-1)/6
...13-q'=60j+r <=> r=13-(k-1)/6-60j
...ce sont les r non divisible par 2, ni par 3 ni par 5 <=> 13-(k-1)/6-60j ne doit être divisible ni par 2, ni par 3, ni par 5.
Comme 60 est divisible par 2,3 et 5, ça veut dire que 13-(k-1)/6 ne doit être divisible ni par 2, ni par 3, ni par 5

[chan79]

si possible de m expliquer votre méthode sur une autre valeur du PGCD(x,y)=10

Salut
on a donc les solutions (4a,90-5a) (voir le post de nodgim)
Pour que 10 divise 4a et (90-5a), il est nécessaire que a soit multiple de 5 et de 2 donc de la forme 10b.
(4a,90-5a) s'écrit (40b,90-50b)
10 est le PGCD si celui de 4b et (9-5b) est 1
soit si le PGCD de 4b et (9-9b) est 1
soit si le PGCD de 4b et (9(1-b)) est 1
b et 1-b sont premiers entre eux.
b doit être pair et non multiple de 3
b=2m
a=10b=20m
Les solutions qui conviennent sont
(80m,90-100m) à condition que m ne soit pas multiple de 3
(à vérifier...)

[ayarajaayassmine]

Salut ayarajaayassmine
je n est pas compris votre méthode car les solutions contiennent un quotient et on travail dans Z

x=( 8/3)k+40 et y=(-10/3)k+50


si possible de m expliquer votre méthode pour un PGCD(x,y)=180

merci

Attention y = (-10/3)k + 40

Vous n'avez pas fait attention quand j'ai dit : il faut prendre k=multiples de 3. et k élément de Z
En procédant de la sorte, les solutions sont des relatifs.
Bon courage !

[ayarajaayassmine]

pour pgcd(x,y)=180
on fait x - y = 180k
après calcul on trouve : x = 80k + 40 et y = -100k + 40
avec k élément de Z.

[Ben314]

pour pgcd(x,y)=180 on fait x - y = 180k <- Absolument pas
après calcul on trouve : x = 80k + 40 et y = -100k + 40 qui, si k=0 nous donne x=y=40 et tout le monde voit bien que pgcd(40,40)=180

Si tu ne sait pas ce qu'est un pgcd, évite de répondre (des c...) aux post qui parlent de pgcd, ça sera mieux pour tout le monde.
Merçi.

[YASMIN2016]

Salut Ben314
merci pour tes remarques
svp j aime que tu me donne plus d explication sur votre dernière façon car je n est pas peux la comprendre et l appliquer sur un autre exemple de PGCD .par exemple PGCD(x,y)=180 .

merci

[YASMIN2016]

Salut Ben314
merci pour tes remarques
svp j aime que tu me donne plus d explication sur votre dernière façon car je n est pas peux la comprendre et l appliquer sur un autre exemple de PGCD .par exemple PGCD(x,y)=180 .

merci

[Ben314]

Pour que 10 divise 4a et (90-5a), il est nécessaire que a soit multiple de 5 et de 2 donc de la forme 10b.
(4a,90-5a) s'écrit (40b,90-50b)
10 est le PGCD si celui de 4b et (9-5b) est 1
soit si le PGCD de 4b et (9-9b) est 1
soit si le PGCD de 4b et (9(1-b)) est 1
b et 1-b sont premiers entre eux.
b doit être pair et non multiple de 3
b=2m
a=10b=20m

Perso, je préfère me ramener systématiquement à pgcd(?,constante)=constante via l'algorithme d'Euclide.
Donc, par exemple ici, ça donnerais

Pour que il faut déjà que divise donc divise :
Et il faut alors que c'est à dire que et, vu que cela signifie que ne doit être divisible ni par ni par et on retombe bien sur ta solution : il faut que soit pair et non divisible par .

[Ben314]

par exemple PGCD(x,y)=180

Début totalement identique au post. précédent, puis :
Pour que il faut déjà que divise donc que ( entier relatif)
Et il faut alors que c'est à dire que donc que ne soit pas divisible par .

[YASMIN2016]

Salut Ben314
merci c est très bien expliquer
mais il reste a déterminer les valeurs de b pour pouvoir écrire la forme des solutions
qui sont les formes des valeurs de b


autre façon pour repondre autrement svp
PGCD(x,y)=180 équivaut a x et y sont divisibles par 180 et x et y non divisibles par 360 ( ou 2)

mais encore on pas utiliser les congruences pour repondre a la question (on a utiliser PGCD(a,b)=PGCD(?;constante)
si possible de repondre en utilisant les congruences
merci

[ayarajaayassmine]

Je m'excuse de la connerie que j'ai faite.
Merci de bien accepter mes excuses.
Personne n'est parfait.