\subsection{Diviseurs d'un nombre entier}
\begin{enumerate}
\item Effectue les divisions euclidiennes suivantes :
\begin{multicols}{3}
\begin{enumerate}
\item 399 par 21
\item 279 par 9
\item 357 par 17
\item 171 par 19
\item 252 par 14
\item 1\,683 par 99
\end{enumerate}
\end{multicols}
Que remarque-t-on ?
\item Traduis chacune de ces divisions par une égalité.
\item Peut-on faire la même remarque pour 543 et 18 ?
\end{enumerate}
\subsection{Diviseurs communs à deux nombres entiers}
\begin{enumerate}
\item
\begin{enumerate}
\item Donne les diviseurs de 399.
\item Donne les diviseurs de 171.
\item Que remarque-t-on ?
\end{enumerate}
\item
\begin{enumerate}
\item Donne les diviseurs de 145.
\item Donne les diviseurs de 78.
\item Que remarque-t-on ?
\end{enumerate}
\end{enumerate}
\subsection{Propriétés du $\pgcd$ de 2 nombres entiers}
Dans toute cette activité, $a$ et $b$ sont deux nombres entiers strictement positifs tels que $a>b$.
\subsubsection{Diviseurs et opérations}
\begin{enumerate}
\item\begin{enumerate}
\item Donne un diviseur $d$ (différent de 1) commun à 45 et à 35.
\item $d$ est-il un diviseur de $45+35$ ? de $45-35$ ?
\end{enumerate}
\item Supposons que 2 soit un diviseur de $a$ alors $a=2\times n$ avec $n$ un nombre entier.
\par Supposons que 2 soit un diviseur de $b$ alors $b=2\times m$ avec $m$ un nombre entier.
\par Alors 
$$\Eqalign{
a+b&=\ldots\times n+\ldots\times m=\ldots\times\ldots\ldots\qquad\mbox{d'où 2 est un diviseur de $\ldots\ldots\ldots$}\cr
a-b&=\ldots\times n-\ldots\times m=\ldots\times\ldots\ldots\qquad\mbox{d'où 2 est un diviseur de $\ldots\ldots\ldots$}\cr
}$$
\item Si $5$ est un diviseur commun à $a$ et $b$, prouve que 5 est aussi un diviseur de $a-b$.
\par 5 est un diviseur de \ldots alors $\ldots=5\times\ldots$ avec $n$ un nombre entier.
\par 5 est \dotfill.
\par Donc $a-b=\ldots\ldots\ldots\ldots\ldots=\ldots\times\ldots\ldots$ d'où \dotfill.
\end{enumerate}
\subsubsection{Théorie}
Si $k$ est un diviseur commun de $a$ et de $b$ alors $a=k\times a'$ et $b=k\times b'$ avec $a'$ et $b'$ des nombres entiers.
\par Donc $a-b=$\dotfill
\par d'où $k$ est un diviseur de $a-b$.
\par\underline{Application} Soit $k=\pgcd(a,b)$. Donc
$$\left.\begin{tabular}{l}
$k$ divise $a-b$\\
$k$ divise $b$\\
\end{tabular}
\right\}
\mbox{Donc $k$ est un diviseur commun à $b$ et $a-b$.}
$$
Est-ce le plus grand ?
Soit $l$ le $\pgcd(b;a-b)$. Alors $k\leqslant l$ et $b=l\times b_1$ et $a-b=l\times c_1$.
\\On obtient alors que
$$a=a-b+b=l\times c_1+l\times b_1=l\times(c_1+b_1)$$
$l$ est donc un diviseur commun de $a$ et $b$ et $l\leqslant k$.
Donc $k$ est le $pgcd(b;a-b)$.
\subsubsection{Pratique}
Comment faire, avec cette méthode, pour trouver le $\pgcd(254,76)$ ?
\subsection{PGCD et Division Euclidienne}
\subsubsection{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 $l$ le $\pgcd(126;56)$. Alors $d\leqslant l$ et $126=l\times n$ et $56=l\times m$.
\\On obtient
$$434=126\times3+56=l\times n\times3+l\times m=l\times(3n+m)$$
$l$ est donc un diviseur commun à 434 et 126 donc $l\leqslant d$.
\\$d$ est donc le $\pgcd(126;56)$.
\subsubsection{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 $l$ le $\pgcd(b;r)$. Alors $d\leqslant l$ et $b=l\times b_1$ et $r=l\times r_1$.
\\On obtient alors que
$$a=b\times q+r=l\times b_1\times q+l\times r_1=l\times(b_1\times q+r_1)$$
$l$ est donc un diviseur commun de $a$ et $b$ et $l\leqslant d$.
Donc $d$ est le $pgcd(b;r)$.
\subsubsection{Pratique}
Comment faire, avec cette propriété, pour trouver le $\pgcd{548,124}$ ?