Pgcd et congruence

[georgets555]

salut Ben314 svp donner une explication plus détailler

merci pour les explications
mais svp explique moi de plus prés ( 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 )

et donne moi les calculs a faire résolution du System

et les etapes a suivre 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 )

donc je reformule on resoud le systeme suivant
x =0 mod 4 et y =0 mod 4 et x non congru 0 mod 5 ou bien
x =0 mod 4 et y =0 mod 4 et y non congru 0 mod 5

dons x =0 mod 4 et y =0 mod 4 on détermine k puis on cher les valeurs de k tel que y non congru 0 mod 5

et pour les autres cas


merci

[georgets555]

salut Ben 314
svp
expliquer moi
pourquoi les congruences n'ont pas la notion de pgcd

merci

[Ben314]

salut Ben 314
expliquer moi
pourquoi les congruences n'ont pas la notion de pgcd

Simplement parce que, dans PGCD, il n'y a pas que le "CD" (commun diviseur), mais aussi "PG" (plus grand) et que de traduire qu'il n'y a pas d'autres diviseurs plus grands que celui là (4 ou 5 ou autre chose), ben c'est pas facile avec des congruences...

[georgets555]

salut Ben 314
salut Ben314 svp donner une explication plus détailler

merci pour les explications
mais svp explique moi de plus prés ( 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 )

et donne moi les calculs a faire résolution du System

et les etapes a suivre 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 )

donc je reformule on resoud le systeme suivant
x =0 mod 4 et y =0 mod 4 et x non congru 0 mod 5 ou bien
x =0 mod 4 et y =0 mod 4 et y non congru 0 mod 5

dons x =0 mod 4 et y =0 mod 4 on détermine k puis on cher les valeurs de k tel que y non congru 0 mod 5

et pour les autres cas


merci

[georgets555]

salut
zygomatique
svp
donner moi votre méthode pour résoudre cette exercice
merci

[georgets555]

salut PSEUDA
comment traiter les autres cas
pgcd(x,y)=2 , ou 4 ou 10 ou 20 ou 1

merci

[Pseuda]

En utilisant les congruences (puisque c'est l'objet de l'exercice) :

Si x et y vérifient (E), alors pgcd (x,y) divise 20, donc pgcd (x,y) = 5 ssi x et y sont congrus à 0 mod 5, et x ou y non congrus à 0 mod 2, ssi (x,y) = (20m, 5-35m) et x ou y impairs.

Comme 20m ne peut pas être impair, donc il faut que y le soit, c'est-à-dire que m soit pair.

Finalement ce n'était pas si compliqué avec les congruences. :lol3:

[Pseuda]

salut PSEUDA
comment traiter les autres cas
pgcd(x,y)=2 , ou 4 ou 10 ou 20 ou 1

merci

Pour pgcd (x,y) = 2, cela paraît plus compliqué. Il faut réunir les 3 conditions :
. x et y congrus à 0 mod 2
. x ou y non congrus à 0 mod 4
. x ou y non congrus à 0 mod 5

Comme (x,y) = (4k, 5-7k), x est donc congru à 0 mod 4, y doit donc être congru à 0 mod 2 et non congru à 0 mod 4, c'est-à-dire congru à 2 mod 4.

5-7k congru à 2 mod 4 ssi k congru à 1 mod 4 (en rajoutant 8k congru à 0).

x ou y non congrus à 0 mod 5 ssi k non congru à 0 mod 5 (car 4 et 7 sont premiers avec 5).

Finalement pgcd (x,y) = 2 ssi (x,y) = (4k, 5-7k) avec k congru à 1 mod 4 et non congru à 0 mod 5, c'est-à-dire k=4m+1, avec m différent de 5p+1 (car 4m+1 est congru à 0 mod 5 ssi m est congru à 1 mod 5).

Si je ne me suis pas trompée en route. Tout cela paraît compliqué pour un exercice de Terminale.

[Ben314]

- 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.

ça vous permettra d'utiliser la méthode que vous voulez avec la valeur que vous voulez comme pgcd et de vérifier... que c'est juste...

[georgets555]

salut Ben 314
merci pour votre patience et coopération et c est très gentille

seulement j aime savoir l utilité e des deux lignes pgcd(k+5,4) et pgcd(k+5,4) et comment les utiliser
pourquoi ne pas ajouter pas une ligne pour pgcd(k+5,2) et pgcd(k+5,10) en fonction de quoi ajouter des lignes 20 =4x5 et 5 et 4 premiers entre eux

dans moi un autre exemple d application dans un autre cas 24 diviseurs de 24 {1,2,3,6,12,24} ou autres

merci bien

[georgets555]

salut PSEUDA
merci pour vous explications
k congru à 1 mod 4 et non congru à 0 mod 5, c'est-à-dire k=4m+1, avec m différent de 5p+1 (car 4m+1 est congru à 0 mod 5 ssi m est congru à 1 mod 5).

donc qu elle est la forme générale de k

est ce que k prend pour m=5p k=20p+1 p
pour m=5p+2 k=20p+9
pour m=5p+3 k=20p+13
pour m=5p+4 k=20p+17

donc 4 couple de solutions

comment écrire les systèmes pour les autres cas

Pour pgcd (x,y) = 5, cela paraît plus compliqué. Il faut réunir les 3 conditions :
. x et y congrus à 0 mod 5
. x ou y non congrus à 0 mod 4
. x ou y non congrus à 0 mod 2

Pour pgcd (x,y) = 10, cela paraît plus compliqué. Il faut réunir les 3 conditions :
. x et y congrus à 0 mod 10
.
. x ou y non congrus à 0 mod 2

Pour pgcd (x,y) = 4, cela paraît plus compliqué. Il faut réunir les 3 conditions :
. x et y congrus à 0 mod 4
. x ou y non congrus à 0 mod 5
. x ou y non congrus à 0 mod 2


Pour pgcd (x,y) = 1, cela paraît plus compliqué. Il faut réunir les 3 conditions :

. x ou y non congrus à 0 mod 4
. x ou y non congrus à 0 mod 5



merci

[Ben314]

dans moi un autre exemple d application dans un autre cas 24 diviseurs de 24 {1,2,3,6,12,24} ou autres

Comme les diviseurs de 24 sont de la forme avec a=0, 1 ou 2 et b=0 ou 1.
Pour un entier x quelconque, le pgcd(x,24) sera donc de cette forme et, pour le connaitre, il suffit d'avoir pgcd(x,8) et pgcd(x,3).

[georgets555]

salut Ben314

merci pour les explications mais j aime comprendre qu il suffit d'avoir pgcd(x,8) et pgcd(x,3) est ce qu on va faire le produit utiliée et
comment généraliser votre méthode

a= d^c x e^h x k^q pgcd(x,a) et pour le connaitre il suffit d avoir pgcd(x,?)


l appliquer sur un autre exemple a=2^3 x 3^2 x 5^4 x7^5 et x entier qq

merci

[Pseuda]

ça vous permettra d'utiliser la méthode que vous voulez avec la valeur que vous voulez comme pgcd et de vérifier... que c'est juste...

Ouah, bien sûr ! C'est le plus simple. Là où j'ai eu plus de mal, c'est pour montrer rigoureusement que pgcd (a,5) * pgcd (a,4) = pgcd (a,20).

On peut maintenant résoudre l'exercice pour tous les cas :

par exemple : pgcd (x,y) = 2 ssi (x,y)= (4k, 5-7k) avec k congru à 1,9,13 ou 17 mod 20. Cela revient à dire avec k congru à 1 mod 4 et non congru à 0 mod 5.

Pour georgets555, c'est-à-dire tous les couples de la forme (x,y) = (4*(20m+1), 5-7*(20m+1)) = (80m+4,-140m-2), ou (4*(20m+9), 5-7*(20m+9)) = (80m+36,-140m-58), ...

[Pseuda]

salut PSEUDA
merci pour vous explications
k congru à 1 mod 4 et non congru à 0 mod 5, c'est-à-dire k=4m+1, avec m différent de 5p+1 (car 4m+1 est congru à 0 mod 5 ssi m est congru à 1 mod 5).

donc qu elle est la forme générale de k

est ce que k prend pour m=5p k=20p+1
pour m=5p+2 k=20p+9
pour m=5p+3 k=20p+13
pour m=5p+4 k=20p+17

donc 4 couple de solutions


merci

Oui, c'est cela. Cela revient au même qu'en utilisant la solution de Ben314, c'est une façon différente de l'exprimer.

[georgets555]

salut PSEUDA

comment tu passe du modulo 20 a un autre dans cette exemple ( théorème utiliser )

svp comment tu as déduit du tableau (k congru à 1,9,13 ou 17 mod 20. Cela revient à dire avec k congru à 1 mod 4 et non congru à 0 mod 5.) comment passer des mod 20 a partir du tableau vers les autres mod

pgcd (x,y) =4 ssi (x,y)= (4k, 5-7k) avec k congru à? mod 20. Cela revient à dire avec k congru à ? mod ? et non congru à ? mod ?.


pgcd (x,y) =5ssi (x,y)= (4k, 5-7k) avec k congru à? mod 20. Cela revient à dire avec k congru à ? mod ? et non congru à ? mod ?.

pgcd (x,y) =10 ssi (x,y)= (4k, 5-7k) avec k congru à? mod 20. Cela revient à dire avec k congru à ? mod ? et non congru à ? mod ?.

pgcd (x,y) =20 ssi (x,y)= (4k, 5-7k) avec k congru à? mod 20. Cela revient à dire avec k congru à ? mod ? et non congru à ? mod ?.


pgcd (x,y) =1 ssi (x,y)= (4k, 5-7k) avec k congru à? mod 20. Cela revient à dire avec k congru à ? mod ? et non congru à ? mod ?.


merci

[Pseuda]

salut PSEUDA

comment tu passe du modulo 20 a un autre dans cette exemple ( théorème utiliser )

svp comment tu as déduit du tableau (k congru à 1,9,13 ou 17 mod 20. Cela revient à dire avec k congru à 1 mod 4 et non congru à 0 mod 5.) comment passer des mod 20 a partir du tableau vers les autres mod

pgcd (x,y) =4 ssi (x,y)= (4k, 5-7k) avec k congru à? mod 20. Cela revient à dire avec k congru à ? mod ? et non congru à ? mod ?.


pgcd (x,y) =5ssi (x,y)= (4k, 5-7k) avec k congru à? mod 20. Cela revient à dire avec k congru à ? mod ? et non congru à ? mod ?.

pgcd (x,y) =10 ssi (x,y)= (4k, 5-7k) avec k congru à? mod 20. Cela revient à dire avec k congru à ? mod ? et non congru à ? mod ?.

pgcd (x,y) =20 ssi (x,y)= (4k, 5-7k) avec k congru à? mod 20. Cela revient à dire avec k congru à ? mod ? et non congru à ? mod ?.


pgcd (x,y) =1 ssi (x,y)= (4k, 5-7k) avec k congru à? mod 20. Cela revient à dire avec k congru à ? mod ? et non congru à ? mod ?.


merci

Le mieux est de repartir de : pgcd (x,y) = pgcd (4k,5-7k) = pgcd (k+5,20), pour n'avoir plus qu'un seul nombre à étudier.

On a (en mode direct, sans utiliser le tableau) : pgcd (k+5,20)=2 ssi k+5 est divisible par 2 mais pas par 4 ni par 5, ssi k+5 congru à 2 mod 4 et non congru à 0 mod 5, ssi k congru à 1 mod 4 (en soustrayant 5) et k non congru à 0 mod 5.

On se ramène à un modulo 20 pour avoir un dénominateur commun : k congru à 1 mod 4 ssi k congru à 1,5,9,13 ou 17 mod 20; k non congru à 0 mod 5 ssi k congru à 1,2,3 ou 4 mod 5, ssi k congru à 1,2,3,4,6,7,8,9,11,12,13,14,16,17,18 ou 19 mod 20 .

Au final, pgcd (k+5,20)=2 ssi k congru à 1,9,13 ou 17 mod 20, soit (x,y) = (4k,5-7k) avec k = 20m+1,+9, +13 ou +17.

C'était pour répondre à ta question. Mais en fait on a beaucoup plus rapide (dès que l'on s'est ramené à (k+5,20)) :

pgcd(k+5,20) = 2 ssi k+5 congru à 2,6,14, ou 18 mod 20, c'est-à-dire k congru à 17, 1, 9 ou 13 mod 20.

[chan79]

salut
petite vérif avec un tableur
On pourrait aussi conjecturer puis vérifier les résultats mais c'est beaucoup moins bien que ce qui a été fait ci-dessus (et on n'a pas forcément un tableur sous la main)

[georgets555]

salut PSEUDA

j aime bien savoir comment faire sans passer par le tableau et sans partir comme vous par pgcd(k+5,20)

remplacer ?

svp comment tu as déduit du tableau (k congru à 1,9,13 ou 17 mod 20. Cela revient à dire avec k congru à 1 mod 4 et non congru à 0 mod 5.) comment passer des mod 20 a partir du tableau vers les autres mod

pgcd (x,y) =4 ssi (x,y)= (4k, 5-7k) avec k congru à? mod 20. Cela revient à dire avec k congru à ? mod ? et non congru à ? mod ?.


pgcd (x,y) =5ssi (x,y)= (4k, 5-7k) avec k congru à? mod 20. Cela revient à dire avec k congru à ? mod ? et non congru à ? mod ?.

pgcd (x,y) =10 ssi (x,y)= (4k, 5-7k) avec k congru à? mod 20. Cela revient à dire avec k congru à ? mod ? et non congru à ? mod ?.

pgcd (x,y) =20 ssi (x,y)= (4k, 5-7k) avec k congru à? mod 20. Cela revient à dire avec k congru à ? mod ? et non congru à ? mod ?.


pgcd (x,y) =1 ssi (x,y)= (4k, 5-7k) avec k congru à? mod 20. Cela revient à dire avec k congru à ? mod ? et non congru à ? mod ?.


merci

[georgets555]

salut Ben314
svp donner moi un autre exemple d application de votre méthode un peu compliquer avec plusieurs diviseurs


merci pour les explications mais j aime comprendre qu il suffit d'avoir pgcd(x,8) et pgcd(x,3) est ce qu on va faire le produit et
comment généraliser votre méthode

a= d^c x e^h x k^q pgcd(x,a) et pour le connaitre il suffit d avoir pgcd(x,?)


l appliquer sur un autre exemple a=2^3 x 3^2 x 5^4 x7^5 et x entier qq

merci