\addtocontents{toc}{\protect\newpage}
\chapter{Arithmétique (spécialité)}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Division Euclidienne}%

%
\begin{exointro}{Lycée Courbet, Belfort}
\begin{questions}
\item Calculer le reste de la division euclidienne de $\numprint{1000}$ par $37$.
\item En déduire que si $n$ s'écrit $\numprint{1000}\times u+v$ alors :
\[n \text{ est divisible par } 37 \iff u+v \text{ est 
     divisible par } 37.\]
\end{questions}
\end{exointro}

%
%
\begin{defin}[Diviseurs et multiples] 
Soit $n \in \Z$ et $p$ un entier supérieur ou égal à $2$. On dit que \emph{$p$ divise $n$}, et on écrit $p\mid n$, si et seulement si il existe un entier $a \in \Z$ tel que $n=a\times p$.
\Par
On rencontre aussi les expressions : $n$ est \emph{multiple de} $p$, $n$ est \emph{divisible par} $p$.
\end{defin}
%
\begin{defin}[Congruence] 
Soient $n,\ m \in \Z$ et $p$ un entier supérieur ou égal à $2$. On dit que $n$ est \emph{congru à} $m$ \emph{modulo} $p$, et on note : $n \equiv m \pod {p} $ si et seulement si $n-m$ est divisible par $p$.
\end{defin}
%
\begin{props}
Soient $a$, $b$, $c$, $d$, $e$ $\in \Z$, et $p$ un entier supérieur ou égal à $2$. Alors :
\begin{equation*}
\left\lbrace
\begin{aligned}
a&\equiv b \pod{p}\\
b&\equiv e \pod{p}\\
c&\equiv d \pod{p}
\end{aligned}
\right.
\Longrightarrow
\left\lbrace
\begin{aligned}
a&\equiv e &\pod{p}&\\
a+c&\equiv b+d &\pod{p}&\\
a\cdot c&\equiv b\cdot d &\pod{p}&
\end{aligned}
\right.   
\end{equation*}
\end{props}
%
\begin{thm}[Division euclidienne]
Soit $n \in \Z$, et $p$ un entier supérieur ou égal à $2$.
\Par
Il existe un unique $q \in \Z$ appelé \emph{quotient}, et un unique entier $r \in [0~;p-1]$ appelé \emph{reste}, tels que :
\[n=pq+r.\]
\end{thm}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{solintro}
\begin{questions}
\item Le quotient de la division de $\numprint{1000}$ par $37$ vaut $27$ et le reste vaut $1$, en d'autres termes :
\[
\numprint{1000}\equiv 1 \pod{37}.
\]
\item Par la compatibilité des opérations avec la relation de congruence, nous avons :
\[
\numprint{1000}\cdot u+v \equiv u+v \pod{37}.
\]
De cette relation, nous tirons l'équivalence suivante :
\[
\numprint{1000}\cdot u+v \equiv 0 \pod{37} \quad \Leftrightarrow u+v \equiv 0
\pod{37}.
\] 
\end{questions}
\end{solintro}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{PGCD et algorithme d'Euclide}

\begin{exointro}{Lycée Thiers, Marseille}%
Calculer le PGCD de $\numprint{231868}$ et de $\numprint{8190}$.
\end{exointro}


\begin{thm}[Algorithme d'Euclide]
Soient $a$ et $b$ deux entiers strictement positifs. On pose $A_{0} = a$ et $B_{0}=b$, on définit par récurrence deux suites d'entiers $A_{n}$ et $B_{n}$ comme suit : 
\[
A_{n+1}=B_{n}, \text{  et  }B_{n+1} \text{ est le reste de la division de } A_n \text{ par } B_{n}. 
\]
Soit $n_0$ le plus petit entier tel que $B_{n_0}$ soit nul. Alors, $B_{n_0-1}$ est le $\PGCD$ de $a$ et de $b$.
\end{thm}
\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{solintro}
 Mettons en place l'algorithme d'Euclide :
 
$
\begin{aligned}[t]
\begin{cases}
A_0&=\numprint{231868}\\ 
B_0&=\numprint{8190}
\end{cases}
&
\hspace*{2cm}A_0 = 28 \times B_0 +\numprint{2548}
\end{aligned}$

$\begin{aligned}[t]
    \begin{cases}
    A_1&=\numprint{8190}\\ 
    B_1&=\numprint{2548}
    \end{cases}
    &
\hspace*{2.35cm}A_1 = 3\times B_1 +546
\end{aligned}$

\Par

$\begin{aligned}[t]
\begin{cases}
A_2&=\numprint{2548}\\ 
B_2&=546
\end{cases}
&
\hspace*{2.35cm}A_2 = 4 \times B_2 +364 
\end{aligned}$

\Par

$\begin{aligned}[t]
\begin{cases}
A_3&=546\\ 
B_3&=364
\end{cases}
&
\hspace*{2.6cm}A_3 = 1 \times B_3 +182 
\end{aligned}$

\Par

$\begin{aligned}[t]
\begin{cases}
A_4&=364\\ 
B_4&=182
\end{cases}
&
\hspace*{2.6cm}A_4 = 2 \times B_4 +0.
\end{aligned}$

\Par

Donc :
\[
\PGCD(\numprint{8190},\numprint{231868})=182.
\]
\end{solintro}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Nombres premiers entre eux, égalité de Bézout}
%
\begin{exointro}{Lycée Sainte-Croix, Neuilly}
On considère l'équation $(E)$ : $12x-5y=3$ où $x$ et $y$ sont des entiers relatifs. Après avoir vérifié que le couple $(4~;9)$ est solution, résoudre l'équation $(E)$.
\end{exointro}


\begin{defin} [Entiers premiers entre eux] Deux entiers strictement positifs $m$ et $n$ sont dits \emph{premiers entre eux} lorsque l'une des conditions équivalentes suivantes est vérifiée :
\begin{itemize}
\item $\PGCD(m, n)=1$,
\item Il existe deux entiers $u$ et $v$ tels que $u \cdot m+v \cdot n=1\quad$ (égalité de Bézout).
\end{itemize}
\end{defin}
%
\begin{prop}
L'entier $d$ est le $\PGCD$ de $n$ et de $m$ si et seulement si les entiers $\dfrac{n}{d}$ et $\dfrac{m}{d}$ sont premiers entre eux.
\end{prop}

\newpage

\begin{thm}[Théorème de Gauss]
Si un entier $n$ divise le produit $ab$ et si $n$ et $a$ sont premiers entre eux, alors $n$ divise $b$.
\end{thm}


\begin{solintro}
On vérifie que $12\times4-5\times9=3$.\par
On a donc $12x-5y = 12\times4-5\times9$.\par
Cette équation équivaut à :
\[
12(x-4)=5(y-9).
\]
12 divise $12(x-4)$ donc 12 divise $5(y-9)$. Or, 12 est premier avec 5 donc, d'après le théorème de Gauss, 12 divise $(y-9)$. Il existe donc un entier relatif $k$ tel que $y-9=12k$ soit $y=12k+9$.\par 

En remplaçant $y$ par $12k+9$ dans l'équation initiale, on en déduit alors que $x=5k+4$.\Par
Réciproquement, tout couple $(5k+4~;12k+9)$, où $k$ désigne un entier relatif est solution de l'équation $12x-5y = 3$ puisque $12(5k+4)-5(12k+9)=3$.\Par
Les solutions de l'équation $(E)$ sont les couples  $(5k+4~;12k+9)$, où $k$ désigne un entier relatif.
\end{solintro}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Nombres premiers}%
%
\begin{exointro}{Lycée Chaptal, Paris}
Soit $n$ un entier positif, on définit :
\[
M_n=\dfrac{3^{n}-1}{2}.
\]
Démontrer que si $M_n$ est premier, alors $n$ est premier.
\end{exointro}

\begin{defin} On dit qu'un entier positif $n$ différent de $1$ est un \emph{nombre premier} s'il vérifie l'une des conditions équivalentes : 
\begin{itemize}
\item L'ensemble des diviseurs positifs de $n$ est $\Delta (n)=\{ 1~; n \}$, 1 et $n$ étant distincts
\item Soient $p$ et $q$ deux entiers positifs. Si $n=pq$ alors $p=1$ ou $q=1$.
\item Tous les entiers compris entre $1$ et $n-1$ sont premiers avec $n$.
\end{itemize}
\end{defin}

\newpage

\begin{attention}
1 n'est pas un nombre premier.
\end{attention}
%
\begin{thm}[Euclide]
L'ensemble des nombres premiers est infini.
\end{thm}
%
\begin{thm}[Décomposition en facteurs premiers]
Pour tout entier $n$ strictement plus grand que $1$, il existe un unique $k$-uplet de nombres premiers $(p_1~; \dots~; p_k)$, avec $p_1< \dots <p_k$, et un unique $k$-uplet d'entiers strictement positifs $(a_1~;\dots~; a_k)$ tel que :
\[
n=p_{1}^{a_{1}} \times \cdots \times p_{k}^{a_{k}}.
\]
\end{thm}
%
\begin{prop}
Le PGCD de deux entiers est égal au produit de leurs facteurs premiers communs affectés de leur plus petit exposant.
\end{prop}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{solintro}
Supposons que $n$ n'est pas premier. Il existe alors deux entiers $p$ et $q$ strictement supérieurs à 1 tels que $M_n$ puisse s'écrire :
\[
M_n=\left( \dfrac{3^{pq}-1}{3^{q}-1} \right) \left( \dfrac{3^{q}-1}{3-1}
\right).
\]
Les deux facteurs du produit sont des entiers : le premier est la somme des $p$ premiers termes de la suite géométrique de raison $3^q$ et de premier terme~1; le second est la somme des $q$ premiers termes de la suite géométrique de raison $3$ et de premier terme 1. Ce sont donc dans les deux cas des sommes d'entiers non nuls.
\par
Comme $M_n$ est premier, l'un de ces facteurs est égal à $1$. Ceci implique que $p=1$ ou $q=1$, ce qui est contraire à l'hypothèse, donc $n$ est premier.
\end{solintro}

\endinput
