\documentclass[a4paper,11pt]{article}
\usepackage[francais]{babel}
\usepackage[dvips]{graphics}
\usepackage{graphicx}
\usepackage[latin1]{inputenc}
%\usepackage{isolatin1}
\usepackage{amsmath}
\usepackage{amscd}
\usepackage{amstext}
\usepackage{amsbsy}
\usepackage{amsopn}
\usepackage{amsthm}
\usepackage{amsxtra}
\usepackage{upref}
\usepackage{euscript}
\usepackage{amssymb}
\usepackage{amsfonts}
%\usepackage{ulsy}
\usepackage[all]{xy}
\usepackage{enumerate} % pour avoir des enumerations plus evoluees
\usepackage{vmargin}
\usepackage{txfonts}
\usepackage{textcomp}
\usepackage{fontenc}
%\usepackage{marvosym}
% Idem pour avoir un beau symbole du si et seulement si
\def\NN{\ensuremath{\mathbb{N}}}
\def\ZZ{\ensuremath{\mathbb{Z}}}
\def\QQ{\ensuremath{\mathbb{Q}}}
\def\RR{\ensuremath{\mathbb{R}}}
\def\CC{\ensuremath{\mathbb{C}}}
\def\KK{\ensuremath{\mathbb{K}}}
%
\parindent=0pt
\setmarginsrb{2,5cm}{0,5cm}{2,5cm}{1,5cm}{16pt}{30pt}{16pt}{45pt}
%\setmarginsrb{1}{2}{3}{4}{5}{6}{7}{8} 
% {1} marge gauche, {2} est la marge en haut,{3} est la marge droite,{4} est la marge en bas, {5} fixe la hauteur de l'entête, {6} fixe la distance entre l'entête et le texte, {7} fixe la hauteur du pied de page, {8} fixe la hauteur entre le texte et le pied de page.
%
\date{}
%
\title{Exposé 11 : PGCD et PPCM de deux entiers naturels. Nombres premiers entres eux. Applications. Illustration avec la calculatrice.}
%pour la date en français
%\def\today{\ifnum\day=1\relax 1\raisebox{.6ex}{\small er}
%\else \number\day\fi
%\space\ifcase\month\or janvier\or février\or mars\or avril\or mai\or juin\or juillet\or août\or septembre\or %octobre\or novembre\or décembre\fi\space\number\year}  
% guillemets ouvrant \og  fermant \fg
%
\newenvironment{pluslong}[2][]%
{\begin{flushleft}\textbf{#1} \textsc{#2\\} \textup}%
{\end{flushleft} }
%
%
\newenvironment{pluslong2}[2][]%
{\begin{flushleft}\textbf{#1} \textsc{#2} \textup}%
{\end{flushleft} }
%
\newenvironment{moyen}[1][]%
{\begin{flushleft}\textbf{#1\\} \textup}%
{\end{flushleft} }
%
\newenvironment{moyen2}[1][]%
{\begin{flushleft}\textbf{#1} \textup}%
{\end{flushleft} }
%
\newenvironment{court}%
{\begin{flushleft} \textup}%
{\end{flushleft} }
%
%
\newenvironment{preuve}[1][]%
{\begin{flushleft}\underline{preuve}\textup}%
{\qed\end{flushleft}}
%
\begin{document}
\maketitle
%\tableofcontents
% (table des matières)
%\newpage
\textbf{Prérequis}\footnotemark[1] :\\
\footnotetext[1]{L'exposé a été présenté à Bordeaux(1) en février 2005 par Johann, corrigée par M.B, et a été tapé par Gwendal Haudebourg. Il s'inspire très largement d'un exposé de Lionel. Réalisé avec \LaTeX. Mise à jour le 31/07/2007}
-Notion de diviseur multiple et de nombre premier\\
-Division Euclidienne dans $\NN$ \\
-Toute partie non vide de $\NN$ admet un plus petit élément\\
-Toute suite décroissante de $\NN$ est stationnaire à partir d'un certain rang
%
\\
\begin{small}
Cadre : $(a,b)\in \NN^{2}$. On se place dans $\NN$ (on pourra prendre $(a,b)\neq\left\lbrace (0,0) \right\rbrace$ pour éviter les problèmes de pgcd nons définis). 
\end{small}

\section{PGCD}

\subsection{Définition et calcul du PGCD}

\textbf{Définition:} Tout entier divisant à la fois $a$ et $b$ est appelé diviseur commun de $a$ et de $b$.\\

\textbf{Notation:} On notera $Div\lbrace a,b\rbrace$ l'ensemble des diviseurs communs à $a$ et $b$ (et $Div\lbrace c \rbrace$ l'ensemble des diviseurs de $c$, $c\in \NN$).\\


\textbf{Lemme:} Soit $r$ le reste de la division euclidienne de $a$ par $b$, $b \neq 0$. Alors : $Div\lbrace a,b \rbrace=Div\lbrace b,r \rbrace$\\

\textbf{Théorème :} Il existe un unique entier $d$ plus grand élément de $Div\lbrace b,r \rbrace$ pour la relation "est diviseur de", et on a $Div\lbrace b,r \rbrace=Div\lbrace d \rbrace$.\\

\textbf{Définition:} $d$ est appelé le plus grand diviseur de $a$ et $b$, noté $pgcd(a,b)=d$\\

\textbf{preuve}\textsc{(théorème)}:\\
\underline{Existence} Si $b=0$, $Div \lbrace a,b \rbrace$ $=D \lbrace a \rbrace$, si $a=0$, $Div \lbrace a,b \rbrace$ $=D \lbrace b \rbrace$. Supposons que $a \geq b>0$\\
Si $b \vert a$, alors $Div \lbrace a,b \rbrace$ $= Div \lbrace b \rbrace$, sinon $\exists !(q_{1},r_{1})$, $a=bq_{1}+r_{1}$, $0 \geq r_{1} \geq b$ par division euclidienne. Par le lemme, on a $Div\lbrace a,b \rbrace=Div\lbrace b,r_{1} \rbrace$. On pose $b=r_{0}$, et l'on construit ainsi $(r_{n})_{n},(q_{n})_{n}$ tels que $r_{0}=r_{1}q_{1}+r_{2}$, $r_{n-1}=r_{n}q_{n+1}+r_{n+1}$ avec $0\leq r_{n+1}<r_{n}$. Or $(r_{n})_{n}$ est une suite strictement décroissante et minorée (positive) de \NN, donc $\exists k \in \NN$ tel que $r_{k} \neq 0$ et $r_{k+1}=0$ (et $\forall n\geq K+1$, $r_{n}=0$).$r_{k-1}$ est donc le dernier reste non nul.\\
Donc $Div\lbrace a,b \rbrace$ $=Div\lbrace b,r_{1} \rbrace$ $=...=Div\lbrace r_{k-2},r_{k-1} \rbrace$ $=Div\lbrace r_{k-1} \rbrace$.\\
\underline{Unicité} Supposons qu'il existe deux $pgcd(a,b)=d_{1}$ et $d_{2}$\\
$d_{1}\vert a$ et $d_{1}\vert b$ or $d_{2}=pgcd(a,b)$ $\Rightarrow d_{1}\vert d_{2}$\\
$d_{2}\vert a$ et $d_{2}\vert b$ or $d_{1}=pgcd(a,b)$ $\Rightarrow d_{2}\vert d_{1}$ donc $d_{1}=d_{2}$\\

En fait, la preuve est constructive car en plus de prouver l'existence du $pgcd$, elle nous donne une méthode pour l'obtenir.

\subsection{Propriétés du PGCD}

Trois propriétés importantes :
\begin{enumerate}
\item $pgcd(a,b)=pgcd(b,a)$ (\textsc{commutativité})
\item $pgcd(na,nb)=n.pgcd(a,b)$
\item $pgcd(a,pgcd(b,c))=pgcd(pgcd(a,b),c)$ (\textsc{associativité)})
\end{enumerate}

\begin{moyen}[preuve]
(2) : on multiplie par $n$ toutes les divisions euclidiennes de l'algorithme d'Euclide :\\
$na=nbq+nr$, $nb=nrq_{1}+nr_{1}$, $nr=nr_{1}q_{2}+nr_{2}$...$nr_{N-2}=nr_{N-1}q_{N}$\\
donc $pgcd(na,nb)=n.r_{N-1}=n.pgcd(a,b)$
\end{moyen}

Deux autres propriétés : $pgcd(a,0)=a$ et $pgcd(a,1)=1$ 

\subsection{Nombres premiers entres eux}

\textbf{Définition :} $a$ et $b$ sont dits premiers entres eux si $pgcd(a,b)=1$

\subsubsection{Théorème de Bezout}

\textbf{Théorème de Bezout :} $a$ et $b$ sont premiers entres eux $\Longleftrightarrow \exists (u,v)\in \ZZ^{2}$ tels que $au+bv=1$\\

\textbf{preuve}\textsc{(Théorème de Bezout)}:\\
Si $au+bv=1$ alors toute division de $a$ et $b$ divise 1, donc est égale à 1, donc $pgcd(a,b)=1$\\
Réciproquement, $pgcd(a,b)=1$, donc dans l'algorithme d'euclide, $r_{N-1}=1$\\
On va vérifier par récurrecne sur $m$ que les $r_{m}$ sont combinaisons linéaires de $a$ et $b$\\
$r=a-bq$, $r_{1}=b-q_{1}r$ $=b-q_{1}a+bqq_{1}$ $=-q_{1}a+(1+qq_{1})b$, $r_{2}=r-r_{1}q_{2}$, donc on suppose que $\forall k\leq m, \exists u_{k},v_{k}\in \NN$ tels que $r_{k}=au_{k}+bv_{k}$.\\
$r_{m+1}=r_{m-1}-r_{m}q_{m+1}$ $=(au_{m-1}+bv_{m-1})-(au_{m}+bv_{m}).q_{m+1}$ $=a(u_{m-1}-u_{m}q_{m+1})+b(v_{m-1}-v_{m}q_{m+1})$, donc de même, $\exists (u,v)$ tq $r_{N-1}=1=au+bv$\\

\textbf{Corollaire :} $pgcd(a,b)=1$ et $pgcd(a,c)=1$ $\Rightarrow pgcd(a,bc)=1$

\subsubsection{Théorème de Gauss}

\textbf{Théorème de Gauss :} Si $pgcd(a,b)=1$ et si $a \vert bc$ alors $a \vert c$\\

\textbf{preuve :} $au+bv=1$ $\Rightarrow auc+bvc=c$ $\Rightarrow a \vert a$ et $a \vert bc$ $\Rightarrow a \vert c$

\section{PPCM}

\subsection{Définitions-Théorèmes}

\textbf{Définition :} Tout entier multiple à la fois de $a$ et de $b$ est appelé multiple commun de $a$ et $b$\\

Notation : $mult\left\lbrace a,b \right\rbrace$\\ 

\textbf{Théorème :} Il existe un unique entier $m$ plus petit élément de $mult\left\lbrace a,b \right\rbrace$ pour la relation divise, tel que $mult\left\lbrace m \right\rbrace=mult\left\lbrace a,b \right\rbrace$\\

\textbf{Définition :} m est appelé le plus petit multiple commun de $a$ et de $b$, et est noté $ppcm(a,b)=m$\\

\textbf{preuve}(\textsc{théorème}): on suppose que $a$ ou $b$ n'est pas nul (si $a=b=0 \Rightarrow m+0$ trivial)\\
\underline{Existence}: on a $\mu \in mult(a,b)\Leftrightarrow \exists u,v \in \NN$ $\mu=ua=vb$\\
Notons $d$ le $pgcd(a,b)$ et posons $a=da'$ et $b=db'$, donc on a $ua'=vb'$ avec $pgcd(a',b')=1$. Par Gauss, $\exists w$ tq $u=wb'$ donc $\mu=ua=wda'b'$.\\
Réciproquement, $\mu=wda'b'$ entraîne l'existence de $u$ et $v$ tq $\mu=ua=vb$, donc $\mu \in mult(a,b)\Leftrightarrow \exists w,\mu=wda'b'$ $\Leftrightarrow \mu \in mult(da'b')$. On pose $m=da'b'$\\ 
\underline{Unicité}: $mult(m)=mult(m')$ $\Leftrightarrow \exists u,v \in \NN$ tq $m=um'$ et $m'=vm$ d'où $m=uvm$ $\Rightarrow m=uvm$ $\Rightarrow u=v=1$ car $m\neq 0$ donc $m=m'$.

\subsection{Propriétés}

\begin{enumerate}
\item $m(a,b)=m(b,a)$
\item $m(a,m(b,c))=m(m(a,b),c)$
\item $m(ka,kb)=k.m(a,b)$
\end{enumerate}

\subsection{Relation entre ppcm et pgcd}

\textbf{Thérême :} $ppcm(a,b).pgcd(a,b)=a.b$\\

\textbf{preuve :} dans le théorème, on a trouvé que $m=da'b'\Rightarrow md=da'db'=ab$ 

\section{Applications}

\subsection{Fraction}

Toute fraction $\dfrac{a}{b}$ peut s'écrire sous la forme d'une fraction irréductible :\\
$\dfrac{a}{b}=\dfrac{a'.pgcd(a,b)}{b'.pgcd(a,b)}=\dfrac{a'}{b'}$ avec $pgcd(a',b')=1$

\subsection{Equations diophantiennes}
Résolution dans $\ZZ$ de $ax+by=c$, $(a,b)\in \NN^{*^{2}}$\\

L'équation admet des solutions si $pgcd(a,b)\vert c$\\
Soit $d=pgcd(a,b)$, $a=da'$, $b=db'$. $d(a'x+by')=c\Rightarrow d\vert c$ et $c=dc'$. $pgcd(a',b')=1\Rightarrow$ $\exists(u,v) \in \ZZ^{2}$ tq. $a'u+b'v=1$\\
d'où $a(c'u)+b(c'v)=c'$ donc $a(c'u)+b(c'v)=c$ donc $(c'u,cv)$ est solution de l'équation.\\
Résolution de l'équation : $(x_{0},y_{0})$ solution particulière.\\
$\forall (x,y)\in \ZZ^{2}$, $a'(x-x_{0})=b'(y-y_{0})$. $b'\vert a'(x-x_{0})$ et $pgcd(a',b')=1$ implique $b'\vert (x-x_{0})$ donc $\exists k$ tq. $x-x_{0}=kb'$.\\
$a'\vert b'(y-y_{0})$ et $pgcd(a',b')=1$ implique $a'\vert (y-y_{0})$ donc $\exists k'$ tq. $y-y_{0}=a'k'$\\ donc $x=kb'+x_{0}$ et $y=k'a'+y_{0}$

\subsection{$\sqrt{p}$, avec $p$ premier, est irrationnel}

Montrons par l'absurde que $\sqrt{p}\notin \QQ$ :\\
Supposons qu'il existe $(a,b)\in \ZZ^{2}$ tq. $\sqrt{p}=\dfrac{a}{b}$. On a alors $p=\dfrac{a^{2}}{b^{2}}$ donc $pb^{2}=a^{2}$ donc $p\vert a^{2}$ or  $p$ premier donc $p\vert a$ (lemme de Gauss)\\
De plus, $a=pq$ donc $pb^{2}=p^{2}q^{2}$, $b^{2}=pq^{2}$ d'où $p\vert b$.\\
Or $pgcd(a,b)=1$ d'où la contradiction (car $p\vert a$ et $p\vert b$).

\newpage

\section{Compléments}

\subsection{Un procédé de recherche : l'algorithme d'Euclide}

Algorithme pour la calculatrice (on prendra comme entrée $a\geq b$, $b\neq 0$)\\

\begin{small}
Entrée $a,b$\\
$a \rightarrow p$\\
$b \rightarrow q$\\
$a-E(\dfrac{a}{b}).b \rightarrow R$\\
$1 \rightarrow K$\\
Tant que $R\neq 0$ faire\\
$Q \rightarrow P$\\
$R \rightarrow Q$\\
$P-E(\dfrac{P}{Q}).Q \rightarrow R$\\
$K+1 \rightarrow K$\\
Fin tant que\\
Afficher $K,Q$
\end{small}\\

ex : $pgcd(131228,1912)=4$, $K=9$

\subsection{Application}

On peut aussi mettre les congruences comme applications (cf oral écrit 2005/2006) \\
Un autre point de vue peut-être pris pour cette leçon : parler de la relation d'orde "$\vert$"

\subsection{Commentaires M.B.}

Toute partie non vide de $\NN$ admet un plus petit élément : c'est ce que l'on appelle \textbf{une structure de bon ordre} (la relation d'odre sur $\NN$ étant "$\vert$" (div. Eulclidienne$\rightarrow$ odre partiel) ou "$\leqslant$" (ordre total).\\
\\
Toute ensemble peut-être muni d'une structure de bon-ordre$\Leftrightarrow$ axiome du choix\\
\textbf{Axiome du choix} : $(E_{i})_{i}$ ensemble, $E_{i}\neq\O{}$. Alors il existe $f$:
\begin{tabular}[t]{rlc}
$I$ & $\to$ & $\bigcup_{i \in I}E_{i}$ \\
$i$ & $\mapsto$ & $f(i)\in E_{i}$\\
\end{tabular}\\ 
\\
Quand $(E_{i})$ infini, on est incapable d'exhiber une telle fonction (ex : $f$).

\subsection{Exercices supplémentaires}

L'ensemble $\left\lbrace 2n+1,2n^{2}+2n \right\rbrace$ est composé de couple d'entiers premiers entres eux :\\
$2n^{2}+2n=n(2n+1)+n$\\
$n=\dfrac{1}{2}(2n+1)-\dfrac{1}{2}$\\
donc $2n^{2}+2n=(n+\dfrac{1}{2})(2n+1)-\dfrac{1}{2}$ donc $(2n+1)(2n+1)-2(2n^{2}+2n)=1$\\
d'où $pgcd(2n^{2}+2n,2n+1)=1$
Cela montre par ailleurs qu'il existe une infinité de couples $(a,b)$ de nombres premiers.\\
\\
De même pour l'ensemble $\left\lbrace 2n+5,n^{2}+5n+6 \right\rbrace$ :\\

\begin{center}
\begin{tabular}{c|c}
$n^{2}+5n+6$ &  $2n+5$\\ \hline 
$\frac{5}{2}n+6$ & $\frac{n}{2}+\frac{5}{4}$\\
$\frac{-1}{4}$ &  \\
\end{tabular} 
\end{center}

donc $n^{2}+5n+6=(2n+5)(\dfrac{n}{2}+\dfrac{5}{4})-\dfrac{1}{4}$\\
d'où $-4(n^{2}+5n+6)-(2n+5)(n+5)=1$ d'où $pgcd(2n+5,n^{2}+5n+6)=1$\

\end{document}