\documentclass[12pt]{book}\usepackage[Aymar1]{ammaths2}\usetikz\begin{document}



\newcommand{\pgcd}{\mbox{PGCD}}
\newcommand{\ppcm}{\mbox{PPCM}}


\chapitre{1}{Divisibilité dans $\Z$}{Ts Spé}
\begin{minipage}{16cm}
\tableofcontents
\end{minipage}
\newpage

\section{Diviseurs et multiples}

\txt{L'ensemble $\Z$ des entiers relatifs est stable par addition,
soustraction et multiplication, c'est à dire que chacune
 de ces opérations, appliquée à deux entiers relatifs, donne un entier relatif.
 Ce n'est pas le cas pour la division.
 On trouve sans difficulté des exemples de divisions d'entiers donnant des résultats
 non entiers. Les divisions restant dans le cadre de l'ensemble $\Z$
 ont de ce fait un intérêt particulier.}

\defi{Diviseur -- Multiple}{Soient $a$ et $b$ deux nombres entiers relatifs non nuls. On dit que $a$ est divisible par $b$ si il existe un
entier relatif $c$ tel que $a=bc$. On dit alors que $b$ est un \defin{diviseur} de $a$ et que $a$ est un \defin{multiple}
de $b$.}

\exe{12 est divisible par 3 ; 3 est un diviseur de 12 ; 12 est un multiple de 3.}

\prop{}{Soient $a$ et $b$ deux entiers tels que $a$ est divisible par
$b$. Alors,
\begin{enumerate}
\item L'entier $a$ est divisible par $-b$.
\item Les nombres $a$ et $b$ vérifient $|b|\leq |a|$.
\item Si d'autre part $b$ est divisible par $a$, alors $a=b$ ou $a=-b$.
\item Si $k$ est un entier quelconque non nul, alors $bk$ divise $ak$.
\item Si $d$ est un entier qui divise $b$, alors $d$ divise $a$. On dit que la relation de divisibilité est transitive.
\end{enumerate}
}


\dem{Par définition, le fait que $a$ soit divisible par $b$ signifie
qu'il existe un entier relatif $c$ tel que $a=bc$.\begin{enumerate}
\item Sachant que $a=bc$, il est clair que $a=(-b)(-c)$ donc
$a$ est divisible par $-b$.
\item Par définition, $1\leq |c|$ donc $|b|\leq |bc|$, c'est à dire $|b|\leq |a|$.
\item D'après la propriété démontrée précédemment, si $b$ divise $a$ et $a$ divise
$b$ alors on a à la fois $|b|\leq |a|$ et $|a|\leq |b|$, donc
$|a|=|b|$. Ceci signifie que soit $a=b$, soit $a=-b$.
\item On sait que $a=bc$, donc $ak=(bc)k=(bk)c$, ce qui prouve que $bk$ divise $ak$.
\item Si $d$ divise $b$, alors il existe un entier $c'$ tel que $b=dc'$. On en déduit
que $a=bc=dc'c$ et donc que $d$ divise $a$.
\end{enumerate}
}

\prop{Linéarité de la divisibilité}{Si un entier $b$ divise deux entiers $a$ et $a'$, alors $b$
divise toute combinaison linéaire de $a$ et $a'$, c'est à dire tout entier de la forme $au+a'v$, où $u$ et $v$ sont deux
entiers quelconques. En particulier, $b$ divise $a+a'$ et $a-a'$.}

\exe{12 divise 24 et 36 donc, sans faire de calcul, on sait que 12 divise $5*24+2*36$.}

\dem{Par définition, si $b$ divise $a$ et $a'$, il existe deux
entiers $c$ et $c'$ tels que $a=bc$ et $a'=bc'$. Ainsi, quels que
soient les entiers $u$ et $v$, $au+a'v=(bc)u+(bc')v=b(cu+c'v)$, ce
qui prouve que $b$ divise $au+a'v$.}

\section{P.G.C.D de deux entiers}

\defi{}{Soit $a$ un entier positif. On note ${\cal D}(a)$ l'ensemble des
diviseurs positifs de $a$. Cet ensemble est fini car tout diviseur
positif $m$ de $a$ vérifie $m<a$.\\ Par convention, l'ensemble ${\cal D}(0)$ est
l'ensemble des entiers naturels.}

\exe{${\cal D}(12)=\{1;2;3;4;6;12\}$.}

\defi{Plus grand diviseur commun}{Soient $a$ et $b$ deux entiers naturels. L'ensemble de leurs diviseurs positifs communs est
${\cal D}(a,b)={\cal D}(a)\cap{\cal D}(b)$. Cet ensemble est fini
car majoré par $a$ et $b$. Il contient donc un plus grand élément
unique $d$, le plus grand diviseur commun de $a$ et $b$. On
le note \defin{P.G.C.D} de $a$ et $b$ et on le note $\pgcd(a,b)$ ou $a\wedge
b$.}

\exe{${\cal D}(12)=\{1;2;3;4;6;12\}$ et ${\cal D}(16)=\{1;2;4;8;16\}$ donc $\pgcd(12,16)=4$.}


\prop{}{Soient $a$ et $b$ deux entiers positifs.
\begin{enumerate}
\item ${\cal D}(a,0)={\cal D}(a)$, donc $\pgcd(a,0)=a$.
\item Si $b$ divise $a$ alors ${\cal D}(a,b)={\cal D}(b)$ et donc $\pgcd(a,b)=b$.
\item $\pgcd(a,b)\geq 1$, car $1\in{\cal D}(a,b)$.
%\item ${\cal D}(a,b)={\cal D}(d)$ où $d$ est le P.G.C.D de $a$ et $b$.
\end{enumerate}}

\dem{\begin{enumerate}
\item Par définition ${\cal D}(a,0)={\cal D}(a)\cap{\cal D}(0)={\cal D}(a)\cap \N={\cal
D}(a)$. Il est alors clair que $\pgcd(a,0)=a$.
\item Si $b$ divise $a$ il est clair que ${\cal D}(b)\subset{\cal D}(a)$ et donc
${\cal D}(a)\cap {\cal D}(b)={\cal D}(b)$. Par conséquent
$\pgcd(a,b)=b$.
\item Il est clair que $1$ divise $a$ et $b$, donc $1\in{\cal D}(a)$ et
$1\in{\cal D}(b)$, ce qui prouve que $1\in{\cal D}(a)\cap{\cal
D}(b)={\cal D}(a,b)$. Par conséquent, $\pgcd(a,b)\geq 1$.
%\item Tout élément $e$ de ${\cal D}(d)$ divise $d$ et donc à la fois
%$a$ et $b$. Ainsi, tout élément de ${\cal D}(d)$ est élément de
%${\cal D}(a,b)$, ce qui prouve que ${\cal D}(d)\subset {\cal
%D}(a,b)$. Soit $f$ un élément de ${\cal D}(a,b)$. Il divise à la
%fois $a$ et $b$, c'est à dire qu'il existe deux réels $s$ et $t$
%tels que $a=sf$ et $b=tf$.
%${\cal D}(a,b)={\cal D}(d)$ où $d$ est le P.G.C.D de $a$ et $b$.
\end{enumerate}}


\defi{}{Soient $a$ et $b$ deux entiers relatifs. Leur P.G.C.D est $PGCD(a;b)=PGCD(|a|;|b|)$.}

\section{Les nombres premiers}

\subsection{Définition}

\defi{Nombre premier}{Un entier naturel $n$ est \defin{premier} s'il admet exactement deux diviseurs positifs distincts, 1 et lui-même.}

\exes{
    \begin{itemize}
        \itemb L'entier 1 n'est pas premier car il n'a qu'un diviseur positif.
        \itemb Le plus petit nombre premier est 2, qui est divisible
        par 1 et 2.
        \itemb 3 est aussi premier.
        \itemb 4 n'est pas premier car il est divisible par 1, 2 et 4.
        \itemb Plus généralement, un nombre pair supérieur à 4 n'est pas premier, car il est divisible par
        1, 2 et lui-même, soit au moins 3 diviseurs.
    \end{itemize}
}

% \defi{}{Les \emph{diviseurs stricts} d'un entier $n$ sont tous ses diviseurs différents de
% $n$. Ainsi, un nombre premier est un entier naturel différent de $1$
% admettant un seul diviseur strict.}

\subsection{Reconnaître un nombre premier}

\subsubsection{Méthode directe}

Soit $n$ un entier. Pour savoir si $n$ est premier, on effectue les divisions de $n$ par tous les entiers naturels inférieurs à $n$.
Si aucune de ces divisions ne donne un résultat entier, alors $n$ est un nombre premier.

\subsubsection{Méthode directe optimisée}

\txt{Elle est basée sur la propriété suivante :}


\prop{}{Si tous les nombres premiers inférieurs à $\sqrt{N}$ ne sont pas des diviseurs de N, alors N est un nombre premier.}

\exe{53 est -il un nombre premier ?\\
$\sqrt{53}$ environ 7,28.  Les nombres premiers inférieurs à 7,28 sont 2, 3, 5, 7. Comme aucun d'eux ne divisent 53, alors 53 est un nombre premier.}

% \prop{}{Tout entier naturel $n$ non premier admet un diviseur
% strictement supérieur à 1 et inférieur ou égal à $\sqrt{n}$.}
% 
% \dem{Soit $n$ un entier non premier et $d$ un diviseur strict de
% $n$, (c'est à dire différent de $1$ et $n$). Si $d\leq\sqrt{n}$ la
% propriété est bien vérifée. Si $d>\sqrt{n}$, alors $d'=\frac{n}{d}$
% est un diviseur de $n$ différent de $d$, de $1$ et de $n$ et
% $$d'=\frac{\sqrt{n}\sqrt{n}}{d}\leq\frac{\sqrt{n}\sqrt{n}}{\sqrt{n}}=\sqrt{n}$$
% ce qui prouve que la propriété est aussi vérifiée dans ce cas.}
% 
% Pour déterminer si un entier naturel $n$ est premier, il suffit donc
% d'effectuer les divisions de $n$ par les entiers naturels inférieurs
% à $\sqrt{n}$. On peut encore améliorer cette méthode en se limitant
% aux nombres premiers. En effet, si un entier $m$ inférieur à $n$
% n'est pas premier, il admet un diviseur $m'$ tel que $1<m'<m$. En
% procédant aux divisions dans l'ordre croissant en commençant par 2,
% il est ainsi inutile de vérifier que $m$ ne divise pas $n$ après
% l'avoir vérifié pour $m'$.

\subsubsection{Crible d'Erathostène}

A proprement parler, le crible d'Erathostène ne détermine pas si un
entier est premier. C'est une méthode pour dresser la liste de tous
les nombres premiers inférieurs à un entier naturel $n$. Prenons
l'exemple $n=50$. Plaçons tous les entiers naturels inférieurs à 50
dans un tableau.
\par
    \begin{center}
        \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}
        \hline
        1 & 2 & 3 & 4 & 5 & 6 & 7 & 8& 9 & 10 \\
        \hline
        11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\
        \hline
        21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 & 30 \\
        \hline
        31 & 32 & 33 & 34 & 35 & 36 & 37 & 38 & 39 & 40 \\
        \hline
        41 & 42 & 43 & 44 & 45 & 46 & 47 & 48 & 49 & 50 \\
        \hline
        \end{tabular}
    \end{center}
Commençons par barrer le nombre 1, qui n'est pas premier par
définition. Le nombre 2 est premier. On peut alors barrer tous les
multiples de 2, puisqu'ils ne sont pas premiers. Le nombre non barré
suivant est donc premier, il s'agit de 3. On barre maintenant tous
les multiples de 3, qui ne peuvent pas être premiers et on passe au
nombre non barré suivant. Une fois tout le tableau parcouru, les
seuls entiers non barrés sont tous les nombres premiers inférieurs à
50.

\subsection{Ensemble des nombres premiers}

\txt{On a longtemps cherché une logique dans la répartition des
nombres premiers.  En vain. On est aujourd'hui persuadé que cette
répartition est anarchique. Seuls quelques résultats concernant
l'ensemble des nombres premiers sont connus à ce jour.}

\theo{Théorème d'Euclide (Livre IX, proposition 20)}{L'ensemble des nombres premiers est infini.}

\dem{Démontrons ce résultat par l'absurde, c'est à dire en supposant
que l'ensemble des nombres premiers est fini. \\
Notons alors $\cal P$ le produit de tous les nombres premiers. Il est clair que ${\cal
P}+1$ n'est divisible par aucun des nombres premiers (car $\cal P$ est divisible par chacun des nombres premiers mais $1$ ne l'est pas). Il est donc
premier, ce qui est impossible car il ne fait pas partie de
l'ensemble des nombres premiers. Ceci contredit notre hypothèse. Par
conséquent, l'ensemble des nombres premiers est infini.}

\rem{La demonstration s'appuie sur le fait que si $a$ et $b$ sont premiers alors $a\times b+1$ l'est aussi.}

\txt{La répartition des nombres premiers est donnée par la fonction
$\pi$, où $\pi(x)$ est le nombre d'entiers premiers inférieurs à
$x$. Le mathématicien Tchebychef a démontré en 1896 que $\pi(x)$ est
équivalent, au voisinage de l'infini, à $\frac{x}{\ln x}$. Cela
signifie globalement que la proportion de nombres premiers est
décroissante}

%\prop{}{Soit $n$ un entier naturel quelconque. Il existe une suite de
%$n$ entiers naturels consécutifs non premiers.}
%
%\dem{Posons $N=(n+1)!=1\times 2\times\dots\times n\times (n+1)$.
%Pour $k$ compris entre 2 et $n+1$, il est clair que $N+k$ est
%divisible par $k$, et n'est donc pas premier. Les nombres $N+2$,
%$N+3$, $\dots$, $N+n+1$ sont bien $n$ entiers consécutifs non
%premiers.}



\subsection{Décomposition en facteurs premiers}

\prop{}{Soit $a$ un entier naturel ($a>1$). Alors :
\begin{itemize}
\itemb $a$ admet un diviseur premier.
\itemb Si $a$ n'est pas premier, il admet un diviseur premier $p$ tel que $2\leq p \leq \sqrt{a}$.
\end{itemize}
}

\dem{\begin{itemize}
\itemb Si $a$ est premier, comme $a$ divise $a$, la propriété est bien vérifiée.
\itemb Si $a$ n'est pas premier alors il admet au moins un diviseur strictement supérieur à $1$. Notons $p$ le plus petit d'entre ces diviseurs. 
$p$ est forcement premier car sinon, il admettrait un diviseur $d$ avec $1<d<p$, qui serait alors un diviseur de $a$ strictement inférieur au 
plus petit d'entre eux : $p$ ; c'est impossible. Donc $p$ est pemier.
\end{itemize}
De plus, $a$ s'écrit $a=pq$ avec $p\leq q$ ; on en tire : $p^2\leq pq=a \textrm{, donc } p\leq \sqrt{a}.$
Finalement, on a bien $$2\leq p\leq \sqrt{a}.$$
}

\theo{Décomposition en facteurs premiers}{Soit $n$ un entier supérieur ou égale à deux. Alors :
\begin{itemize}
 \itemb $n$ se décompose en un produit de facteur premier.
 \itemb Cette décomposition est unique à l'ordre des facteurs près.\\
 On note alors $n=p_1^{\alpha_1}\dots p_k^{\alpha_k}$ où  $p_1, p_2, \cdots p_r$ sont des nombres premiers distincts et $\alpha_1, \alpha_2, \cdots \alpha_r$ 
sont des entiers naturels non nuls.
\end{itemize}}

\dem{On ne démontrera que l'existence de la décomposition. L'unicité est admise.\\
Démontrons cette propriété par récurrence.
 \begin{itemize}
\itemb \textbf{Initialisation :} Pour $n=2$, elle est vraie puisque 2 est lui-même premier. 
\itemb \textbf{Hérédité : } Supposons la propriété vérifiée pour tout entier $n\leq k$ et étudions le cas $n=k+1$. 
	\begin{itemize}
	\itemb  Si $k+1$ est premier, la propriété est bien vérifiée. 
	\itemb  Sinon, $k+1$ admet un diviseur premier $p$ et il existe $k'$ tel que $k+1=pk'$ avec
	$k'<k+1$. Par récurrence, $k'$ est un produit de nombres
	premiers, et donc $k+1$ aussi.
	\end{itemize}
\end{itemize}}

\dem{Voici une autre preuve moins formelle :\\
D'après la proposition 5, $n$ admet un diviseur premier $p_1$, alors $n=p_1n_1$ avec $1\leq n_1<n$, puisque $p_1\geq2$.\\
Si $n_1=1$, c'est terminé.\\
Si $n_1\geq2$ on répète ce raisonnement avec $n_1$ : $n_1$ admet un diviseur premier $p_2$ et $n_1=p_2n_2$, avec $1\leq n_2 < n_1 <n$.\\
On itère ce raisonnement tant que le quotient $n_i$ n'est pas égal à $1$.\\
La suite de ces quotients étant strictement décroissante ($\cdots < n_i<\cdots <n_2<n_1<n$), le processus s'arrête à une certaine étape $k$. Alors
$n=p_1p_2\cdots p_k$ et en regroupant les facteurs non distincts, on obtient :
$$n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$$}

\txt{{\bf Méthode de décomposition}\par}

\txt{Pour décomposer un entier naturel en facteurs premiers, on peut
utiliser une méthode systématique qui consiste à tester un par un
par les facteurs possibles, c'est à dire les nombres premiers
inférieurs à $n$. L'exemple suivant, $n=2184$ expose le procédé et
sa présentation graphique conventionnelle :\par
    \begin{center}
        \begin{tabular}{lr|l}
        2184 est divisible par 2 et le quotient est 1092\hspace{12pt} & 2184 & 2 \\
        1092 est divisible par 2 et le quotient est 546 & 1092 & 2 \\
        546 est divisible par 2 et le quotient est 273 & 546 & 2 \\
        273 est divisible par 3 et le quotient est 91 & 273 & 3 \\
        91 est divisible par 7 et le quotient est 13 & 91 & 7 \\
        13 est un nombre premier & 13 & 13 \\
        La décomposition est terminée & 1 & \\
        \end{tabular}
    \end{center}
La décomposition en facteurs premiers de 2184 est donc
$2184=2^3\times 3\times 7\times 13$.}


\theo{}{Soit $n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$ la décomposition
en nombres premiers d'un entier naturel $n$. Les diviseurs de $n$
sont les entiers dont les décompositions sont de la forme
$p_1^{\beta_1}\cdots p_k^{\beta_k}$, où pour tout
$i\in\{1,\cdots,k\}$, $\beta_i\leq\alpha_i$.}

\dem{Il est clair qu'un entier de la forme donnée dans le théorème
divise bien $n$. Il reste à démontrer que tout diviseur de $n$ est
de cette forme.\\
 Soient $d$ un diviseur de $n$, $p$ un facteur
premier de $d$ et $\beta$ tel que $d=p^{\beta}d'$, où $d'$ n'est pas
divisible par $p$. Alors $p^{\beta}$ divise $n$ et donc $p$ doit
être l'un des facteurs premiers de $n$, disons $p_i$. Il est alors
clair que $\beta$ doit être inférieur à $\alpha_i$. Comme ceci est
vrai pour tous ses diviseurs premiers, $d$ est bien de la forme
donnée dans le théorème.}

\prop{}{Soit $n$ un entier supérieur ou égal à $2$, admettant la décomposition en facteur premier :
$$n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}\,.$$
Le nombre de diviseurs de $n$ est :
$$(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_k+1)\,.$$}

\dem{Si $n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$, alors d'après la proposition précédente, tout diviseur $d$ de $n$ s'écrit
$d=p_1^{\beta_1}\cdots p_k^{\beta_k}$, où pour tout $i\in\{1,\cdots,k\}$, $\beta_i\leq\alpha_i$.\\
On a $\alpha_1+1$ choix pour la valeur de $\beta_1$, $\alpha_2+1$ choix pour la valeur de $\beta_2$, \dots}

\section{P.P.C.M}

\defi{}{Soient $a$ et $b$ deux entiers positifs. L'ensemble des
multiples positifs non nuls communs à $a$ et $b$ n'est pas vide car
il contient $ab$, et il est minoré par $a$ et $b$. Il contient donc
un plus petit élément. Cet élément est appelé P.P.C.M de $a$ et $b$ et
noté $\ppcm(a,b)$ ou $a\vee b$.}

\prop{}{Tout multiple commun à $a$ et $b$ est un multiple de leur P.P.C.M
$m$.}

\dem{Soit $n$ un multiple commun à $a$ et $b$ et $m$ leur P.P.C.M. Par
définition de $m$, on a $m\leq n$. La division de $n$ par $m$ donnent deux nombres 
$q$ et $r$ tel que $n=mq+r$ avec $r<m$.\\
On a alors $r=n-mq$ qui est un multiple commun à
$a$ et $b$ (car $n$ et $m$ le sont) et qui est inéfrieur à $m$. Par définition de $m$, on a donc
$r=0$. Ainsi $n$ est un multiple de $m$.}

\theo{}{Soient $a$ et $b$ deux entiers. Si $d$ et $m$ sont
respectivement le P.G.C.D et le P.P.C.M de $a$ et $b$, alors $md=ab$.}

\dem{\begin{itemize}
\itemb On considère l'entier $\frac{ab}{d}$. $d$ étant le pgcd, il existe $a'$ et $b'$ entiers tels que $\frac{ab}{d}=a'b=ab'$ ce qui signifie que $\frac{ab}{d}$ est un multiple commun à $a$ et $b$.\\
C'est donc, d'après la propriété précédente, un multiple de $m$. Cela signifie
qu'il existe $k$ dans $\Z$ tel $\frac{ab}{d}=km$, et donc $ab=kmd$.
\itemb $m$ étant un multiple commun à $a$ et $b$, il existe $h$ et $h'$ dans $\Z$ tels que $m=ah$ et $m=bh'$. En remplaçant $m$ par la première de ces expressions, on obtient $ab=kahd$, et donc $b=kdh$. L'entier $b$ est donc divisible par $kd$. De manière
analogue $kd$ divise aussi $a$. Par maximalité de $d$, on doit donc
avoir $kd\leq d$. La seule valeur possible pour $k$ est 1, ce qui
implique $ab=md$.
\end{itemize}
}

%\prop{}{Soient $a$ et $b$ deux entiers. Leur P.P.C.M $m$ est l'unique
%multiple commun à $a$ et $b$ tel que $\frac{m}{a}$ et $\frac{m}{b}$
%soient premiers entre eux.}
%
%\dem{Soit $m$ le P.P.C.M de $a$ et $b$ et soit $d$ leur P.G.C.D. Nous
%avons vu que $ab=mb$. Donc $\frac{m}{a}=\frac{b}{d}$ et
%$\frac{m}{b}=\frac{a}{d}$. Or on a vu précédemment que $\frac{b}{d}$
%et $\frac{a}{d}$ sont premiers entre eux. Par conséquent
%$\frac{m}{a}$ et $\frac{m}{b}$ le sont aussi. Réciproquement, soit
%$m'$ un multiple de $a$ et $b$ tel que $\frac{m'}{a}$ et
%$\frac{m'}{b}$ soient premiers entre eux. Soit $m$ le P.P.C.M de $a$ et
%$b$. L'entier $m'$ est un multiple de $m$, donc il existe un entier
%$k$ tel que $m'=mk$. Alors $\frac{m'}{a}=k\frac{m}{a}$ et
%$\frac{m'}{b}=k\frac{m}{b}$. l'entier $k$ divise donc $\frac{m'}{a}$
%et $\frac{m'}{b}$, qui sont premiers entre eux par hypothèse. Donc
%$k=1$, $m=m'$, $m'$ est le P.P.C.M de $a$ et $b$.}

%\pagebreak
\theo{}{Soient $a$ et $b$ deux entiers. Notons $\{p_1,\dots,p_k\}$
l'union des ensembles de leurs facteurs premiers. On peut noter
$a=p_1^{\alpha_1}\cdots p_k^{\alpha_k}\mbox{ et }b=p_1^{\beta_1}\dots
p_k^{\beta_k}$ où certains exposants $\alpha_i$ et $\beta_i$ sont
éventuellement nuls. Notons $d$ et $m$ respectivement le P.G.C.D et le
P.P.C.M de $a$ et $b$. Alors
    $$d=p_1^{\mbox{Min}(\alpha_1,\beta_1)}\cdots
    p_k^{\mbox{Min}(\alpha_k,\beta_k)}\mbox{ et }m=p_1^{\mbox{Max}(\alpha_1,\beta_1)}\cdots
    p_k^{\mbox{Max}(\alpha_k,\beta_k)}.$$}

\dem{Soit $d'$  un diviseur commun de $a$ et $b$. D'après le
théorème 3.3, $d'$ est de la forme $p_1^{\gamma_1}\dots
p_k^{\gamma_k}$, où pour tout $i\in\{1,\dots,k\}$,
$\gamma_i\leq\alpha_i$ et $\gamma_i\leq\beta_i$, c'est à dire
$\gamma_i\leq\mbox{Min}(\alpha_i,\beta_i)$. Par conséquent tout diviseur commun à $a$ et $b$
$d'$ vérifie $d'\leq p_1^{\mbox{Min}(\alpha_1,\beta_1)}\dots
p_k^{\mbox{Min}(\alpha_k,\beta_k)}$, et comme ce produit est bien un
diviseur de $a$ et $b$, c'est leur P.G.C.D. D'autre part on sait que
$ab=md$, c'est à dire $m=\frac{ab}{d}$, et donc
    \begin{eqnarray}
    m & = & \frac{p_1^{\alpha_1}\cdots p_k^{\alpha_k}\times p_1^{\beta_1}\cdots p_k^{\beta_k}}
    {p_1^{\mbox{Min}(\alpha_1,\beta_1)}\cdots p_k^{\mbox{Min}(\alpha_k,\beta_k)}}
    \nonumber \\
    m & = & \frac{p_1^{\alpha_1+\beta_1}\cdots p_k^{\alpha_k+\beta_k}}
    {p_1^{\mbox{Min}(\alpha_1,\beta_1)}\cdots p_k^{\mbox{Min}(\alpha_k,\beta_k)}}
    \nonumber \\
    m & = & p_1^{\mbox{Max}(\alpha_1,\beta_1)}\cdots p_k^{\mbox{Max}(\alpha_k,\beta_k)}\nonumber
    \end{eqnarray}
}

\exe{Prenons $a=2184$ et $b=1617$. Leurs décompositions en facteurs
premiers sont $a=2^3\times 3\times 7\times 13$ et $b=3\times
7^2\times 11$. Donc
    \begin{eqnarray}
    PGCD(a,b) & = & 3\times7=21 \nonumber \\
    PPCM(a,b) & = & 2^3\times 3\times 7^2\times 11\times 13\nonumber \\
              & = & 168168.\nonumber
    \end{eqnarray}}


\end{document}
