Pgcd et congruence

[zygomatique]

2 et 3 étant premiers

si p divise x et 8 il ne divise pas 3
si q divise x et 3 il ne divise pas 8

le théorème de Gauss te dit alors que pq divise x et 24

il en est de même pour le pgcd ...



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

les diviseurs de x et y sont les diviseurs de 20


4 = pgcd(x, y) <=> 4 divise x et y et 5 ne divise pas x et y

or 4 divise x = 4k

donc il faut que 4 divise 5 - 7k


4 divise 5 - 7k <=> il existe p tel que 4p = 5 - 7k <=> 4p + 7k = 5 (1)

or 4 et 7 sont premiers entre eux donc d'après le théorème de Bézout il existe u et v tels que 4u + 7v = 1

exemple 4 * 2 + 7(-1) = 1 donc 4 * 10 + 7(-5) = 5 qu'on soustrait de (1)

4(p - 10) = -7(k + 5)

théorème de Gauss ==> k = -5 + 4p

donc y = 5 - 7k = 5 - 7(-5 + 4p) = 40 - 28p

et x = 4(-5 + 4p) = 16p - 20


il faut ensuite vérifier qu'ils ne sont pas simultanément multiple de 5 ...

or 2x + y = 4p donc p ne doit pas être multiple de 5

on trouve donc quatre solutions comme le montre Ben34 dans son tableau de congruence modulo 20

....

[Ben314]

Je sais pas si ça se voit au Lycée, mais d'un autre coté, tout est quand même on ne peu plus évident :

Si on a les décompositions en facteurs premier de et de alors

1) Si on fait le produit , on ajoute les exposants.

2) Donc pour que n divise m, c'est à dire que il faut et il suffit qu'on puisse obtenir les exposants de m en ajoutant des entiers positifs à ceux de n, c'est à dire en fait que les exposants de n soit inférieurs où égaux à ceux de m.

3) Donc pour qu'un nombre divise à la fois n et m, il faut que ces exposants soient inférieurs ou égaux à ceux de n et aussi à ceux de m.
Donc, si on veut que d soit le plus grand possible (donc que ce soit le pgcd(n,m)) il faut prendre comme exposants (de 3 par exemple) le plus grand entier possible inférieur aux exposants de 3 dans n et dans m et c'est clairement le plus petit des deux exposants (le plus grand entier inférieur ou égal à 7 et inférieur ou égal à 9 est évidement 7).

Par exemple :

Écrit de façon théorique, on a donc où désigne le plus petit des deux entiers a et b.

4) Tu en déduit en particulier que vu que ; ; ...

Et si on veut aller "à peine plus loin", on peut montrer que, si a et b sont premiers entre eux alors pgcd(n,ab)=pgcd(n,a)xpgcd(n,b) (c'est exactement la même preuve)

[Pseuda]

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

C'est bien de vouloir comprendre, c'est ce qu'il faut faire pour progresser. Si tu veux revenir à la forme (4k,5-7k), c'est plus compliqué. On a trouvé une solution simple, tu en veux donc une autre plus compliquée ?

Tu sais que le pgcd(x,y) divise 20. On a ainsi : pgcd (x,y) = pgcd (4k,5-7k) = 4 ssi x et y sont divisibles par 4 et pas par 5, donc s'ils sont congrus à 0 mod 4 et pas à 0 mod 5.
Pour tout k, 4k est congru à 0 mod 4 ; 5-7k est congru à 0 mod 4 ssi k+1 est congru à 0 mod 4 (on enlève 4 et on rajoute 8k) ssi k est congru à 3 mod 4.

Je te laisse continuer pour x et y non congrus à 0 mod 5 selon le même principe. Tu dois trouver k non congru à 0 mod 5.

Il faut ensuite réunir ces 2 résultats. Mais il faut revenir à une congruence mod 20 (comme j'ai fait plus haut). Tu vas trouver k congru à 3, 7, 11 ou 19 mod 20, comme dans le tableau de Ben.

De manière générale, si a est congru à b mod 20, il est aussi congru à b mod 4 (pourquoi ?). L'inverse n'est pas vrai.

[georgets555]

salut Ben 314
merci pour les explications
surtout des nouvelles formules qui apparaissent sous autres formes
comment faire les démonstrations des cas suivants
1) montrer que, si a et b sont premiers entre eux alors pgcd(n,ab)=pgcd(n,a)xpgcd(n,b)

2)est ce qu on peux montrer le résultat pour a1,a2, ,,,,ap premiers entres eux
pgcd(n,a1...ap)=pgcd(n,a1)x...........xpgcd(n,ap)

au niveaux des congruences comment passer de k est congru à 3 mod 4 et k non congru à 0 mod 5
au mod 20 ( mod4 et mod 5) et inversement

merci

[georgets555]

salut zygomatique
merci pour les explications
svp
j aime bien comprendre votre façon
si possible de l appliquer pour le cas PGCD(x,y)=2 et de me détailler les étapes a faire pour les autres cas PGCD(x,y)=5 ou 10 ou bien 20

merci

[georgets555]

salut PSEUDA
svp donner une reponse pour les autres cas avec cette démarche


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

[Ben314]

1) montrer que, si a et b sont premiers entre eux alors pgcd(n,ab)=pgcd(n,a)xpgcd(n,b)
2)est ce qu on peux montrer le résultat pour a1,a2, ,,,,ap premiers entres eux
pgcd(n,a1...ap)=pgcd(n,a1)x...........xpgcd(n,ap)

au niveaux des congruences comment passer de k est congru à 3 mod 4 et k non congru à 0 mod 5
au mod 20 ( mod4 et mod 5) et inversement

Question 1) => cherche : écrit de même que a=produit_de_premiers_avec_certains_exposant, idem pour b et n puis regarde ce que ça veut dire que a et b sont premier entre eux au niveau des exposants et tu conclue par une simple vérif vu que tu as la formules qui te donne direct le pgcd de deux nombre décomposés en produit de premiers.

Question 2) => Totalement évident par récurrence a1a2...an ,n'est jamais que le produit de a1a2...a(n-1) par an et on sait que ça marche pour le produit de deux termes.

Question 3) Perso, ça me semble "totalement trivial", c'est à dire que j'aurais tendance à ne strictement rien écrire pour passer par exemple de k=3 [4] à k=3 ou 7 ou 11 ou 15 ou 19 [20].
Si tu veut VRAIMENT écrire quelque chose, tu peut écrire que k=3 [4], ça veut dire que k=3+4p et qu'ensuite, tu regarde les différentes valeur possible pour p modulo 5 :
si p=0 [5] alors p=5j et k=3+4(5j)=3+20p = 3 [20]
si p=1 [5] alors p=1+5j et k=3+4(1+5p)=7+20p = 7 [20]
si p=2 [5] alors p=2+5j et k=3+4(2+5p)=11+20p = 11 [20]
si p=3 [5] alors p=3+5j et k=3+4(3+5p)=15+20p = 15 [20]
si p=4 [5] alors p=4+5j et k=3+4(4+5p)=19+20p = 19 [20]
Et si tu veut en même temps que k ne soit pas congru à 0 modulo 5, c'est à dire k non congru ni à 0, ni à 5, ni à 10, ni à 15 modulo 20, ben ça veut juste dire qu'il faut enlever le 15 de la liste {3,7,11,15,19} précédemment établie.

[georgets555]

svp Ben314
donner moi la formule finale et un exemple pour comprendre l idée
((a et b sont premier entre eux au niveau des exposants)) et tu conclue par une simple vérif vu que tu as la formules qui te donne direct le pgcd de deux nombre décomposés en produit de premiers.)

merci

[Ben314]

Si j'ai bien compris, la "formule finale" (celle que tu va démontrer), c'est que

...si a et b sont premiers entre eux alors pgcd(n,ab) = pgcd(n,a) x pgcd(n,b)

[georgets555]

salut Ben314

oui c est cette formule pgcd(n,a b)=pgcd(n,a)xpgcd(n,b)
aussi sous forme plus générale pgcd(n,produit ai) avec ai premier entre eux ( a indice i)

soit par récurrence ou d une façon théorique et une application sur un exemple
Écrit de façon théorique, on a donc \text{pgcd}(n,m)=2^{\min(a_2,b_2)}\times3^{\min(a_ 3,b_3)}\times5^{\min(a_5,b_5)}\times\cdots où 4$\min(a,b) désigne le plus petit des deux entiers a et b.

4) Tu en déduit en particulier que \text{pgcd}(n,m)=\text{pgcd}(n,2^{b_2}) \times \text{pgcd}(n,3^{b_3}) \times \text{pgcd} (n,5^{b_5})\times\cdots vu que \text{pgcd}(n,2^{b_2})=2^{\min(a_2,b_2)} ; \text{pgcd}(n,3^{b_3})=3^{\min(a_3,b_3)} ; \text{pgcd}(n,5^{b_5})=5^{\min(a_5,b_5)}

merci

[Pseuda]

salut PSEUDA
svp donner une reponse pour les autres cas avec cette démarche


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

Bonjour georgets555,

Je vais te donner les clés pour faire cela toi-même :

1) supposons n et m tels que m divise n : n = m*d, alors k congru à b mod m ssi k congru à b+m*r mod n avec r = 0,1,2... ou d-1, soit d possibilités (car si k-b = m*p et p=d*q+r, division euclidienne de p par d, alors k-b = m*(d*q+r) = n*q + m*r) ; par exemple, k congru à 3 mod 4 ssi k congru à 3,7,11,15 ou 19 mod 20

2) tu peux être amené à résoudre l'équation en k : a*k congru à b mod m (par exemple : 7*k congru à 5 mod 10) :
- si a est premier avec m, il n'y a qu'une solution mod m : il faut essayer tous les k de 0 à m-1, (par exemple, l'unique solution de 7*k congru à 4 mod 10 est k = 2 mod 10)
- sinon, tu peux te ramener à une équation équivalente en divisant (si c'est possible) les 2 membres de l'équation et le modulo par le pgcd de (a,m), (par exemple 4 * k congru à 2 mod 10 ssi 2 * k congru à 1 mod 5)

3) tu peux faire un tableau avec les pgcd cherchés en lignes, et en colonne, pour chaque pgcd cherché, les congruences possibles et non possibles de k modulo les diviseurs de 20 : 2,4,5,10, puis leur équivalence mod 20.

A toi de jouer !

[georgets555]

salut PSEUDA
merci pour les détails

je vais les appliquer puis si possible de le vérifier
merci beaucoup

[georgets555]

salut Ben314
si possible de me donner une démonstration et un exemple numérique

oui c est cette formule pgcd(n,a b)=pgcd(n,a)xpgcd(n,b)
aussi sous forme plus générale pgcd(n,produit ai) avec ai premier entre eux ( a indice i)

soit par récurrence ou d une façon théorique et une application sur un exemple
Écrit de façon théorique, on a donc \text{pgcd}(n,m)=2^{\min(a_2,b_2)}\times3^{\min(a_ 3,b_3)}\times5^{\min(a_5,b_5)}\times\cdots où 4$\min(a,b) désigne le plus petit des deux entiers a et b.

4) Tu en déduit en particulier que \text{pgcd}(n,m)=\text{pgcd}(n,2^{b_2}) \times \text{pgcd}(n,3^{b_3}) \times \text{pgcd} (n,5^{b_5})\times\cdots vu que \text{pgcd}(n,2^{b_2})=2^{\min(a_2,b_2)} ; \text{pgcd}(n,3^{b_3})=3^{\min(a_3,b_3)} ; \text{pgcd}(n,5^{b_5})=5^{\min(a_5,b_5)}

merci

[georgets555]

salut PSEUDA
je n arrive pas a appliquer les clés de votre méthode
svp donner une solution pour la comprendre


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 zygomatique
si possible de m étudier le cas pgcd(x,y)= 2 avec votre méthode qui utilise th de BÉZOUT

merci

[georgets555]

salut zygomatique
si possible de m étudier le cas pgcd(x,y)= 2 avec votre méthode qui utilise th de BÉZOUT

merci

[georgets555]

salut PSEUDA
svp expliquer moi le passage suivant et est ce que la réciproque est vrai

k congru à 1,9,13 ou 17 mod 20. Cela revient à dire avec k congru à 1 mod 4 et non congru à 0 mod 5

merci

[chan79]

oui c est cette formule pgcd(n,a b)=pgcd(n,a)xpgcd(n,b)

juste une remarque
on a la formule (sorte de "distributivité")
PGCD(n,PPCM(a,b))=PPCM(PGCD(n,a),PGCD(n,b))
voir ce que ça donne si a et b sont premiers entre eux
on a une autre formule en permutant PPCM et PGCD

[georgets555]

salut
j ai essayé de répondre autrement sans passer par un tableau
si possible de me vérifier ce travail et de me faire des remarques

Pgcd(x,y) après transformation devient

Pgcd(k+5,20)

Etude d un cas

Pour le cas pgcd(x,y)=2

Pgcd(k+5,5)=2 si et seulement si il existe a et b deux entiers premiers entres eux pgcd(a,b)=1

K+5=2 *a
et
20= 2 *b

K+5=2 *a d ou k=2*a-5 d ou k= 20q+2r-5 avec 0 <=2r-5<20 d ou
et
b=10
1) chercher un encadrement pour le reste r
D ou 2,5<=r<12,5


r=3 ou r=4 ou r=5 ou r=6ou r=7 ou r=8ou r=9 ou r=10ou r=11 ou r=12


2) on cherche les entiers compris entre 0 et 10 et qui sont premier avec 10
3) en détermine par suite les valeurs possible de k en suite x et y

pgcd(a,10)=1 si et seulement si pgcd(r,10)=1 d ou a= 10q+r 0<=r<10
r=1 a=10q+1 d ou k=10q-3
r=3 pgcd(r,10)=1 d ou a=10q+3 d ou k=10q+1
r=7 a=10q+7 d ou k=10q+9
r=9 a=10q+9 d ou k=10q +13

On obtient 4 couples