Pgcd et congruence

[olivier 2020]

salut

j ai un exercice d arithmétique
il y a un problème au niveau
des questions 2 et 3
si possible de me donner une réponse avec les congruences ou autres méthodes

Exercice
On considère dans Z;)Z , l’équation ( E ) : 7x + 4y = 20
Qui admet comme solution (4k, -7k+5)
soit (x,y) une solution de (E)
1)Quelles sont les valeurs possibles de PGCD(x,y)
On pose d = x ;) y ; d divise x et d divise y donc d divise7x + 4yet d divise 20 d’où d ;);) 1 , 2 , 4 , 5,10,20;)

En utilisant les congruences
2)Déterminer les couples (x,y) solutions de (E) tel que PGCD(x,y)=5
3)Déterminer les couples (x,y) solutions de (E) tel que PGCD(x,y)=2

merci

[Ben314]

Salut,
Je pense que je n'aurais pas répondu comme toi à la 1), mais a mon avis tu as raison, c'est à dire que c'est bien ça qui est attendu comme réponse.

Perso, j'aurais plutôt écrit que (et c'est ce qu'il faut faire pour le 2, et le 3) :
pgcd(x,y)=pgcd(4k,-7k+5)=...

En utilisant le résultat que tu as du voir, à savoir que pgcd(a,b)=pgcd(a,b+na) (pour n'importe quel n)
Par exemple, ici, ça permet de faire diminuer les coeff. qu'il y a devant les k dans le pgcd (en fait, c'est un peu comme l'algorithme d'Euclide... et pour cause...)
Je te fait la première étape ;
pgcd(4k,-7k+5)=pgcd(4k,-7k+5+2.4k)=pgcd(4k,5+k)

ensuite...

[zygomatique]

salut

tout est dit ici :: http://www.ilemaths.net/forum-sujet-641640.html

....

[georgets555]

salut
mais il manque des détails et réponse non complète car il ne donnent pas de réponses avec les congruences http://www.ilemaths.net/forum-sujet-641640.html

reprenons l idée de Ben314 mais j aime savoir comment utiliser les congruences pour ce type de questions

j ai essayé de terminer

Pgcd(4k,5+k)=pgcd(5+k,-20)=pgcd(5+k,20)
Pgcd(5+k,20)=5
5+k=5 p et 20=5 x 4= 5 x2x2 et faut que p ne soit pas un multiple de5 (10 ou 20) 4 p=4q+1 ou p =4q+2 ou p=4q+3 et non multiple de 2 donc p =2 n+1
Pgcd(5+k,20)=2
5+k=2 p et 20=2*10 =2*(5*2) donc p ne soit pas un multiple 2( 10 ou 20)

a bientôt

[Ben314]

Pgcd(4k,5+k)=pgcd(5+k,-20)=pgcd(5+k,20)
Pgcd(5+k,20)=5

Oui, perso, c'est ce que j'aurais écrit.
Aprés, d'utiliser directement les congruences, par exemple modulo 5 pour traduire que le pgcd doit être égal à 5, c'est pas forcément le plus rapide du fait que ça va uniquement traduire le fait que 5 divise les deux, mais ça traduira pas que 5 est le plus grand diviseur.
Je pense que, perso, pour conclure, j'aurais sans doute commencé par écrire que pgcd(5+k,20)=pgcd(r,20) où r est le reste de la division de 5+k par 20 donc 0<=r<20 et 5+k=r modulo 20 donc le résultat ne dépend que de la congruence de k modulo 20.

Arrivé à ce point, il y a plusieurs de façon de finir vu que de toute façon y'a que 20 cas à étudier (les différentes valeurs de r) :

- Méthode un peu empirique :
Faire un tableau avec en première ligne le reste de la division de k par 20, en 2em ligne le reste r de la division de k+5 par 20 et en 3em ligne le pgcd(r,20). C'est pas super théorique, mais comme 20 est pas super grand, ça marche bien et ça répond aux deux questions en même temps.

- Autre méthode :
Comme 20=5x2x2, pour que le pgcd(20,r)=5, il faut et il suffit que r soit divisible par 5 (donc 0,5,10 ou 15) mais pas par 2, donc r=5 ou 15 ce qui signifie qu'il faut que 5+k soit congru à 5 ou 15 modulo 20 c'est à dire à 0 ou 10 modulo 20, soit encore congru à 0 modulo 10.
Plus ou moins idem pour 2 : pour que le pgcd(20,r)=2, il faut et il suffit que r soit divisible par 2 mais pas par 4 ni par 5, donc r dans {2,6,14,18} donc k congru à 6-5=1 ou 14-5=9 ou 18-5=13 ou 2-5=-3=17 modulo 20 (qu'on peut pas vraiment écrire plus simplement en terme de congruence)

- La même chose rédigé de façon un soupons plus théorique (et sans utiliser r) :
Comme 20=5x2x2 pour que pgcd(5+k,20)=5, il faut et il suffit que 5+k soit divisible par 5 mais pas par 2 c'est à dire 5+k=0 [5] et 5+k=1 [2] soit encore k=0 [5] et k=0 [2] qu'on peut (si on veut) "remonter" en k=0 [10].
Pour que pgcd(5+k,20)=2, il faut et il suffit que 5+k soit divisible par 2 mais pas par 4 ni par 5 c'est à dire 5+k\=0 [5] (non congru) et 5+k=2 [4] soit encore k\=0 [5] et k=1 [4] qu'on peut (si on veut) "remonter" en k=1 ou 9 ou 13 ou 17 [20].

[zygomatique]

salut
mais il manque des détails et réponse non complète car il ne donnent pas de réponses avec les congruences http://www.ilemaths.net/forum-sujet-641640.html

reprenons l idée de Ben314 mais j aime savoir comment utiliser les congruences pour ce type de questions

j ai essayé de terminer

Pgcd(4k,5+k)=pgcd(5+k,-20)=pgcd(5+k,20)
Pgcd(5+k,20)=5
5+k=5 p et 20=5 x 4= 5 x2x2 et faut que p ne soit pas un multiple de5 (10 ou 20) 4 p=4q+1 ou p =4q+2 ou p=4q+3 et non multiple de 2 donc p =2 n+1
Pgcd(5+k,20)=2
5+k=2 p et 20=2*10 =2*(5*2) donc p ne soit pas un multiple 2( 10 ou 20)

a bientôt

et il n'y a pas tout là ::

(x, y) = (4k, 5 - 7k)


pgcd(x, y) = 5


5 divise 4k et ne divise pas 4 donc d'après le théorème de Gauss 5 divise k

posons k = 5m

(x, y) = (20m, 5 - 35m)

donc 20 divise x et 20 (donc 10) peut être pgcd de x et y (d'après la question précédente)

donc ni 20 ni 10 ne divisent y

or y = 5 - 35m = 5(1 - 7m) donc ni 2 ni 4 ne divisent 1 - 7m

à toi de finir ....

il est trivial de finir ....

[georgets555]

salut Ben314
svp expliquer moi plus claire cette ligne
(( Pour que pgcd(5+k,20)=2, il faut et il suffit que 5+k soit divisible par 2 mais pas par 4 ni par 5 c'est à dire 5+k\=0 [5] (non congru) et 5+k=2 [4] soit encore k\=0 [5] et k=1 [4] qu'on peut (si on veut) "remonter" en k=1 ou 9 ou 13 ou 17 [20]))

moi j ai essayé autrement si possible de me corriger
Déterminer les couples (x,y) solutions de (E) tel que PGCD(x,y)=5
PGCD(x,y)=5 implique x congru à 0 mod 5 et y congru a 0 mod 5
je trouve après calcul k congru a 0mod 5 d ou k=5 p
x= 20 p = 5x 4p et y = 5-35p =5 x (1-7p)
réciproquement x= 20p et y =5-35p
il faut déterminer les conditions sur 4p et 1-7p pour qu ils soient premiers entre eux
d après Bezout 7 (4p)+4 (1-7p)=4 d ou pgcd ( 4p ,1-7p)= 4 ou 1
Pour P congru a 3 mod 4 pgcd ( 4p ,1-7p)= 4
Donc pour que le pgcd ( 4p ,1-7p)= 1 il faut prendre p=4q ou p=4q+1 ou p=4q+2

mon problème c est au niveau de la condition a imposer à p pour ne pas avoir un pgcd autres que 5



merci

[Ben314]

salut Ben314
svp expliquer moi plus claire cette ligne
Pour que pgcd(5+k,20)=2, il faut et il suffit que 5+k soit divisible par 2 mais pas par 4 ni par 5 c'est à dire 5+k\=0 [5] (non congru) et 5+k=2 [4] soit encore k\=0 [5] et k=1 [4] qu'on peut (si on veut) "remonter" en k=1 ou 9 ou 13 ou 17 [20]

C'est où que tu bloque ?

moi j ai essayé autrement si possible de me corriger
Déterminer les couples (x,y) solutions de (E) tel que PGCD(x,y)=5
PGCD(x,y)=5 implique x congru à 0 mod 5 et y congru a 0 mod 5
je trouve après calcul k congru a 0mod 5 d ou k=5 p
x= 20 p = 5x 4p et y = 5-35p =5 x (1-7p)
réciproquement x= 20p et y =5-35p
il faut déterminer les conditions sur 4p et 1-7p pour qu ils soient premiers entre eux
d après Bezout 7 (4p)+4 (1-7p)=4=2² d ou pgcd ( 4p ,1-7p)= 4 ou 1 ou 2
Pour P congru a 3 mod 4 pgcd ( 4p ,1-7p)= 4
Donc pour que le pgcd ( 4p ,1-7p)= 1 il faut prendre p=4q ou p=4q+1 ou p=4q+2
non : avec p=4q+1, ça te donne pgcd(4p,1-7p)=2
mon problème c est au niveau de la condition a imposer à p pour ne pas avoir un pgcd autres que 5

Pour avoir 5 et pas autres chose, tu ne coupera pas au fait d'écrire qu'il faut que "truc" soit non divisible par quelque chose, c'est à dire qu'il soit non congru à 0 modulo le quelque chose en question.
Dans certain cas, c'est simple, par exemple être non divisible par 2, donc non congru à 9 modulo 2, ben ça veut bêtement dire être congru à 1 modulo 2.
Après, toujours par exemple, être divisible par 2 mais pas par 4, ça veut dire être congru à 0 ou 2 modulo 4 ( divisible par 2) et pas à 0 modulo 4 ( pas divisible par 4) donc il reste comme seule possibilité d'être congru à 2 modulo 4.
Mais pour non divisible par 5 (ou par 17, c'est encore pire), ben, à part écrire "ne pas être congru à 0 modulo 5", y'a pas bien d'autres possibilités (écrire "être congru à 1 ou 2 ou 3 ou 4 modulo 5" est évidement possible, mais c'est bien long...)

[georgets555]

salut Ben314
merci pour les explications et si possible de me vérifier et corriger
le blocage c est au niveau de la réciproque dans chaque et exactement a partir de l application de Bézout ( la recherche des conditions sur p)

réciproquement x= 20p et y =5-35p
il faut déterminer les conditions sur 4p et 1-7p pour qu ils soient premiers entre eux
d après Bezout 7 (4p)+4 (1-7p)=4=2² d ou pgcd ( 4p ,1-7p)= 4 ou 1 ou 2
Pour P congru a 3 mod 4 p=4q+3 pgcd ( 4p ,1-7p)= 4
Donc pour que le pgcd ( 4p ,1-7p)= 1 il faut prendre p=4q ou p=4q+2
pour p=4q+1 pgcd(4p,1-7p)=2
d ou x= 20(4q+3) et y=-150 q-100

Déterminer les couples (x,y) solutions de (E) tel que PGCD(x,y)=2
PGCD(x,y)=2 implique x congru à 0 mod 2 et y congru a 0 mod 2
je trouve aprés calcul k congru a 1 mod 2 d ou k=2p+1
x= (8p+4) = 2 (4p+2) et y = (-14p-2)=2 x (-7p-1)
réciproquement x= 8p+4 et y =-14p-2

aussi voir PGCD(x,y)=10 implique x congru à 0 mod 10 et y congru a 0 mod 10
je trouve aprés calcul k congru a 0 mod 10 d ou k=10p ou bien k congru a 5 mod 10
x= 40p= 10 (4p) et y = (-70p+5) ou
x= 40p+20= 10 (4p+2) et y = (-70p-30)=10 x (-7p-1)
reciproquement x= 40p= 10 (4p) et y = (-70p+5) ou
x= 40p+20= 10 (4p+2) et y = (-70p-30)=10 x (-7p-1)
sont solutions de l équation la condition a imposer à p pour ne pas avoir un pgcd autres que 10


pour le cas pgcd (x,y)= 1 ??

merci

[Ben314]

d après Bezout 7 (4p)+4 (1-7p)=4=2² d ou pgcd ( 4p ,1-7p)= 4 ou 1 ou 2

A mon avis, le problème c'est qu'arrivé à se point là de la preuve, tu te fait c... pour des prunes à vouloir absolument rédiger la suite en terme de pgcd ou autre.
L'entier 4p, est forcément divisible par 4 donc la valeur du pgcd(4p,1-7p) ne dépend QUE de 1-7p avec 3 cas de figure :
-> Le pgcd vaut 1 ssi 1-7p est impair (donc non divisible par 2 et encore moins par 4)
-> Le pgcd vaut 4 ssi 1-7p est divisible par 4
-> Le pgcd vaut 2 ssi 1-7p est divisible par 2 mais pas par 4

Et là où tu te fait aussi c... pour des prunes, c'est que tu pouvait déjà dire la même chose concernant le pgcd(5k+2,20) :
C'est un diviseur de 20=2²x5 donc le pgcd vaut :
-> 1 si 5+k n'est divisible ni par 2 ni par 5
-> 2 si 5+k est divisible par 2 mais pas par 4 ni par 5
-> 4 si 5+k est divisible par 4 mais pas par 5
-> 5 si 5+k est divisible par 5 mais par 2
-> 10 si 5+k est divisible par 2 et 5 mais pas par 4
-> 20 si 5+k est divisible par 20

En résumé (et pour la deuxième fois), tu ne coupera pas à l'utilisation du fait que pgcd(a,4)=2 si et seulement si a est divisible par 2 et pas par 4.

Par exemple, dans ton calcul pour déterminer les cas où pgcd(x,y)=2, c'est forcément faux vu que tu ne dit rien concernant les congruences modulo 5 donc dans ce que tu propose comme solution, je suis sûr (sans même essayer) que tu va avoir des cas où le pgcd(x,y) ne vaut pas 2 mais 10 (i.e. x et y sont bien divisibles par 2, mais aussi par 5...)

Autre façon de voir les choses : même si la méthode ne te convient pas (ce que je peut parfaitement concevoir), la réponse que j'ai donné dans le post un peu au dessus, à savoir que :
pgcd(x,y)=2 ssi k est congru à 1 ou 9 ou 13 ou 17 modulo 20
est juste : si tu ne trouve pas la même chose, c'est faux...

Et concernant les cas où pgcd(x,y)=1, tu as la réponse juste au dessus : il faut (et il suffit) que 5+k ne soit divisible ni par 2, ni par 5 (ce que tu peut écrire sous forme d'une liste de congruences modulo 2x5=10)

[georgets555]

salut Ben314

merci beaucoup les explications et c est très gentille
merci pour les pernes aussi

j ai essayé autrement si possible de me vérifier cette méthode

PGCD(x,y)=2, il faut que
x=2u
y=2v
avec la condition que u et v sont premiers entre eux.

1er etape
Donc l équation devient 7u+4v=10 a pour solution U=;)10 + 4k ; V=20 7k
2em etape

Il faut déterminé les conditions su k pour que u et v soient premiers entre eux
Proposer moi votre méthode ( autres méthodes ) car la mienne est longue
J ai essayé ca mais je suis pas sur

7U+4V=10 donc pgcd(u,v)=1 ou 2ou 5 ou 10

Puis un tableau


Reste de k mod 10 0 1 2 3 4 5 6 7 8 9
U=
-10+4k 0 4 8 2 6 0 4 8 2 6
V=20-7k 0 3 6 9 2 5 8 1 4 7
Pgcd(u,v) 10 1 2 1 2 5 4 1 2 1

U et v sont premiers entre eux si k=10q+1 ou k=10q+3 ou k=10q+7 ou k=10q+9
On a 4 couples de solutions




pour quoi cette méthode ne me convient pas svp j aime bien comprendre

Autre façon de voir les choses : même si la méthode ne te convient pas (ce que je peut parfaitement concevoir), la réponse que j'ai donné dans le post un peu au dessus, à savoir que :
pgcd(x,y)=2 ssi k est congru à 1 ou 9 ou 13 ou 17 modulo 20
est juste : si tu ne trouve pas la même chose, c'est faux...

Et concernant les cas où pgcd(x,y)=1, tu as la réponse juste au dessus : il faut (et il suffit) que 5+k ne soit divisible ni par 2, ni par 5 (ce que tu peut écrire sous forme d'une liste de congruences modulo 2x5=10)[/quote] comment l écrire en modulo 10

merci

[Ben314]

Oui, ça ça marche parfaitement bien.
Il faudrait juste une petite explication sur le pourquoi il suffit d'étudier k modulo 10.

Mais (tu va dire que je suis jamais content et... tu aura raison), c'est un peu con de refaire les calculs pour résoudre 7u+4v=10 alors que tu avait fait (quasiment) la même chose en résolvant auparavant 7x+4y=20.
Et dans cette dernière équation, on a trouvé x=4k, y=-7k+5 et on a montré que pgcd(x,y)=pgcd(20,k+5)
Donc perso., j'essayerais de "rentabiliser" les calculs déjà fait en... les utilisant... plutôt que d'en refaire d'autres (qui sont quasiment les mêmes).
Donc je partirais dés le départ de la recherche des k tels que pgcd(20,5+k)=2 (ou 5)
Et comme il y a deux questions (avec 2 et avec 5) et que 2à n'est somme toute pas très grand, pour pas trop réfléchir, je ferais un tableau avec
Ligne 1 : k modulo 20 (de 0 à 19)
Ligne 2 : 5+k modulo 20 (de 0 à 19)
Ligne 3 : pgcd(20,k+5)
Et il n'y a plus qu'à lire le tableau pour répondre aux deux questions.

[georgets555]

merci beaucoup Ben314
j ai appris beaucoup de choses de vous et surtout votre patience et votre amour pour les maths
juste une question

pgcd(x,y)=2 ssi x congru a 0 mod 2 et y congru a 0 mod 2 et comment écrire la négation suivante avec les congruences et poursuivre le calcul x et y pas divisible par 4 ni par 5
j aime savoir comment appliquer si k = a mod p et k =b mod q alors k = ab mod pq

si possible de l applique sur notre exercice pour les cas ou on demande pgcd(x,y)=10 ou 4

merci

[Ben314]

pgcd(x,y)=2 ssi x congru a 0 mod 2 et y congru a 0 mod 2 et comment écrire la négation suivante avec les congruences et poursuivre le calcul x et y pas divisible par 4 ni par 5
j aime savoir comment appliquer si k = a mod p et k =b mod q alors k = ab mod pq
si possible de l applique sur notre exercice pour les cas ou on demande pgcd(x,y)=10 ou 4

Bon, déjà, l'équivalence en rouge, elle est fausse. Plus précisément, dans le sens 2 ne divise à la fois x et y[/U]

En fait, ça fait plein de fois que tu fait la même erreur (classique) consistant à dire que, pour montrer que pgcd(x,y)=d, il suffit de vérifier que d divise x et y alors que c'est effectivement nécessaire, mais pas suffisant (i.e. si d ne divise pas x ou bien ne divise pas y, on est certain que le pgcd n'est pas égal à d, mais si d divise x et y, on n'est pas certain que le pgcd =d, tout ce qu'on peut dire, c'est que le pgcd va être un multiple de d)

Ensuite, concernant la "négation", je suis pas bien sûr de comprendre la question.
Mettons qu'on parte de cette équivalence (vraie) :
pgcd(x,y)= ssi 2 divise x et y et aucun nombre >2 ne divise à la fois x et y
Alors elle dit aussi que
(pgcd(x,y) est différent de 2) ssi [(2 ne divise pas x) ou bien (2 ne divise pas y) ou bien (il existe un nombre >2 qui divise à la fois x et y)]
En fait, il y a des règles "mécaniques" qu'on entrevois ici pour écrire les négations des phrases mathématiques, mais elle ne sont pas vu au Lycée, donc il faut faire confiance à son "bon sens"...

Enfin, le truc en bleu, lui aussi est faux, par exemple si k=2 [3] et k=4 [5] on n'a pas k=2x4 [15]
C'est plus compliqué que ça. En fait, il y a une théorie derrière, mais a mon avis, il vaut mieux commencer par comprendre comment ça marche "dans la pratique", c'est à dire avec des valeurs simples.
Comme 3 et 5 divisent 15, on peut "remonter" des congruence modulo 3 ou 5 en congruences modulo 15, plus précisément, on a :
k=2 modulo 3 ssi k=2 ou 2+3(=5) ou 2+2x3(=8) ou 2+3x3(=11) ou 2+4x3(=14) modulo 15
k=4 modulo 5 ssi k=4 ou 4+5(=9) ou 4+2x5(=14) modulo 15
Et, en regardant les différent cas de figure, on en déduit que
(k=2 [3] et k=4 [5]) ssi (k=14 [15])
Bilan : le 14 obtenu au final n'est pas du tout 2x4. En fait, si on regarde bien, c'est le plus petit entier naturel que est à la fois congru à 2 [3] et aussi congru à 4 [5].
Si à la place de 3 et 5 on avait des nombres bien plus grand, on pourrait écrire un peu de "théorie" et voir que le 14 final peut s'obtenir à coup d'algorithme d'euclide...
Attention aussi au fait que, si on veut par exemple que k=?[6] et k=?[9] on a fortement intérêt à regarder ce qui se passe modulo 18=ppcm(6,9) plutôt que modulo 54=6x9.

Pour finir, concernant le "comment traduire que pgcd(x,y)=10" (par exemple), on a comme toujours :
pgcd(x,y)=10 ssi (10 divise x) et (10 divise y) et (aucun entier >10 ne divise à la fois x et y)
Évidement le truc super chiant à "traduire", c'est le 3em morceau "aucun entier >10 ne divise à la fois x et y", mais ici, on utilise le fait qu'on sait que le pgcd(x,y) divise 20 donc que les seuls entier succeptible de diviser à la fois x et y sont les diviseurs de 20, c'est à dire {1,2,4,5,10,20} donc on peut (grandement) simplifier le 3em morceau en écrivant à la place "20 ne divise pas à la fois x et y".

Idem pour 4. En général, on a
pgcd(x,y)=4 ssi (4 divise x) et (4 divise y) et (aucun entier >4 ne divise à la fois x et y)
et, vu le contexte, peut remplacer mécaniquement le 3em morceau par "ni 5, ni 10, ni 20 ne divisent à la fois x et y"
puis on réfléchi un peu en se disant que, si x et y était divisibles par 10 ou par 20 alors il seraient divisibles par 5, donc on peut remplacer le 3em morceau par "5 ne divise pas à la fois x et y"

[zygomatique]

une autre façon de traduire pgcd(x, y) = 10

x= 10u et y = 10v et pgcd(u, v) = 1

....

[Ben314]

une autre façon de traduire pgcd(x, y) = 10
x= 10u et y = 10v et pgcd(u, v) = 1
....

Certes, mais, dans le contexte de l'exercice, en écrivant ça tu tourne complètement en rond vu que pour déterminer si un pgcd est égal ou pas à un truc, ben tu dit qu'il faut déterminer si un autre pgcd est égal ou pas a 1.
C'est bien ce qu'elle a essayé d'utiliser au moins 3 fois dans ces différents posts et... ça ne même a rien (si ce n'est à reformuler le même problème de manière à peine différente)

[zygomatique]

j'ai bien vu ... bien sur ....

tout comme le fait qu'il insiste inutilement à vouloir travailler avec des congruences ... qui ne sont pas toujours nécessaires ...

[georgets555]

salut Ben 314
cher professeur votre méthode et la meilleur et économique
(( x=4k, y=-7k+5 et on a montré que pgcd(x,y)=pgcd(20,k+5)
Donc perso., j'essayerais de "rentabiliser" les calculs déjà fait en... les utilisant... plutôt que d'en refaire d'autres (qui sont quasiment les mêmes).
Donc je partirais dés le départ de la recherche des k tels que pgcd(20,5+k)=2 (ou 5)
Et comme il y a deux questions (avec 2 et avec 5) et que 2à n'est somme toute pas très grand, pour pas trop réfléchir, je ferais un tableau avec
Ligne 1 : k modulo 20 (de 0 à 19)
Ligne 2 : 5+k modulo 20 (de 0 à 19)
Ligne 3 : pgcd(20,k+5)
Et il n'y a plus qu'à lire le tableau pour répondre aux deux questions.))

mais est possible de m explique et de me rectifier comment répondre seulement en utilisant les congruences

pgcd(x,y)=4 si et seulement si x =0 mod 2 et y =0 mod 2 et (x non congru 0 mod 5 et y non congru 0 mod 5 ) et (x non congru 0 mod 10 et y non congru 0 mod 10 ) et(x non congru 0 mod 20 et y non congru 0 mod 20 )

le système se réduit a et seulement si x =0 mod 2 et y =0 mod 2 et (x non congru 0 mod 5 et y non congru 0 mod 5 )

comment transformer la négation (x non congru 0 mod 5 et y non congru 0 mod 5 )

comment terminer et résoudre le système et déterminer l entier k sans oublier 4 et 5 sont premiers entre eux

j aime savoir comment appliquer le résultat suivant dans notre exercice et si possible de l appliquer
pour les cas déjà étudier

si pgcd(a,b)=1 et k=0mod a et k =0 mod b alors k=0 mod ab

merci

[Pseuda]

Cela paraît difficile via les congruences car, comme dit Ben314, les congruences n'ont pas la notion de pgcd. Ou alors il faut introduire des notions de congru à et de non congru à ...

En résumé (sans utiliser les congruences) :

pgcd (20m, 5-35 m) = 5 * pgcd (4m, 1-7m) = 5 * pgcd (4m, 1+m) (car si d divise a et b, d divise a et a+b et réciproquement) = 5 * pgcd (m+1,4).

Donc pgcd (20m, 5-35m) = 5 ssi pgcd (m+1,4) = 1 ssi 2 ne divise pas m+1 (car 2 est le seul diviseur premier de 4) ssi m est pair.

Ensemble des solutions de la question 2) : (x,y) = (20m, 5-35m) avec m pair

[Ben314]

pgcd(x,y)=4 si et seulement si x =0 mod 2 et y =0 mod 2 et (x non congru 0 mod 5 et y non congru 0 mod 5 ) et (x non congru 0 mod 10 et y non congru 0 mod 10 ) et(x non congru 0 mod 20 et y non congru 0 mod 20 )

Bon, dés le départ, ça déconne (doublement) :
pour que le pgcd(x,y)=4, il faut que x et y soit divisible non seulement par 2, mais (surtout) par 4 donc il faut que :
(1) x=0 mod 4 et y=0 mod 4
et ensuite, ça déconne aussi vu que, pour que le pgcd ne soit pas plus grand que 4, il faut (par exemple) que l'on ait pas [x=0 mod 5 et y=0 mod 5]. Sauf que la négation de cette phrase, c'est :
(2) x non congru à 0 modulo 5 ou bien y non congru à 0 modulo 5
Avec en plus le "ou bien" à prendre au sens mathématique du terme, c'est à dire ou l'un, ou l'autre, ou les deux.
Pour te donner un exemple "basique", le type qui dit "ma voiture est rouge et puissante", c'est un menteur si sa voiture n'est pas rouge ou bien n'est pas puissante.
De même, pour parler plus de math., dire que M(x,y) est l'origine du repère, ça veut dire que x=0 et y=0. Pour que M soit différent de l'origine, il faut que [x0 ou bien y0]. Par exemple (1,0) est différent de l'origine car y0 (donc on a bien [x0 ou bien y0] alors qu'on a pas [x0 et y0])

Bilan : au départ, ce qu'on a, c'est :
pgcd(x,y)=4 si et seulement si x =0 mod 4 et y =0 mod 4 et (x non congru 0 mod 5 ou bien y non congru 0 mod 5 ) et (x non congru 0 mod 10 ou bien y non congru 0 mod 10 ) et (x non congru 0 mod 20 ou bien y non congru 0 mod 20 )
qui se "réduit" après reflexion à :
pgcd(x,y)=4 si et seulement si x =0 mod 4 et y =0 mod 4 et (x non congru 0 mod 5 ou bien y non congru 0 mod 5 )

Ensuite, arrivé à ce point, y'a pas grand chose à dire de plus, principalement à cause du "ou bien" dans la phrase qui fait qu'il y a plusieurs cas à traiter.
Mais, normalement, tu n'est pas sensé écrire ça avec les deux variables x et y (donc avec le "ou bien" qui fout la m...), vu que tu as déjà résolu le système précédemment et que tu sait exprimer x et y à l'aide d'une seule variable k (où m comme le fait PSEUDA çi dessus, mais il ne manipule qu'une variable et pas 2)