%@Titre: PGCD et Division Euclidienne
%@Dif:3
\paragraph{Exemple}
Effectue la division euclidienne de 434 par 126.
\[434=126\times\ldots+\ldots\]
\par Soit $d$ le $\pgcd(434;126)$ donc $434=d\times n$ et $126=d\times m$ avec $n$ et $m$ deux nombres entiers.
\par Est-ce que $d$ divise 56 ?
\par$56=434-3\times126=\ldots\ldots-\ldots\ldots\ldots=\ldots\ldots-\ldots\ldots=\ldots\times\ldots\ldots$ donc
\dotfill\par\dotfill.
\[\left.\begin{tabular}{l}
$d$ divise $56$\\
$d$ divise $126$\\
\end{tabular}
\right\}
\mbox{Donc $d$ est un diviseur commun de 126 et 56.}
\]
Est-ce le plus grand ?
Soit $\ell$ le $\pgcd(126;56)$. Alors $d\leqslant\ell$ et $126=\ell\times n$ et $56=\ell\times m$.
\\On obtient
\[434=126\times3+56=\ell\times n\times3+\ell\times m=\ell\times(3n+m)\]
$\ell$ est donc un diviseur commun à 434 et 126 donc $\ell\leqslant d$.
\\$d$ est donc le $\pgcd(126;56)$.
\paragraph{Théorie}
Soit $(q;r)$ le couple obtenu par la division euclidienne de $a$ par $b$.
\[a=b\times q+r\]
\par Soit $d$ le $\pgcd(a;b)$ donc $a=d\times n$ et $b=d\times m$ avec $n$ et $m$ deux nombres entiers.
\par$r=a-b\times q=\ldots\ldots\ldots-\ldots\ldots\ldots\ldots=\ldots\times\ldots\ldots\ldots$ donc $d$ divise $r$.
\[\left.\begin{tabular}{l}
$d$ divise $r$\\
$d$ divise $b$\\
\end{tabular}
\right\}
\mbox{Donc $d$ est un diviseur commun à $b$ et $r$.}
\]
Est-ce le plus grand ?
Soit $\ell$ le $\pgcd(b;r)$. Alors $d\leqslant\ell$ et $b=\ell\times b_1$ et $r=\ell\times r_1$.
\\On obtient alors que
\[a=b\times q+r=\ell\times b_1\times q+\ell\times r_1=\ell\times(b_1\times q+r_1)\]
$\ell$ est donc un diviseur commun de $a$ et $b$ et $\ell\leqslant d$.
Donc $d$ est le $\pgcd(b;r)$.
\paragraph{Pratique}
Comment faire, avec cette propriété, pour trouver le $\pgcd(548,124)$ ?