Identité de bezout

[kadaid]

Bonjour

Soit les entiers:

a=26k+1

b=22k+1

k entier

Montrer que a et b sont premiers entre eux

On peut le montrer avec la methode de diviseurs ou pgcd

Mais j'ai voulu appliquer l'identité de Bezout:

S'il existe deux entiers relatifs u et v tels que:

ua + vb=1 alors a et b sont premiers entre eux

u(26k+1)+v(22k+1)=1

Je n'arrive pas à determiner u et v

Merci pour vos commentaires



--------------------------------------------------------------------------------


--------------------------------------------------------------------------------


--------------------------------------------------------------------------------

[Ben314]

Salut,
Il faut bien te dire que, vu que a et b dépendent de k, il est plus que probable que ton 'u' et ton 'v' doivent dépendre de k.
Si tu tient absolument à faire des calculs, tu peut essayer d'utiliser l'algo. d'Euclide "étendu" sur a et b pour voir comment ça marche et essayer d'en déduire au moins un couple u,v qui marche.
Tu peut aussi essayer (juste pour voir) si tu trouve des constantes a,b,c,d telles que, en prenant u=ak+b et v=ck+d, l'égalité au+bv=1 soit vraie pour tout les k (c'est faisable...)

[kadaid]

Bonjour Ben314

Voici le travail que tu m'as conseillé de faire.

Soit les entiers 26k+1 et 22k+1, k entier
Montrer que ces entiers sont premiers entre eux par différentes méthodes.

Première méthode

soit d un diviseur de des deux entiers, alors d divise 22(26k+1)-26(22k+1) soit d divise –4
d divise 4. Or 26k+1 et 22k+1sont impairs donc non divisibles par 2 ou 4. Ils sont divisibles par 1
Conclusion : 26k+1 et 22k+1 sont premier entre eux

Deuxième méthode :

Cherchons deux entiers relatifs, u et v, s’ils existent tels que : u(26k+1) + v(22k+1)=1
Posons u=ak+b et v= ck+d
(ak+b)(26k+1) +(ck+d)(22k+1)=1 (1)
Puis par identification des coefficients des puissances de k, on obtient :
26a+22c=0
a+c+26b+22d=0
b+d=1

On pose d=q et on résout le systeme en fonction de q
d=q, a=-11(2q-13), c=13(2q-13) et b=1-q

u=-22qk+143k-q+1
v=26qk-169k+q
l’égalité (1) est vérifiée mais les calculs sont longs !

Troisième méthode
Algorithme d’euclide étendu
Dividende, diviseur, quotient, reste
26k+1=(22k+1)*1+4k
22k+1=4k*(5)+1+2k
4k=(1+2k)*2-2 (le reste est négatif…)
1+2k=-2*(-k)+1
-2=-2*(1)+0

En remontant l’algorithme :
1=(1+2k)-2*(k)
……………….
1=(26k+1)(11k-5)+(22k+1)(-13k+6)
donc u=11k-5 et v=-13k+6

Apparemment ça marche mais le reste –2 m’inquiète car un reste doit être positif

[Ben314]

C'est nickel.
Pour la méthode 2), tu peut un peu simplifier les calculs vu qu'en fait tu ne cherche pas toutes les solutions a,b,c,d de ton système de 3 équations, mais une seule solution donc à un moment bien choisi, tu peut dire "je prend par exemple telle variable = ça" vu que je ne cherche qu'une seule solution.

Apparemment ça marche mais le reste –2 m’inquiète car un reste doit être positif

On peut effectivement avoir des doutes, mais d'un autre coté, dés la ligne 1, tu écrit
26k+1=(22k+1)*1+4k
et il n'est pas clair non plus que 4k soit positif, ni qu'il soit inférieur à |22k+1| donc ce n'est pas forcément le reste de la division de 26k+1 par 22k+1.
Mais en fait, cela n'a aucune importance : dans l'algo d'euclide, le "coeur" de la preuve repose sur le fait que, si la division euclidienne de n par m donne un quotient q et un reste r, alors pgcd(n,m)=pgcd(m,r).
Sauf qu'en fait r=n-qm et que la relation pgcd(n,m)=pgcd(m,n-qm) est valable pour n'importe quel entier (relatif) q et pas seulement pour le quotient de la division.

Par exemple, si on te demand de calculer le pgcd de 126 et de 43, l'algo "normal" d'euclide commence par
pgcd(126,43) = pgcd(43,126-2*43) = pgcd(43,40) = ...
Mais pour gagner du temps, tu peut aussi directement écrire que
pgcd(126,43) = pgcd(43,126-3*43) = pgcd(43,-3) = pgcd(43,3) = ...
Tu peut même écrire que
pgcd(126,43) = pgcd(43,126-4*43) = pgcd(43,-46) = pgcd(43,46) = ...
Mais là, ça sert vraiment à rien...

[kadaid]

Merci Ben314
C'est vraiment complet ce que tu m'as expliqué.
Je vais reprendre les exemples que tu as donnés.

[nodjim]

On pourrait aussi écrire:
26k+1-(22k+1)=4k
pgcd(4k,22k+1)=pgcd(k, 22k+1) car 22k+1 impair.
or pgcd(k, 22k+1)=1 c'est le reste de la division de 22k+1 par k.