PGCD, congruence et Bezout

Retrouver tous les sujets résolus.
Répondre
Thibault

PGCD, congruence et Bezout

Message par Thibault » sam. 22 mai 2021 13:23

Bonjour,
Voici un exercice que j'ai à faire sur le PGCD :
Capture.PNG
Pour la question 1 pas de problème, le PGCD est toujours 1 sauf pour n=4 et n=9 où PGCD=5
Pour la deuxième, en calculant on tombe sur : 2a-3b=6n-14-(6n-9)=5, d'après le théorème de Bezout on en déduit que comme il existe u et v tel que ua+vb=5 alors PGCD (a,b)=5
J'en arrive donc à la troisième mais j'ai un peu de mal car 3n-7 congrue à 0[5] implique que 3n-7 divise 5 donc que 5k=3n-7 mais ici je suis bloqué car on est dans les entiers. Quelqu'un pourrait m'aider ? Merci d'avance
sos-math(21)
Messages : 10334
Enregistré le : lun. 30 août 2010 11:15

Re: PGCD, congruence et Bezout

Message par sos-math(21) » sam. 22 mai 2021 15:00

Bonjour,
attention, ton raisonnement est faux :
d'après le théorème de Bezout on en déduit que comme il existe u et v tel que ua+vb=5 alors PGCD (a,b)=5
S'il existe deux entiers \(x\) et \(y\) tels que \(d = ax + by\) , on peut seulement dire que \(d\) est un multiple du PGCD.
En effet, si tu considère le contre-exemple suivant : il existe deux entiers \(x\) et \(y\) tels que \(3x + 4y = 7\) (il suffit de prendre \(x = 1\) et \(y = 1\)) alors que 7 n'est pas le PGCD de 3 et 4.
Je te propose le raisonnement suivant : soit \(d\) le pgcd de \(a\) et \(b\), alors \(d\) divise toute combinaison linéaire de \(a\) et \(b\), donc \(d\) divise \(2a-3b= -5\) (tu avais calculé 5 d'ailleurs), alors \(d\) divise \(-5\) donc on peut en conclure que \(d=1\) ou \(d=5\) : dans ton raisonnement, tu avais perdu \(d=1\)
Pour la 3, avec les congruences, ton équation est équivalente à \(3n\equiv 2[5]\) car le reste de la division de 7 par 5 est 2.
Ensuite, tu peux établir la table des restes modulo 5 :
\(\begin{array}{|c|c|c|c|c|c|}\hline n\equiv &0&1&2&3&3&4\\\hline 3n\equiv &&&&&\\\hline\end{array}\)
Cela te donnera les candidats possibles qui donnent un reste de 2 modulo 5 lorsqu'on en prend le triple.
Je te laisse regarder cela de plus près.
Thibault

Re: PGCD, congruence et Bezout

Message par Thibault » sam. 22 mai 2021 17:10

Merci, je crois avoir réussi :
J'ai complété le tableau et j'en déduit que 3n≡2[5] si et seulement si n≡4[5], de là on en déduit que n-4 divise n, c'est à dire que 5k=n-4 et donc n=5k+4. Les entiers relatifs n tel que 3n-7≡0[5] sont donc de la forme 5k+4.
Pour la 4, est-ce que dire que le PGCD(a,b)=1 dans tout les cas sauf quand n=5k+4 où PGCD (a,b)=5 suffit où est ce qu'il y a d'autre choses à démontrer ?
sos-math(21)
Messages : 10334
Enregistré le : lun. 30 août 2010 11:15

Re: PGCD, congruence et Bezout

Message par sos-math(21) » sam. 22 mai 2021 17:30

Bonjour,
tu as bien travaillé et c'est effectivement ce qu'il fallait trouver : \(n=4+5k\) avec \(k\) entier.
Pour la 4, c'est bien cette réponse qui est attendue mais il faudra peut-être détailler ton raisonnement :
Sachant que tu as établi que le PGCD de \(a\) et de \(b\) est 1 ou 5, tu peux désormais faire une disjonction de cas :
  • Si \(n=4+5k\), avec \(k\in\mathbb{Z}\) (ce qu'on peut aussi écrire \(n\equiv 4\,[5]\)), alors \(5\) divise \(a=3n-7\) d'après la question précédente et on a aussi \(2n-3=2(4+5k)-3=8+10k-3=5+10k=5(1+2k)\) donc 5 divise aussi \(b\) donc le PGCD de \(a\) et \(b\) est 5.
  • Sinon, \(5\) ne divise pas \(a\) donc ne peut pas être le PGCD de \(a\) et de \(b\) donc le PGCD est égal à 1.
Bonne continuation
Répondre