\documentclass[12pt] {article} \usepackage[T1]{fontenc} 
\usepackage[latin1]{inputenc}
\usepackage{amsmath,amssymb,graphicx,multicol,mathrsfs, fancyhdr,enumerate,fourier,eurosym,alterqcm,enumerate,tabularx,numprint,sectsty}
\usepackage[dvips]{color}
\usepackage{pst-plot,pst-tree,pstricks,pst-node,pstricks-add,pst-math,pst-xkey,pst-eucl}
\usepackage{bclogo}
\usepackage[francais]{babel} 
\usepackage[colorlinks=true,pdfstartview=FitV,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref}
\everymath{\displaystyle}
\textwidth 19,5cm \textheight 24cm \hoffset 
-1,7cm \voffset -3.5cm \oddsidemargin 0pt 
\renewcommand{\thesubsection}{\textbf{\textcolor{red}{\Roman{subsection}}}} 
\renewcommand{\thesubsubsection}{\textbf{\textcolor{blue}{\Roman{subsection}.\arabic{subsubsection}}}} 
\title{\fbox{\textbf{\textcolor{blue}{PGCD et PPCM de deux entiers :}}}}
\date{}
\author{}
\pagestyle{fancy}
% pour le pied de page central
\cfoot{Page \thepage/\pageref{fin}}
\lhead{}


\begin{document}
\maketitle
\tableofcontents

\subsection{\textcolor{red}{Plus grand commun diviseur de deux entiers :}}
\begin{bclogo}[couleur = cyan!10, arrondi = 0.1,logo=\bcbook]{\textbf{}\textcolor{red}{Définition :}}
 Soient $a$ et $b$ deux entiers naturels non nuls. On note $\mathcal{D}(a)$ l'ensemble des diviseurs de $a$.\\
Le plus grand élément de $\mathcal{D}(a)\cap\mathcal{D}(b)$, ensemble des diviseurs positifs communs à $a$ et à $b$, est le \textbf{plus grand commun  diviseur} de $a$ et $b$, ou encore PGCD de $a$ et $b$. On le note pgcd$(a~;~b)$ ou PGCD$(a~;~b)$
\end{bclogo}

\textbf{\textcolor{blue}{Cas particuliers :}}\\
pgcd$(a~;~a)=a\qquad$ ~;~ $\qquad pgcd$(1~;~a)=1\qquad$ ~;~ $\qquad pgcd$(a~;~0)=a$ pour $a$ non nul.\\
\textbf{\textcolor{red}{Remarque :}} le PGCD de deux entiers naturels est un entier au moins égal à 1.\\

\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textbf{}\textcolor{red}{Propriété :}}
Soient $a$ et $b$ deux entiers naturels au moins égaux à 2.\\
Le PGCD de $a$ et $b$ est égal au produit des facteurs premiers communs de $a$ et de $b$, avec pour chacun d'eux, l'exposant le plus petit de ceux qu'il a dans $a$ et dans $b$.
\end{bclogo}

\textbf{\textcolor{red}{Démonstration :} :}\\
Soit $d$ le PGCD de $a$ et de $b$, naturels supérieurs ou égaux à 2. Comme $d$ divise $a$, sa décomposition en facteurs premiers est formée des facteurs premiers de $a$ avec un exposant au plus égal à celui qu'ils sont dans dans $a$. De même pour $b$.\\
Ainsi, la décomposition de $d$ comprend les facteurs premiers à $a$ et à $b$, avec un exposant au plus égal au plus petit des exposants dans les décompositions de $a$ et de $b$.\\
Comme $d$ est le plus grand des diviseurs communs, ces exposants sont égaux au plus petit de ceux se trouvant dans la décomposition de $a$ et de $b$.\\

\textbf{\textcolor{blue}{Exemple :}} cherchons le PGCD de 700 et de 90.\\

\textbf{\textcolor{red}{Remarque :}} Soien  $a$ et $b$ des entiers relatifs non nuls simultanément.\\
Comme $\mathcal{D}(a)=\mathcal{D}(-a)$, le PGCD de $a$ et $b$ est le même que celui de $|a|$ et de $|b|$.\\
On peut ainsi se restreindre aux entiers naturels.\\

\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textbf{}\textcolor{red}{Propriété :}}
\begin{enumerate}
\item Si $a$ divise $b$, alors pgcd$(a~;~b)=a$
\item \textbf{\textcolor{blue}{Propriété fondamentale :}} Soit $a$ non nul tel que $a=bq+r$. (division euclidienne de $a$ par $b$).\\
Alors : $\mathcal{D}(a)\cap\mathcal{D}(b)=\mathcal{D}(b)\cap\mathcal{D}(r)$ et pgcd$(a~;~b)$=pgcd$(b~;~r)$.
\end{enumerate}
\end{bclogo}

\textbf{\textcolor{red}{Démonstration :} :}\\
 \begin{enumerate}
\item Si $a$ divise $b$, tout diviseur de $a$ est un diviseur de $b$. Par conséquent : $\mathcal{D}(a)\cap\mathcal{D}(b)=\mathcal{D}(a)$ et le plus grand élément de $\mathcal{D}(a)$ est $a$.

\item Pour démontrer l'égalité des deux ensembles $E=\mathcal{D}(a)\cap\mathcal{D}(b)$ et $F=\mathcal{D}(b)\cap\mathcal{D}(r)$, on montre que $E$ est inclus dans $F$ et que $F$ est inclus dans $E$.\\
 $\bullet$ Soit $d\in E$. Alors $d$ divise $b$, donc $d$ divise $bq$ et comme $d$ divise $a$, $d$ divise $a-bq=r$, donc $d\in F$.\\
 $\bullet$ Soit $d\in F$. $d$ divise $b$ donc $bq$. Comme $d$ divise $r$, $d$ divise $bq+r=a$ donc $d\in E$.\\
 Les ensembles $E$ et $F$ sont égaux, donc ils ont le même plus grand élément. Ainsi : pgcd$(a~;~b)$=pgcd$(b~;~r)$.
\end{enumerate}

 \vspace{1cm}

\begin{enumerate}[Exerc\text{i}ce 1]

\item Déterminer le PGCD de 1960 et de 34300.\\
 On a : $\numprint{1960}=2^3\times5^1\times7^2$ et $\numprint{34300}=2^2\times5^2\times7^3$.\\
 On en déduit que PGCD$(1960~;~34300)=2^2\times 5^1\times 7^2=980$\\
 


\item Déterminer le PGCD de deux entiers dépendant de $n$:\\
 Déterminer, selon les valeurs de $n$,  le PGCD de $A=2n+1$ et de $B=n-5$.\\
 
\textbf{ \textcolor{red}{Méthode :}} on utilise la propriété  fondamentale.\\
 Pour éliminer $n$, on calcule $A-2B$. $A-2B=2n+1-2(n-5)=11$ donc $A=2B+11$.
 PGCD$(A~~;~~B)$=PGCD$(B~;~11)$. Comme 11 est un nombre premier, le PGCD de $B$ et de 11 ne peut valoir que 1 ou 11.\\
 PGCD$(B~;~11)=11$ si et seulement si 11 divise $B$.\\
 PGCD$(B~;~11)=11\Leftrightarrow B\equiv 0(11)\Leftrightarrow n-5\equiv 0(11)\Leftrightarrow n\equiv 5(11)$.\\
 On en conclut que le PGCD de $A$ et $B$ est 11 lorsque $n$ est congru à 5 modulo 11 et à 1 dans les autres cas.\\
 
\item  Égalité de deux PGCD :\\
Soient $a$ et $b$ deux entiers naturels non nuls. Soient $x=7a+5b$ et $y=4a+3b$. Montrer que le PGCD de $x$ et de $y$ est égal au PGCD de $a$ et de $b$.\\

\noindent \textbf{\textcolor{red}{Première méthode :}} $7a+5b=(4a+3b)+(3a+2b)$ donc pgcd$(7a+5b~;~4a+3b)$=pgcd$(4a+3b~;~3a+2b)$.\\
$3a+2b=2(a+b)+a$ donc pgcd$(4a+3b~;~3a+2b)$=pgcd$(a+b~;~a)$=pgcd$(a~;~b)$=pgcd$(a~;~b)$.\\
On en déduit que : pgcd$(x~;~y)$=pgcd$(a~;~b)$.\\

\noindent \textbf{\textcolor{red}{Deuxième méthode :}} Soit $d$ le PGCD de $a$ et $b$. Alors $d$ divise $a$ et $b$, donc $7a+5b$ et $4a+3b$ donc $d$ divise le PGCD $d'$ de $x$ et $y$.\\
Comme $d'$ divise $7a+5b$ et $4a+3b$, $d'$ divise $7(4a+3b)-4(7a+5b)=b$. De même, $d'$ divise $3(7a+5b)-5(4a+3b)=a$. Puisque $d'$ divise $a$ et $b$, il divise leur PGCD $d$.\\
$d$ divise $d'$ et $d'$ divise $d$. Donc $d=d'$.
\end{enumerate}

\subsection{\textcolor{red}{Détermination du PGCD par l'algorithme d'Euclide}}
(Cet algorithme, c'est-à-dire une suite d'instructions, fut décrit par Euclide au III\ième siècle avant JC)\\
\begin{bclogo}[couleur = cyan!10, arrondi = 0.1,logo=\bcfleur]{\textbf{}\textcolor{red}{Description de l'algorithme d'Euclide}}
Soient $a$ et $b$ deux entiers naturels non nuls, avec $a>b$.\\
On divise $a$ par $b$. $a=bq_1+r_1$, avec $0\leq r_1<b$.\\
Si $r_1=0$, alors pgcd$(a~;~b)=b$ puisque $b$ divise $a$.\\
Si $r_1\neq 0$, pgcd$(a~;~b)$=pgcd$(b~;~r_1)$. On effectue alors la division de  $b$ par $r_1$.\\
On a : $b=r_1q_2+r_2$, avec $0\leq r_2<r_1$.\\
Si $r_2=0$, alors pgcd$(a~;~b)$=pgcd$(b~;~r_1)=r_1$.\\
Si $r_2\neq 0$, pgcd$(b~;~r_1)$=pgcd$(r_1~;~r_2)$.\\
On continue la suite de divisions euclidiennes en divisant un reste par le reste suivant. On obtient une suite de restes $r_1$, $r_2$, \dots $r_n$, avec $r_1>r_2>r_3\dots\geq 0$. Comme ce sont des entiers, il existe un reste qui est nul. Notons $r_n$ le dernier reste non nul. Alors : pgcd$(a~;~b)$=pgcd$(b~;~r_1)$=pgcd$(r_1~;~r_2)$=\dots=pgcd$(r_{n-1}~;~r_n)=r_n$ car $r_n$ divise $r_{n-1}$
\end{bclogo}

\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textbf{\textcolor{red}{Propriété :}}}
Le PGCD de deux entiers non nuls $a$ et $b$ tels que $b$ ne divise pas $a$ est le dernier reste non nul de la suite des divisions de l'algorithme d'Euclide.
\end{bclogo}

\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textbf{\textcolor{red}{Corollaires :}}}
\begin{enumerate}
\item L'ensemble des diviseurs communs à deux entiers $a$ et $b$ est l'ensemble des diviseurs de leur PGCD.
\item Soit $a$ et $b$ deux entiers non nuls. Si $k$ est un entier naturel non nul, pgcd $(ka~;~kb)=k\times\text{ pgcd }(a~;~b)$.
\end{enumerate}
\end{bclogo}

\textbf{\textcolor{red}{Démonstration :} }

\begin{enumerate}
\item $\mathcal{D}(a)\cap\mathcal{D}(b)=\mathcal{D}(b)\cap\mathcal{D}(r_1)=\mathcal{D}(r_1)\cap\mathcal{D}(r_2)=\dots=\mathcal{D}(r_n)\cap\mathcal{D}(0)=\mathcal{D}(r_n)=\mathcal{D}(d)$ puisque $d=r_n$.
\item On note $d$ le PGCD de $a$ et $b$ et $d'$ celui de $ka$ et $kb$.\\
Comme $d$ divise $a$ et $b$, $kd$ divise $ka$ et $kb$, donc $kd$ divise leur PGCD $d'$, donc $kd$ divise $d'$.\\
$d'=k'(kd)$. ($k'$ entier)\\
$d'$ divise $ka$ et $kb$, donc $k'kd$ divise $ka$ et $kb$ ~;~ on en déduit que $k'd$ divise $a$ et $b$, donc leur PGCD $d$. $k'd$ divise $d$, donc $k'=1$ et $d'=kd$.
\end{enumerate}

\newpage
\subsection{\textcolor{red}{Entiers premiers entre eux}}
\begin{bclogo}[couleur = cyan!10, arrondi = 0.1,logo=\bcbook]{\textbf{}\textcolor{red}{Définition :}}
Deux entiers sont premiers entre eux lorsque leur PGCD est égal à 1.
\end{bclogo}

\textbf{\textcolor{red}{Remarques :}} \\
$\bullet$ Cela revient à dire que leurs seuls diviseurs sont -1 et 1.\\

$\bullet $ Il ne faut pas confondre nombre premiers et nombres premiers entre eux. Par exemple, 15 et 22 sont premiers entre eux, mais pas premiers.\\

\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textbf{\textcolor{red}{Propriété :}}}
Soient $a$ et $b$ des naturels non nuls et $d$ un diviseur commun de $a$ et $b$. On pose $a=da'$ et $b=db'$.\\
Le PGCD de $a$ et $b$ est $d$ si et seulement si $a'$ et $b'$ sont premiers entre eux.
\end{bclogo}

\textcolor{red}{Démonstration :} :\\
$\bullet$ Si $d$ est le PGCD de $a$ et $b$, soit $a=da'$ et $b=db'$. On en déduit que :\\
$d$=pgcd$(a~;~b)$=pgcd$(da'~;~db')$=d pgcd$(a'~;~b')$. Comme $d$ est non nul, pgcd$(a'~;~b')=1$ et $a'$ et $b'$ sont premiers entre eux.\\

$\bullet$ Si pgcd$(a'~;~b')=1$, alors pgcd$(a~;~b)=d$ pgcd$(a'~;~b')=d$\\\\


\begin{enumerate}[Exerc\text{i}ce 1]
\item  Déterminer le PGCD de \numprint{8870} et de \numprint{3120}.\\

\textbf{\textcolor{blue}{Réponse :}} on utilise l'algorithme d'Euclide : on trouve un PGCD égal à 10.\\

\item Écrire l'algorithme d'Euclide pour une calculatrice.\\
\textcolor{red}{Solution :}\\
\begin{itemize}
\item Entrer $a$ et $b$
\item Tant que $b\neq 0$ (début de la boucle)
\item $E\left(\frac{a}{b}\right)\rightarrow q$
\item $a-bq\rightarrow r$
\item $b\rightarrow a$ Le nouveau dividende est $b$. 
\item $r\rightarrow b$ (Le nouveau diviseur est $r$)
\item Fin Tant que 
\item Afficher $a$ (C'est le dernier reste non nul, donc le PGCD cherché)
\end{itemize}



\item  Déterminer les naturels dont la somme est \numprint{600} et dont le PGCD est 50.\\

\noindent \textcolor{red}{Solution :}\\
On cherche $a$ et $b$ tels que : $a+b=600$ et pgcd$(a~;~b)=50$.\\
Soient $a'$ et $b'$ les entiers tels que : $a=50a'$ et $b=50b'$ ~;~ alors $a'$ et $b'$ sont premiers entre eux.\\
$a+b=600\Leftrightarrow 50a'+50b'=600\Leftrightarrow 50(a'+b')=600\Leftrightarrow a'+b'=12$.\\
On cherche tous les couples d'entiers naturels vérifiant cette relation et on ne garde que les couples d'entiers premiers entre eux. $(1~;~11)$ ~;~ $(5~;~7)$ ~;~ $(7~;~5)$ et $(11~;~1)$.\\
On en déduit les couples solutions : $(50~;~150)$ ~;~ $(250~;~350)$ ~;~ $(350~;~250)$ et $(550~;~50)$.\\
\end{enumerate}

\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textbf{}\textcolor{red}{Théorème de Bézout :}}
Deux entiers $a$ et $b$ sont premiers entre eux si, et seulement si, il existe deux entiers relatifs $u$ et $v$ tels que $au+bv=1$.
\end{bclogo}

\textbf{\textcolor{red}{Démonstration :} :}\\

\begin{enumerate}[$\bullet$]
\item On suppose $a$ et $b$ premiers entre eux, donc pgcd$(a~;~b)=1$. L'un des deux nombres est non nul, par exemple $a$.

\item On considère l'ensemble des nombres entiers de la forme $au+bv$, avec $u$ et $v$ entiers.\\Cet ensemble n'est pas vide, puisqu'il contient par exemple $a$, (avec $u=1$ et $v=0$).

\item Si E contient $a$, il contient $-a$ et l'un de ces deux entiers est positifs, donc E contient un entier positif.

\item Soit $\beta$ le plus petit de ces entiers positifs de E. ~;~ il existe $u_0$ et $v_0$ tels que : $\beta=au_0+bv_0$.

\item La division euclidienne de $a$ par $\beta$ s'écrit : $a=\beta q+r$, avec $0\leq r<\beta$ d'où \\
$r=a-\beta q=a-(au_0+bv_0)q=a(1-u_0q)+b(-v_0q)$. Ainsi, $r$ appartient à E puisqu'il est de la forme $au+bv$ avec $u$ et $v$ entiers. \\
Par définition de $\beta$ qui est le plus petit entier positif de E, on a : $r=0$.\\
On en déduit : $a=\beta q$, donc $\beta$ divise $a$.

\item On montre de même que $\beta$ divise $b$, donc $\beta=1$ puisque le PGCD de $a$ et de $b$ est 1. Par conséquent, il existe bien deux entiers $u_0$ et $v_0$ tels que $au_0+bv_0=1$.
\end{enumerate}


\textbf{\textcolor{red}{Réciproque :}}\\
S'il existe des entiers $u$ et $v$ tels que $au+bv=1$, alors, si $d$ est le PGCD de $a$ et $b$, il divise $a$ et $b$, donc $au+bv$ donc 1 ~;~ par conséquent, $d=1$ et $a$ et $b$ sont premiers entre eux.\\\\

\textbf{\textcolor{blue}{Exemples :}}
\begin{enumerate}
\item  5 et 12 sont premiers entre eux car $7\times (-5)+3\times 12=1$.
\item $(n+1)-n=1$ donc $n$ et $n+1$ sont toujours premiers entre eux.\\\\
\end{enumerate}

\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textbf{}\textcolor{red}{Corollaire}}
Si $d$ est le PGCD de deux entiers $a$ et $b$, alors il existe des entiers $u$ et $v$ tels que $au+bv=d$.
\end{bclogo}

\textcolor{red}{Démonstration :} : \\
$a=da'$ et $b=db'$ où $a'$ et $b'$ sont premiers entre eux. On applique alors le \textbf{théorème de Bézout}.\\

\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textbf{}\textcolor{red}{Propriété :}}
Un nombre premier est premier avec tous les nombres qu'il ne divise pas.
\end{bclogo}

\textcolor{red}{Démonstration :} : Soit $p$ un nombre premier. Soit $a$ un entier non divisible par $p$. On note $d$ le PGCD de $p$ et $a$. $d$ vaut 1 ou $p$, puisque $p$ est premier.\\
$d$ ne peut pas être égal à $p$, sinon $p$ diviserait $a$.\\
Par conséquent : $d=1$.\\

\fbox{\textbf{\textcolor{red}{Exercice fondamental :}}}\\
Montrer que les nombres \numprint{3920} et \numprint{1089}sont premiers entre eux et déterminer des entiers $u$ et $v$ tels que \\
$3920u+1089v=1$.\\

\textbf{\textcolor{red}{Méthode :}} on écrit toutes les divisions de l'algorithme d'Euclide ~;~ on reporte alors chaque reste obtenu en partant de la fin.\\
On obtient :\\
$3920=1089\times 3+653$\\
$1089=653\times 1+436$\\
$653=436\times 1+217$\\
$436=217\times 2+2$\\
$217=2\times 108+1$\\
$2=1\times 2+1$\\
Par conséquent : le dernier reste non nul est 1, donc les deux nombres sont premiers entre eux.\\
On a alors : \\
$\bullet$ $217-2\times 108=1$ (1)\\
$\bullet$ $2=436-217\times 2$ donc en reportant dans (1) :\\
$217-(436-217\times 2)\times 108=1$ d'où $217\times 217-436\times 108=1$ (2)\\
$\bullet$ $217=653-436\times 1$. On remplace dans (2) :\\
$(653-436\times 1)\times 217-436\times 108=1$ d'où $653\times 217-436\times 325=1$ (3)\\
$\bullet$  $436=1089-653$. On remplace dans (3) :\\
$653\times 217-(1089-653)\times 325=1$ d'où $653\times 542-1089\times 325=1$ (4)\\
$\bullet$ $653=3920-1089\times 3$. On remplace dans (4) : \\
$(3920-1089\times 3)\times 542-1089\times 325=1$ soit : $3920\times 542-1089\times 1951=1$.\\

\begin{minipage}{14cm}
\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textbf{}\textcolor{red}{Propriété :}}
Si un entier est premier avec deux entiers, il est entier avec leur produit.
\end{bclogo}
\end{minipage}\\

\textbf{\textcolor{red}{Démonstration :}}\\
Soit $a$ un entier premier avec $b$ et $c$. D'après le théorème de Bézout, il existe deux entiers $u$ et $v$ tels que $au+bv=1$ et des entiers $u'$ et $v'$ tels que $au'+cv'1$.\\
On effectue le produit membre à membre. On obtient : \\
$(au+bv)(au'+cv')=1\Leftrightarrow a^2uu'+acuv'+abvu'+bcvv'=1\Leftrightarrow a(auu'+cuv'+bvu')+bc(vv')=1$. Comme $auu'+cuv'+bvu'$ et $vv'$ sont des entiers, on en déduit que $a$ et $bc$ sont premiers entre eux.\\

\textbf{\textcolor{blue}{Exemples : }}
\begin{enumerate}
\item 4 est premier avec 9 et avec 35, donc 4 est premier avec 315.
\item Pour tout $n$, $n$ est premier avec $n+1$ et avec $n-1$, donc $n$ est premier avec $n^2-1$.
\end{enumerate}

\subsection{\textcolor{red}{Théorème de Gauss et applications :}}
\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textbf{}\textcolor{red}{Théorème}}
Soient $a$, $b$ et $c$ trois entiers. Si $a$ divise le produit $bc$ et si $a$ est premier avec $b$, alors $a$ divise $c$.
\end{bclogo}

\textbf{\textcolor{red}{Démonstration :} :}\\
Si $a$ est premier avec $b$, il existe $u$ et $v$ tels que : $au+bv=1$. On en déduit : $acu+bcv=c$.\\
Or, $a$ divise $acu$ et $bc$ par hypothèse, donc $a$ divise $c$.\\

\textbf{\textcolor{blue}{Exemple :}} Soient $a$ et $b$ deux entiers tels que $5a=14b$. 14 divise le produit $5a$, les entiers 14 et 5 sont premiers entre eux, donc 14 divise $a$.\\
De même, 5 divise $b$.\\

\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textbf{}\textcolor{red}{Corollaires :}}
\begin{enumerate}
\item Si un entier est divisible par des entiers $a$ et $b$ premiers entre eux, alors il est divisible par leur produit $ab$.
\item Si un entier premier divise un produit de facteurs $ab$, alors il divise au moins un des facteurs $a$ et $b$.
\end{enumerate}
\end{bclogo}

\textbf{\textcolor{red}{Démonstration :} :}\\
\begin{enumerate}
\item Soit $n$ entier divisible par $a$ et $b$. Il existe des entiers $k$ et $k'$ tels que $n=ka$ et $n=k'b$ donc $n=ka=k'b$.\\
$a$ divise donc $k'b$. Comme $a$ et $b$ sont premiers entre eux, on en déduit (d'après le théorème de Gauss) que $a$ divise $k'$ donc il existe $q$ tel que $k'=qa$. On a alors $n=qab$ et $n$ est divisible par $ab$.
\item Soit $p$ un nombre premier divisant $ab$. \\
Si $p$ divise $a$, alors la condition est vérifiée.\\
Supposons que $p$ ne divise pas $a$. Alors $a$ et $p$ sont premiers entre eux~;~ comme $p$ divise $ab$, alors $p$ divise $b$ d'après le théorème de Gauss.
\end{enumerate}

\textbf{\textcolor{blue}{Exercices :}}
\begin{enumerate}
\item Résoudre une équation du type $ax+by=0$ dans $\mathbb{Z}^2$.\\
\textbf{\textcolor{blue}{Exemple :}} Déterminer les entiers $x$ et $y$ tels que $7x+5y=0$.\\
Cette équation s'écrit $7x=-5y$. $7$ et $-5$ sont premiers entre eux. 7 divise $-5y$ donc 7 divise $y$ d'après le théorème  de Gauss. Ainsi $y=7k$ avec $k$ entier.\\
En reportant : $7x=-5\times 7k$ d'où $x=-5k$.\\
Les solutions sont les couples $(-5k~;~7k)$ où $k\in\mathbb{Z}$.

\item Résoudre une équation du type $ax+by=c$ dans $\mathbb{Z}^2$, avec $a$ et $b$ premiers entre eux.\\
\begin{enumerate}
\item \textbf{\textcolor{blue}{Exemple :}} Déterminer les entiers $x$ et $y$ tels que $5x+7y=1$\\
Comme 5 et 7 sont premiers entre eux, il existe d'après le théorème de Bezout deux nombres $u$ et $v$ tels que : $5u+7v=1$. Pour déterminer $u$ et $v$, on peut utiliser l'algorithme d'Euclide ou remarquer que $5\times 10-7\times 7=1$ donc on peut prendre $u=10$ et $v=-7$. Le couple $(10~;~-7)$ est une solution particulière de cette équation.\\
Alors : $5x+7y=1\Leftrightarrow 5x+7y=5\times 10-7\times 7\Leftrightarrow 5(x-10)=7(-y-7)$.\\
5 divise $7(-y-7)$~;~ 5 et 7 sont premiers entre eux. D'après le théorème de Gauss, on en déduit que 5 divise $-y-7$. Par conséquent : $-y-7=5k$, $k\in\mathbb{Z}$, donc $y=-7-5k$.\\
On reporte dans l'équation $5(x-10)=7(-y-7)$. On obtient : $5(x-10)=7\times 5k$ d'où $x-10=7k$ soit $x=10+7k$.\\
Les solutions sont de la forme $(10+7k~;~-7-5k)$, $k\in\mathbb{Z}$.

\item Déterminer les entiers $x$ et $y$ tels que $5x+7y=3$.\\
Comme $5\times 10-7\times 7=1$, on a $5\times 30-7\times 21=3$. Ainsi, $(30~;~-21)$ est une solution particulière de cette équation.\\
On trouve alors les solutions en utilisant la même méthode que ci-dessus.\\
Les couples solutions sont $(30+7k~;~-21-5k)$.
\end{enumerate}

\item Montrer la divisibilité par un produit d'entiers.\\
Exemple : Montrer que $A=n(n+1)(n+2)$ est divisible par 6 pour tout $n$ entier.\\
$n(n+1)$ est divisible par 2 ~;~ $n(n+1)(n+2)$ est divisible par 3, car il y a toujours un multiple de 3 parmi trois nombres consécutifs.\\
$A$ est divisible par 2 et par 3, donc divisible par 6 car 2 et 3 sont premiers entre eux.
\end{enumerate}


\subsection{\textcolor{red}{Petit théorème de Fermat}}
\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textcolor{red}{Petit théorème de Fermat}}
$p$ est un nombre premier, $a$ est un entier tel que $a\geqslant 2$ et non divisible par $p$. \\
Alors $a^{p-l} - 1$ est divisible par $p$, c'est-à-dire $a^{p-1}\equiv 1$ (mod $p$).
\end{bclogo}

\textbf{\textcolor{red}{Démonstration :}}\\
$p$ est un nombre premier, donc $p$ est premier avec 1, 2, \dots, $p - 1$ (sinon $p$ admettrait un diviseur positif autre que 1) et donc premier avec $(p - 1)!$\\
\begin{enumerate}[$\bullet$]
\item Si $k$ est un entier tel que $1\leqslant  k\leqslant  p - 1$ , alors le reste $r_{k}$ de la division de $ka$ par $p$ est non nul.\\
En effet, si $p$ divise $ka$, alors $p$ divise $a$ car $p$ est premier avec $k$ ;\\
or ceci est impossible car par hypothèse, $a$ n'est pas divisible par $p$.

\item Si $k'$ est un entier distinct de $k$ (par exemple $k < k'$) tel que $1\leqslant  k'\leqslant  p - 1$, alors les restes $r_{k'}$ et $r_{k}$ des divisions respectives de $k' a$ et $ka$ par $p$ sont distincts.\\
En effet, si $r_{k'} = r_{k}$, alors $p$ divise $k'a - ka$ c'est-à-dire $(k' - k)a$ avec $1\leqslant  k' -k\leqslant  p - 1$, ce qui est impossible car $a$ n'est pas divisible par $p$.

\item  Ainsi, les $p - 1$ restes $r_{1}$, $r_{2}$,\dots, $r_{p- 1}$ des divisions respectives de $a$, $2a$, \dots, $(p - l)a$ par $p$ sont donc des entiers naturels non nuls, strictement inférieurs à $p$ et tous distincts.\\
Donc l'un de ces restes est égal à 1, l'autre à 2, ..., l'autre à $p - 1$.\\
D'où en utilisant le produit des congruences :\\
$a\times 2a\times \cdots\times (p - 1)a \equiv r_{1} r_{2}\cdots r_{p-1}$ (mod $p$) c'est-à- dire $(p - 1)!a^{p-1}\equiv (p - 1)!$ (mod $p$ ).\\
Donc $p$ divise $(p - 1)! a^{p-1} - (p -1)!$ c'est-à-dire $(p - 1)! \left(a^{p-1} - 1\right)$.\\
Or $p$ est premier avec $(p - l)!$, donc $p$ divise $a^{p-1} - 1$ d'après le théorème de Gauss.
\end{enumerate}

\textbf{\textcolor{blue}{EXEMPLE}} 7 est premier et ne divise pas 12, donc $12^6 - 1$ est divisible par 7.\\

\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textcolor{red}{Conséquence}}
$p$ est un nombre premier, $a$ est un entier supérieur ou égal à 2.\\
Alors $a^p - a$ est divisible par $p$ c'est-à-dire $a^p \equiv a$ (mod  $p$).
\end{bclogo}

\textbf{\textcolor{red}{DÉMONSTRATION}}\\
$a^p - a = a(a^{p-1} - 1)$.\\
\begin{enumerate}[$\bullet$]
\item Si $a$ est divisible par $p$, alors $a(a^{p- 1} - 1)$ est divisible par $p$.

\item Si $a$ n' est pas divisible par $p$, alors, d'après le petit théorème de Fermat, $a^{p- 1} - 1$ est divisible par $p$ et donc $a(a^{p-l} - 1)$ est divisible par $p$. 
\end{enumerate}

\subsection{\textcolor{red}{Plus petit commun multiple de deux entiers}}
Étant donné un naturel $a$, notons $\mathscr{M}(a)$ l'ensemble des multiples de $a$ strictement positifs.\\

\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textbf{}\textcolor{red}{Définition}}
Le plus petit commun multiple des naturels non nuls $a$ et $b$ est le plus petit élément de $\mathscr{M}(a)\cap\mathscr{M}(b)$, ensemble des multiples communs strictement positifs de $a$ et de $b$. On l'appelle aussi PPCM de $a$ et de $b$.
\end{bclogo}

\textbf{\textcolor{blue}{Remarques :}}\\
Le PPCM de deux entiers naturels non nuls est un entier au moins égal à 1.\\
PPCM$(a~;~a)=a$ ~;~ PPCM$(1~;~a)=a$.\\
Le seul multiple de 0 est 0, onc PPCM$(a~;~0)=0$.\\
Le PPCM de deux entiers quelconques est celui de leurs valeurs absolues.\\

\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textbf{}\textcolor{red}{Propriété :}}
Soient $a$ et $b$ deux entiers au moins égaux à 2. Le PPCM de $a$ et $b$ est égal au produit de tous les facteurs premiers de $a$ et de tous ceux de $b$, avec pour chacun d'eux l'exposant le plus grand de ceux qu'il a dans la décomposition de $a$ et de $b$.
\end{bclogo}

\textbf{\textcolor{red}{Démonstration :}} \\
Soit $m$ le PPCM de deux naturels $a$ et $b$ supérieurs ou égaux à 2. Comme $m$ est un multiple de $a$, sa décomposition en facteurs premiers comprend tous les facteurs premiers de $a$ avec un exposant au moins égal à celui qu(ils ont dans la décomposition de $a$ ~;~ de même, elle comprend tous les facteurs premiers de $b$ avec un exposant au moins égal à celui qu'ils ont dans la décomposition de $b$.\\
Ainsi, $m$ comprend tous les facteurs premiers de $a$ et tous ceux de $b$, avec un exposant au mois égal à au plus grand de ceux qu'il a dans $a$ et dans $b$.\\\\

\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textbf{}\textcolor{red}{Propriété}}
\begin{enumerate}
\item L'ensemble des multiples communs de $a$ et de $b$ est l'ensemble des multiples de leur PPCM.
\item Soient $a$ et $b$ deux entiers naturels : PPCM$(a~;~b)\times$ PGCD$(a~;~b)=ab$
\end{enumerate}
\end{bclogo}

\vspace{0,5cm}
\textbf{\textcolor{red}{Démonstration :}}\\
On suppose $a$ et $b$ non nuls. Soit $d$ le PGCD de $a$ et $b$ : il existe des entiers $a'$ et $b'$ premiers entre eutels que $a=da'$ et $b=db'$.\\
Soit $\mu$ un multiple commun de $a$ et $b$ : il existe alors des entiers $k$ et $k'$ tels que $\mu=ka$ et $\mu=k'b$. D'où : $kda'=k'db'$. Comme $d$ est non nul, on obtient $ka'=k'b'$.  Puisque $a'$ divise $k'b'$ et que $a'$ et $b'$ sont premiers entre eux, $a'$ divise $k'$ d'après le théorème de Gauss. IL existe ainsi un entier $q$ tel que $k'=qa'$.\\
On en déduit : $\mu=qa'b=qda'b'$.\\
Ainsi, tout multiple comun $\mu$ à $a$ et $b$ est un multiple de $sa'b'$ : le plus petit de ces multiples communs $m$ est obtenu pour $q=1$., ce qui fournit  = $m=da'b'$.\\
D'où : $md=(da')(db')=ab$.\\
Si $a$ et nul et $b$ non nul, l'égalité est vérifiée car $d=b$ et $m=0$.\\

\noindent \textbf{Exemple :}\textcolor{blue}{} \\
Le PGCD de 42 et 60 est 6. Si on note $m$ leur PPCM, alors $6m=42\times 60$ d'où $m=420$.\\

\begin{minipage}{14cm}
\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textbf{}\textcolor{red}{Propriété :}}
 Si $k$ est un entier naturel, PPCM $(ka~;~kb)=k\times \text{PPCM }(a~;~b)$.
\end{bclogo}
\end{minipage}

\textbf{\textcolor{blue}{Exercices :}}
\begin{enumerate}
\item Déterminer le PPCM de 240 et de 756.
\item Déterminer le PPCM de \numprint{44100} et de \numprint{36036}.
\end{enumerate}
\vspace{0,5cm}
\textbf{\textcolor{red}{Solution}}\\
\begin{enumerate}
\item On utilise la décomposition en facteurs premiers.
\item On détermine le PGCD de ces deux entiers avec l'algorithme d'Euclide.\\
Le PGCD est 252. ON a alors $252m=\numprint{44100}\times\numprint{36036}$.
\end{enumerate}


\textbf{\textcolor{red}{Équations faisant intervenir le PPCM :}}\\
\begin{enumerate}
\item Déterminer deux entiers naturels $a$ et $b$ connaissant leur produit \numprint{1512} et leur PPCM \numprint{252}.
\item Soient $d$ et $m$ le PGCD et le PPCM de deux naturels $a$ et $b$? Déterminer $a$ et $b$ tels que $m-2d=11$.
\end{enumerate}
\vspace{1cm}
\textbf{\textcolor{red}{Solutions}}\\
\begin{enumerate}
\item $ab=\numprint{1512}$. Notons $d$ leur PGCD. On a $252d=ab$ d'où $d=6$.\\
Or $a=da'$ et $b=db'$, avec $a'$ et $b'$ premiers entre eux. De plus $35a'b'=\numprint{1512}$ d'où $a'b'=42$. Comme $a'$ et $b'$ sont premiers entre eux, le couple $(a',b')$ peut être égal à :\\
$(1~;~42), (2~;~21), (3.14), (6.7), (7~;~6), (14,3), (21~;~2), (42~;~1)$.\\
On multiplie par 6 pour avoir tous les couples solutions.
\item $a=da'$ et $b=db'$, $a'$ et $b'$ premiers entre eux.\\
Comme $md=ab$, on a $md=d^2a'b'$ d'où $m=da'b'$.\\
La relation donnée s'écrit : $da'b'-2d=11$, soit $d(a'b'-2)=11$.\\
Ainsi, $d$ divise 11 et $d$ est positif, donc $d=11$ ou $d=1$.\\
Si $d=11$, alors $a'b'-2=1$ donc $a'b'=3$. $(a'~;~b')=(1~;~3)$ ou $(3~;~1)$ et $(a~;~b)=(11~;~33)$ ou $(33~;~11)$.\\\\
Si $d=1$, alors $a'b'=13$ d'où $(a'~;~b')=(1~;~13)$ ou $(13~;~1)$. Alors $(a~;~b)=(13~;~1)$ ou $(1~;~13)$.
Ainsi, il y a quatre couples solutions.
\end{enumerate}

\begin{minipage}{14cm}
\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textbf{}\textcolor{red}{Propriété :}}
 Si $k$ est un entier naturel : ppcm$(ka~;~kb)=k\times \text{PPCM }(a~;~b)$.
\end{bclogo}
\end{minipage}

\textbf{\textcolor{blue}{Démonstration :}}\\
Si $k$, $a$ ou $b$ est nul, c'est évident.\\
Si $a$, $b$ ou $k$ sont non nuls : ppcm$(ka~;~kb)\times $pgcd$(ka~;~kb)=ka\times kb$ ~;~ or pgcd$(ka~;~kb)=k\times \text{ pgcd }(a~;~b)$.



\label{fin}
\end{document} 



  		