Comme utiliser le théorème de Bézout

[olivier 2020]

salut

si possible de me donner une réponse
a=5k et b=6-3k
1)déterminer l entier(s) k pour que le pgcd(a,b)=1
2) peut on utiliser le théorème de Bézout pour déterminer deux entiers u ,v
au+bv=1

merci

[mathelot]

salut

si possible de me donner une réponse
a=5k et b=6-3k
1)déterminer l entier(s) k pour que le pgcd(a,b)=1
2) peut on utiliser le théorème de Bézout pour déterminer deux entiers u ,v
au+bv=1

merci

si d|a et d|b alors d|(3a+5b) donc d|30

[olivier 2020]

salut mathelot
mais comment déterminer l entier k pour que le pgcd(a,b)=1
merci

[nodjim]

a=5k et b=3(2-k)
les diviseurs communs évidents sont, pour k, les multiples de 2,3.
Dans les autres cas, il n'y a pas de diviseurs communs. Car les diviseurs de k sont aussi ceux de a (a=5k) et jamais ceux de b (à cause du 2-k).
pgcd (a,b)=1 pour tout k non multiple de 2 ou 3, qu'on exprime aussi par 6k+-1.

[olivier 2020]

salut nodjim

je n est pas bien compris votre explication

comment choisir k ou les valeurs de k qui me donne a et b premiers entres eux
comment utiliser le théorème de Bézout

merci

[zygomatique]

salut

a = 5k et b = 3(2 - k)

et on cherche k tel que pgcd(a, b) = 1

d divise a et b => d divise 30 = 1 * 2 * 3 * 5


k et 2 - k ont même parité donc si k est pair alors 2 divise a et b

donc k est impair ... posons k = 2p + 1 .............(on élimine le facteur 2)

alors a = 5(2p + 1) = 10p + 5 et b = 3(1 - 2p) = 3 - 6p

or a = 3(3p + 1) + p + 1

3 divise a et b 3 divise p + 1

donc 3 ne divise pas a et b

si p = -2 + 3q alors k = 6q - 3 et a = 15(2q - 1) donc 3 divise a et b donc ça ne convient pas

si p = 3q alors k = 6q + 1 et a = 5(6q + 1) et b = 3(1 - 6q).......... (on élimine le facteur 3)

.... à toi d'éliminer le facteur 5 pour que d = 1 ....

[olivier 2020]

salut zygomatique]



on part de a = 5(6q + 1) et b = 3(1 - 6q)

5 divise a et b a =0 mod5 et b=0mod5 d
q=0mod 5 et q=1mod 5
on obtient de valeurs de q
je ne sait pas si c est juste
svp comment poursuivre
merci

[olivier 2020]

[quote="zygomatique"] salut si possible de me donner plus d explications et de me donner le résultat finale

on cherche k tel que pgcd(a, b) = 1

d divise a et b => d divise 30 = 1 * 2 * 3 * 5


si possible de m expliquer votre méthode
est ce que a chaque fois pour déterminer pgcd( a,b) =1 il faut éliminer les autre multiples
si par exemple j ai d divise a et b => d divise 60 = 1 * 2^2 * 3 * 5
dans le cas générale
d divise a et b => d divise N = 1 * p1^n2 *p2^n2 * p3^n3....*pi^ni avec p1,p2....pi nombres premiers distincts
comment je dois procéder

merci beaucoup

[zygomatique]

oui on essaie d'éliminer les éventuels diviseurs ...

[olivier 2020]

Salut zygomatique
pour éliminer le diviseur 5 ( je n est réussi a terminer svp donner la suite comment faire )
on part de a = 5(6q + 1) et b = 3(1 - 6q)

5 divise a et b a =0 mod5 et b=0mod5 d
q=0mod 5 et q=1mod 5
on obtient de valeurs de q
je ne sait pas si c est juste
svp comment poursuivre
merci

[zygomatique]

voir ici :: http://www.maths-forum.com/pgcd-congruence-165505.php

...

[olivier 2020]

salut zygomatique
merci pour le lien
mais si possible de m expliquer comment en va éliminer le diviseur 5
car je n arrive pas a le faire
j aime bien comprendre votre méthode

on part de a = 5(6q + 1) et b = 3(1 - 6q)

5 divise a et b a =0 mod5 et b=0mod5 d
q=0mod 5 et q=1mod 5
on obtient de valeurs de q
je ne sait pas si c est juste
svp comment poursuivre
merci

[olivier 2020]

Salut zygomatique
comment éliminer le diviseur 5 ?
on a
a = 5(6q + 1) et b = 3(1 - 6q)
il faut déterminer une condition sur l entier q pour que b ne soit pas divisible par 5
1-6q ou bien 6q+1 non divisible par 5


q+1=0mod 5 signifie q=4mod5 donc q=0 mod5 ou q=1mod 5 ou q=2mod5 q=3mod 5

est ce que mon travail est juste
merci

[olivier 2020]

Salut zygomatique
comment éliminer le diviseur 5 ?
et donner moi svp le résultat finale

merci

[chan79]

Salut zygomatique
comment éliminer le diviseur 5 ?
et donner moi svp le résultat finale

merci

a=5k
b=6-3k
Si d divise a et b, il divise 30
Si k est pair, le PGCD de a et b est supérieur ou égal à 2.

Si k=1+30m
a=5+150m
b=6-3(1+30m)=3-90m
Si d divise a et b, il divise 5 et 3 (car il divise 30). Donc d=1
Si k est congru à 1 (mod 30) le PGCD de a et b est égal à 1.

Si k=3+30m
a=15+150m
b=-3-90m
Le PGCD de a et b est supérieur ou égal à 3.

Si k=5+30m
a=25+150m
b=6-3(5+30m)=-9-90m
Le PGCD de a et b est égal à 1 (il divise 25 et 9)

on continue gentiment jusqu'à k=29 modulo 30

J'arrive aux valeurs suivantes pour k: {1;5;11;13;19;23;25;29} mod 30.
à vérifier... il y a sans doute plus rapide

[zygomatique]

c'est ce que Ben314 fait dans le lien que j'ai donné plus haut ....

pour aller un peu plus vite ::

si k est pair le pgcd est multiple de 2
si k est multiple de 3 le pgcd est multiple de 3 ...

donc on essaie k = 6p +- 1 (mod 30) (voir post nodjim ....)

....

[zygomatique]

a = 5k
b = 6 - 3k = 3(2 - k)

on pose donc k = 6p + 1

a = 5(6p + 1) = 30p + 5
b = 3(1 - 6p) = 3 - 18p

6p - 1 et 6p + 1 sont premiers entre eux ...

3 ne divise pas a

5 divise b 5 divise 1 - 6p 5 divise p - 1


p = 5q donc k = 30q + 1 donc a = 5(30q + 1) et b = 3(1 - 30q) ==> pgcd(a, b) = 1
p = 5q + 2 donc k = 30q + 13 donc a = 5(30q + 13) et b = 3(11 - 30q) ==> pgcd (a, b) = 1

puis p = 5q + 3 / + 4

puis on recommence avec k = 6p - 1 ....

[chan79]

[quote="zygomatique"]c'est ce que Ben314 fait dans le lien que j'ai donné plus haut ....
[\QUOTE]
OK, je vais y regarder.

[chan79]

c'est ce que Ben314 fait dans le lien que j'ai donné plus haut ....



....

Ah OK, je vais y regarder

[olivier 2020]

salut chan79
merci pour votre message