par sos-math(21) » dim. 14 juin 2020 10:00
Bonjour,
tes entiers \(x\) et \(y\) sont solutions de l'équation \(409x-68y=17\).
Le "si et seulement si" correspond à une équivalence donc on fait la preuve par double implication.
le sens direct \((pgcd(x,y)=17)\Longrightarrow (y\equiv 17k \,[x])\) : si 17 est le pgcd de \(x\) et \(y\), alors il divise \(x\) et \(y\), \(x=17k\) et \(y=17k'\) et la division euclidienne de \(y\) par \(x\) donne \(y=qx+r\) donne \(17k'=17k'q+r\) donc \(r=17k'-17k'q=17(k-k'q)\) ce qui prouve bien que le reste est un multiple de 17.
Dans l'autre sens : \((y\equiv 17k \,[x])\Longrightarrow (pgcd(x,y)=17)\)
on a encore la division euclidienne de \(y\) par \(x\) qui donne \(y=qx+r\).
si on note \(d=pgcd(x,y)\) alors \(d|x\) et \(d|y\) donc \(d\) divise toute combinaison de \(x\) et \(y\) en particulier \(d|409x-68y=17\) donc \(d|17\)
donc comme 17 est premier \(d=1\) ou \(d=17\).
Or on a vu dans la question 1 que si \(x\) est solution de l''équation, alors c'est un multiple de 17 donc 17 divise \(x\) donc aussi \(qx\) et 17 divise le reste \(r\) par hypothèse, donc \(17\) divise \(qx+r\) soit \(17\) divise \(y\). Donc 17 est un diviseur commun à \(x\) et \(y\) donc 17 divise leur pgcd et on a nécessairement \(d=17\).
Est-ce plus clair ?
Bonjour,
tes entiers \(x\) et \(y\) sont solutions de l'équation \(409x-68y=17\).
Le "si et seulement si" correspond à une équivalence donc on fait la preuve par double implication.
le sens direct \((pgcd(x,y)=17)\Longrightarrow (y\equiv 17k \,[x])\) : si 17 est le pgcd de \(x\) et \(y\), alors il divise \(x\) et \(y\), \(x=17k\) et \(y=17k'\) et la division euclidienne de \(y\) par \(x\) donne \(y=qx+r\) donne \(17k'=17k'q+r\) donc \(r=17k'-17k'q=17(k-k'q)\) ce qui prouve bien que le reste est un multiple de 17.
Dans l'autre sens : \((y\equiv 17k \,[x])\Longrightarrow (pgcd(x,y)=17)\)
on a encore la division euclidienne de \(y\) par \(x\) qui donne \(y=qx+r\).
si on note \(d=pgcd(x,y)\) alors \(d|x\) et \(d|y\) donc \(d\) divise toute combinaison de \(x\) et \(y\) en particulier \(d|409x-68y=17\) donc \(d|17\)
donc comme 17 est premier \(d=1\) ou \(d=17\).
Or on a vu dans la question 1 que si \(x\) est solution de l''équation, alors c'est un multiple de 17 donc 17 divise \(x\) donc aussi \(qx\) et 17 divise le reste \(r\) par hypothèse, donc \(17\) divise \(qx+r\) soit \(17\) divise \(y\). Donc 17 est un diviseur commun à \(x\) et \(y\) donc 17 divise leur pgcd et on a nécessairement \(d=17\).
Est-ce plus clair ?
