\documentclass[12pt]{book}\usepackage{aymar}\begin{document}\couleur

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



\chapitre{3}{Nombres premiers entre eux, théorèmes de Bézout et Gauss}{Ts spé}

\begin{minipage}{16cm}
\tableofcontents
\end{minipage}


\begin{center}Voir les compléments et la video de Gilles Horweck\end{center}

\newpage
\section{Nombres premiers entre eux}

\subsection{Définition}

\defi{Soient $a$ et $b$ deux entiers relatifs. On dit que $a$ et $b$ sont
{\em premiers entre eux} si leur PGCD est égal à 1.
On note alors $a\wedge b=1$.}



\subsection{Théorème de Bézout}

\theo{Soient $a$ et $b$ deux entiers positifs non nuls. \\
$a$ et $b$ sont premiers entre eux si et seulement si il existe $u$ et $v$ dans $\Z$ tels que $au+bv=1$.
}

\dem{Soit $d$ le PGCD de $a$ et $b$.
\begin{description}
\item[($\Leftarrow$)]  On suppose qu'il existe $u$ et $v$ dans $\Z$ tels que $au+bv=1$. Par linéarité, $d$ divise $a$ et $b$ donc par linéarité, $d$ divise $1$. Donc $1\leq d\leq 1$, ce qui implique $d=1$.
Les entiers $a$ et $b$ sont bien premiers entre eux.
\item[($\Rightarrow$)]   On suppose que $a$ et $b$ sont premiers entre eux.
	\begin{itemize}
	\itemb Posons ${\cal E}=\{ax+by|x,y\in\Z\}\cap\N$ (c'est l'ensemble des combinaisons linéaires positives de $a$ et $b$).
	$\cal E$ est minoré par $0$ et $a=a\times1+b\times0$ donc $a\in\cal E$ et donc $\cal E$ n'est pas vide. Il contient par conséquent un plus petit élément non nul $m$ de la forme $au+bv$.
	\itemb Selon la division euclidienne de $a$ par $m$, 
	il existe $q$ et $r$ dans $\Z$ tels que $a=mq+r$ et $0\leq
	r<m$. Mais $a=mq+r$ implique $r=a-mq=a-(au+bv)q=a(1-uq)+bvq$. Donc
	$r$ est  élément de $\cal E$ inférieur à $m$. Par définition, $m$ est le plus petit
	élément non nul de $\cal E$, donc $r=0$. Par conséquent $m$ divise $a$.
	\itemb On démontre de la même façon que $m$ divise $b$.
	\itemb Donc $m$ diviseur commun à $a$ et $b$, et donc $0<m\leq d=1$ donc $m=1$.
	On en déduit que $au+bv=1$.\end{itemize}
\end{description}}


\subsection{Quelques propriétés}

\prop{}{Soient $a$ et $b$ deux entiers positifs. Le PGCD $d$ de $a$ et
$b$ est l'unique diviseur commun à $a$ et $b$ tel que $\frac{a}{d}$
et $\frac{b}{d}$ soient premiers entre eux.}

\dem{\begin{itemize}
\item[($\Rightarrow$)]  Soit $d=a\wedge b$. Alors $\frac{a}{d}$ et $\frac{b}{d}$ sont
des entiers. Soit $e$ leur PGCD. Il existe deux entiers $k$ et $k'$
tels que $\frac{a}{d}=ke$ et $\frac{b}{d}=k'e$. En multipliant ces
deux égalités par $d$, on trouve que $a=ked$ et $b=k'ed$. Donc $ed$
est un diviseur commun de $a$ et $b$, ce qui implique $ed\leq d$ par
définition de $d$. Donc $e=1$, $\frac{a}{d}$ et $\frac{b}{d}$ sont
premiers entre eux.
\item[($\Leftarrow$)] Soit $g$ un diviseur commun à $a$ et $b$ tel que 
$\frac{a}{g}$ et $\frac{b}{g}$ soient premiers entre eux et 
$d$ le PGCD de $a$ et $b$. Alors $g\leq d$. D'après le
théorème de Bézout, il existe $u$ et $v$ dans $\Z$ tels que
$\frac{a}{g}u+\frac{b}{g}v=1$. En multipliant par $g$, on en déduit
que $au+bv=g$. Comme $d$ divise $a$ et $b$, il divise aussi $au+bv=g$, et
donc $d\leq g$.  La seule possibilité est alors $d=g$, et $g$ est
bien le PGCD de $a$ et $b$.                           \end{itemize}
}

\prop{}{Soient $a$ et $b$ deux entiers positifs. Le PGCD $d$ de $a$ et
$b$ est l'unique diviseur commun à $a$ et $b$ tel qu'il existe $u$
et $v$ dans $\Z$ vérifiant $au+bv=d$.}

\dem{D'après la propriété précédente, $d$ est l'unique diviseur
commun de $a$ et $b$ tel que $\frac{a}{d}$ et $\frac{b}{d}$ soient
premiers entre eux. D'après le théorème de Bézout, c'est donc
l'unique diviseur commun de $a$ et $b$ tel qu'il existe $u$ et $v$
dans $\Z$ vérifiant $\frac{a}{d}u+\frac{b}{d}v=1$, c'est à dire
$au+bv=d$.}

\rems{\begin{itemize}
\item 
$a=12$ et $b=18$. $\pgcd(a,b)=6$. $6$ est l'unique diviseur commun
à $12$ et $18$, tel que l'équation $12u+18v=6$ admette des solutions dans $\Z$.
$3$ est un autre diviseur commun, mais l'équation $12u+18v=3$ n'admet pas de solution dans $\Z$.
(seulement dans $\Q$).
\item L'algorithme d'Euclide permet de trouver les entiers $u$ et $v$
de la propriété précédente. En effet, puisque :
\begin{eqnarray}
342 & = & 276\times 1+66 \nonumber\\
276 & = & 66\times 4 +12 \nonumber\\
66 & = & 12\times 5 +6 \nonumber\\
12 & = & 6\times 2 +0 \nonumber
\end{eqnarray}
en écrivant les restes successifs en fonction  de 342 et 276, on obtient que
\begin{eqnarray}
66 & = & 342 +276\times(-1) \nonumber\\[5pt]
12 & = & 276 - 66\times 4  \nonumber\\
     & = & 276 - (342+ 276\times(-1))\times 4  \nonumber\\
     & = & 342\times(-4)+276\times(5)  \nonumber\\[5pt]
6 & = & 66-12\times 5 \nonumber\\
   & = & (342 +276\times(-1))-(342\times(-4)+276\times(5))\times 5 \nonumber\\
   & = & 342\times 21+276\times(-26)\nonumber
\end{eqnarray}
Les entiers cherchés sont donc $u=21$ et $v=-26$.
\end{itemize}
}

\prop{}{Soient $a$, $b$ et $c$ trois entiers positifs. Si $d$ est le
PGCD de $a$ et $b$, alors $dc$ est le PGCD de $ac$ et $bc$.}

\dem{D'après la propriété précédente, si $d$ est le PGCD de $a$ et
$b$ il existe $u$ et $v$ dans $\Z$ tels que $au+bv=d$. On en déduit
que $(ac)u+(bc)v=dc$. Comme $dc$ est un diviseur de $ac$ et $bc$, en
appliquant la propriété précédente, $dc$ est bien le PGCD de $ac$
et $bc$.}

\section{Théorème de Gauss}

\theo{Soient $a$, $b$, $c$ trois entiers positifs non nuls tels
que $a$ divise le produit $bc$. Si $a$ est premier avec $b$, alors
il divise $c$.}

\dem{Supposons que $a$ divise le produit $bc$ et soit premier avec
$b$. D'après le théorème de Bézout, puisque $a$ et $b$ sont premiers
entre eux, il existe $u$ et $v$ dans $\Z$ tels que $au+bv=1$. Donc
$acu+bcv=c$. Puisque $a$ divise $bc$, il divise aussi $bcv$ et
$acu+bcv$. On en déduit que $a$ divise $c$.}

\rem{$4$ divise $60=6\times10$ mais $4$ ne divise ni $6$, ni $10$. 
L'hypothèse $a$ est premier avec $b$ est nécessaire.}

\prop{}{Soit $a$ un entier divisible par deux entiers $b$ et $c$. Si
$b$ et $c$ sont premiers entre eux, alors $a$ est divisible par le produit $bc$.}

\dem{Par définition, il existe $k$ et $k'$ dans $\Z$ tels que
$a=bk=ck'$. Donc $c$ divise $bk$. Si $b$ et $c$ sont premiers entre
eux, d'après le théorème de Gauss, $c$ divise $k$, et donc il existe
$k''$ dans $\Z$ tel que $k=ck''$. Alors $a=bck''$, et donc $a$ est
divisible par le produit $bc$.}

\rems{\begin{itemize}
\item $12$ est divisible par $4$ et par $2$, mais n'est pas divisible par $4\times2$. 
\item Ce résultat s'étend au cas où un nombre $a$ est divisible par
plus de deux entiers premiers entre eux deux à deux. 
 \end{itemize}}

\theo{Soient $p$ un nombre premier et $n$ un entier non divisible
par $p$. Les nombres $p$ et $n$ sont premiers entre eux.}

\dem{Puisque $p$ est premier ${\cal D}(p)=\{1,p\}$. Comme $n$ n'est
pas divisible par $p$, $p\not\in{\cal D}(n)$. Par contre, $1\in{\cal
D}(n)$, et donc ${\cal D}(n)\cap{\cal D}(p)={1}$. Le PGCD de $p$ et
$n$ est 1, c'est à dire $p$ et $n$ sont premiers entre eux.}

\theo{Soient $p$ un nombre premier, $a$ et $b$ deux entiers
naturels. Si $p$ divise $ab$ alors soit $p$ divise $a$, soit $p$
divise $b$.}

\dem{Si $p$ divise $a$, la propriété est vraie. Si $p$ ne divise pas
$a$, d'après le théorème précédent, $p$ est premier avec $a$. Or il
divise le produit $ab$ et donc, d'après le théorème de Gauss, il
divise $b$.}

\rem{Ce théorème admet quelques cas particuliers intéressants. Par
exemple, si un nombre premier $p$ divise $a^2$, alors il divise $a$,
et s'il divise un produit de nombres premiers $qq'$, alors $p=q$ ou
$p=q'$.}


\section{Résoudre des équations diophantiennes}

\defi{L'équation à deux inconnues entières $x$ et $y$ $$ax+by=c\ (E)$$  où $a$, $b$ et $c$ sont des entiers relatifs
donnés est une \emph{équation diophantienne}.}


\prop{}{D'après la généralisation du théorème de Bézout vue
précédemment, l'équation $(E)$ admet une infinité de solutions si et
seulement si $c$ est un multiple du PGCD de $a$ et $b$. C'est en
particulier le cas pour toute valeur de $c$ quand $a$ et $b$ sont
premiers entre eux. La méthode pour les déterminer utilise
l'algorithme d'Euclide, le théorème de Bézout et le théorème de
Gauss.}



\emph{Trouver tous les couples d'entiers $u$ et $v$ tels que $21u+10v=1 (E)$ .}


Pour résoudre ce problème, nous allons d'abord vérifier si cette
équation admet des solutions. Si c'est le cas, on trouvera une
solution particulière en appliquant l'algorithme d'Euclide. On
pourra alors en déduire toutes les solutions du problème.

\bigskip\par
Déterminons tout d'abord le PGCD de 21 et 10 en utilisant
l'algorithme d'Euclide :
    \begin{eqnarray*}
        21 & = & 10\times 2+1 \\
        10 & = & 1\times 10+0
    \end{eqnarray*}
Donc le PGCD de 21 et 10 est 1 (le dernier reste non nul), ils sont
donc premiers entre eux, ce qui prouve que l'équation admet une
infinité de solutions entières.\\[5pt] 

Les étapes de l'algorithme permettent de trouver une solution particulière de $(E)$. La
première égalité donne $1=21-10\times 2$, ce qui montre que $u_0=1$
et $v_0=-2$ conviennent.\\[5pt]

Soit $(u;v)$ une solution quelconque de l'équation $(E)$. Alors $21u+10v=21u_0+10v_0=1$.
Par conséquent $21(u-u_0)+10(v-v_0)=0$. Cette équation s'écrit aussi
$$21(u-u_0)=-10(v-v_0).$$
Le nombre 10 divise donc le produit  $21(u-u_0)$. Or il est
premier avec 21, par conséquent, d'après le théorème de Gauss, il
divise $u-u_0$, c'est à dire qu'il existe un nombre relatif $k$
tel que $u-u_0=10k$. En remplaçant $u-u_0$ par $10k$ dans
l'équation  $(E)$, on obtient $-(v-v_0)=21k$. Ainsi, toute solution de $(E)$ est de la forme 
$$\left\{\begin{array}{rcl}
u & = & u_0+10k \\
v & = & v_0-21k \\
\end{array}\right.(k\in\Z)$$ est solution de $(E)$.\\[5pt]
Réciproquement, tout couple de cette forme est solution de $(E)$ puisque $21(u_0+10k)+10(v_0-21k)=21u_0+10v_0=1$.

\begin{center}Les solutions de $(E)$ sont les couples d'entiers $(1-10k;-2+21k)$ où $k$  est un entier relatif.\end{center}

\section{Compléments historiques}

\subsection{Bezout}
BEZOUT Etienne (1730-1783), France.\\
E. Bezout est né à Nemours. Dès 1758, il fit partie de l'Académie des sciences. En 1763, il devint enseignant et examinateur en mathématiques des futurs officiers des Gardes du pavillon, de la marine et du corps d'artillerie.\\
La première démonstration actuellement connue du théorème portant son nom est due à Claude-Gaspard Bachet de Méziriac ; elle figure dans la seconde édition de son ouvrage Problèmes plaisans et délectables qui se font par les nombres, parue en 1624. Cependant, le mathématicien Étienne Bézout a généralisé ce résultat, notamment aux polynômes, démonstration notablement plus difficile. Par un de ces accidents de l'histoire mathématique, très fréquents, le nom de Bézout a été attribué à tort au résultat de Bachet.\\[10pt]
Johann Carl Friedrich Gauss Prononciation du titre dans sa version originale (traditionnellement transcrit Gauss en français) (30 avril 1777 - 23 février 1855) est un mathématicien, astronome et physicien allemand. Doté d'un grand génie, il a apporté de très importantes contributions à ces trois sciences. Surnommé << le prince des mathématiciens >>, il est considéré comme l'un des plus grands mathématiciens de tous les temps.\\
La qualité extraordinaire de ses travaux scientifiques était déjà reconnue par ses contemporains. Dès 1856, le roi de Hanovre fit graver des pièces commémoratives avec l'image de Gauss et l'inscription Mathematicorum Principi (<< prince des mathématiciens >> en latin). Gauss n'ayant publié qu'une partie infime de ses découvertes, la postérité découvrit la profondeur et l'étendue de son \oe uvre uniquement lorsque son journal intime, publié en 1898, fut découvert et exploité.\\
Considéré par beaucoup comme distant et austère, Gauss ne travailla jamais comme professeur de mathématiques, détestait enseigner et collabora rarement avec d'autres mathématiciens. Malgré cela, plusieurs de ses étudiants devinrent de grands mathématiciens, notamment Richard Dedekind et Bernhard Riemann.

\subsection{Équations diophantiennes}
Une équation diophantienne, en mathématiques, est une équation  dont les coefficients sont des nombres entiers et dont les solutions recherchées sont également entières. Le terme est aussi utilisé pour les équations à coefficients rationnels. Les questions de cette nature entrent dans une branche des mathématiques appelée arithmétique.

Si l'expression du problème posé est parfois simple, les méthodes de résolution peuvent devenir complexes. Carl Friedrich Gauss (1777 - 1855), un mathématicien du XIXe siècle, disait des problèmes de cette nature : \og~Leur charme particulier vient de la simplicité des énoncés jointe à la difficulté des preuves[1]. \fg

Certaines équations diophantiennes ont demandé pour leur résolution les efforts conjugués de nombreux mathématiciens sur plusieurs siècles. Gauss se plaignait \og~des efforts démesurés que lui a coûté la détermination d'un signe d'un radical dans la théorie des nombres ; bien d'autres choses ne l'ont pas retenu autant de jours que cette question l'a retenu d'années[2]. \fg Le dernier théorème de Fermat est un exemple archétypal, il est conjecturé par Pierre de Fermat (1601 - 1665) et résolu en 1994 par Andrew Wiles après 357 ans d'efforts de la part de nombreux mathématiciens.

L'intérêt de la résolution de questions de cette nature réside rarement dans l'établissement d'un théorème clé pour les mathématiques, la physique ou les applications industrielles, même s'il existe des contre exemples comme la cryptologie, qui fait grand usage du petit théorème de Fermat. Leur analyse amène le développement d'outils mathématiques puissants dont l'usage dépasse le cadre de l'arithmétique. Les formes quadratiques sont à cet égard exemplaires. La richesse et la beauté formelle des techniques issues de la résolution d'équations diophantiennes fait de l'arithmétique la branche reine des mathématiques pour David Hilbert[2].

Ce type d'équation doit son nom au mathématicien grec Diophante d'Alexandrie, un mathématicien vivant à une date incertaine, probablement autour du IIIe siècle. Il est l'auteur d'un traité, Arithmétiques, étudiant des questions de cette nature.

\subsection{Nouvelles méthodes de démonstrations}
Video de Gilles Dorweck a montrer.





\end{document}
