\chapter{Arithmétique}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Divisibilité}

\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{thm}[division euclidienne]
Soit $n \in \Z$, et soit $p\in\N^*$.
\Par
Il existe un unique couple $(q,r) \in \Z\times\N$ tel que :
\[n=pq+r\quad\text{avec}\quad 0 \leqslant r < q.\]
\end{thm}


\begin{defin}[congruence] 
Soient $n,\ m \in \Z$ et $p\in\N^*$. 

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}&\\
ac&\equiv bd &\pod{p}&
\end{aligned}
\right.   
\end{equation*}
\end{props}
%



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{solintro}
\begin{questions}
\item On peut écrire: $\numprint{1000}=27\times 37 + 1$ donc le quotient de la division euclidienne de \numprint{1000} par $37$ vaut $27$ et le reste vaut $1$.

\item Par la compatibilité des opérations avec la relation de congruence, nous avons :
\[
\numprint{1000}\times 1\times u+v \equiv u+v \pod{37}
\]
Ainsi,
\begin{align*}
n\text{ divisible par 37} & \iff n \equiv 0 \pod{37}\\
& \iff \numprint{1000}u+v \equiv 0 \pod{37}\\
& \iff u+v \equiv 0 \pod{37}\\
& \iff u+v\text{ divisible par }37.
\end{align*}
\end{questions}
\end{solintro}


\section{PGCD}

\subsection{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$, et 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{align*}
\numprint{231868} & = 28 \times \numprint{8190} + \numprint{2548}\\
\numprint{8190}   & = 3 \times \numprint{2548} + 546\\
\numprint{2548}   & = 4 \times 546 + 364\\
546               & = 1 \times 364 + 182\\
364               & = 2 \times 182 + 0.
\end{align*}

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


\subsection{Nombres premiers entre eux}

\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} si et seulement si $\PGCD(m;n)=1$.
\end{defin}

\begin{thm}[théorème de Bézout]
Soient $a$ et $b$ deux entiers relatifs non nuls. On a l'équivalence suivante:
\[
\PGCD(a;b)=1 \iff \exists (u,v)\in\Z\times\Z,\ au+bv = 1.
\]
\end{thm}


\begin{prop}
Soient $a$ et $b$ deux entiers relatifs non nuls. On a l'équivalence suivante:
\[
\begin{cases}
d|a\text{ et } d|b\\
\exists(u,v)\in\Z\times\Z,\ au+bv = d
\end{cases}
\iff
\PGCD(a;b)=d.
\]
\end{prop}

\begin{prop}[équations diophantiennes]
Soient $a$, $b$ et $c$ trois entiers relatifs non nuls.

L'équation diophantienne $ax+by=c$, d'inconnues entières $x$ et $y$, admet des solutions si et seulement si $\PGCD(a;b)$ divise $c$.
\end{prop}

\begin{Exemple}
$\PGCD(17;19)=1$ donc l'équation diophantienne $17x+19y=1$ admet des solutions entières.
\end{Exemple}


\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 a:\vspace*{-1em}
\[
\begin{array}{*9{@{}c@{}}}
12 & \times & 4 & - & 5 & \times & 9 & = & 3\\
12 &  \times & x & - & 5 & \times & y & = & 3
\end{array}
\]
Donc, par soustraction, on a:
\[
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$.

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.
\]
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}

\enlargethispage*{5em}

\begin{defin} 
Un entier naturel $n$ est un \textit{nombre premier} s'il  possède deux diviseurs distincts: 1 et lui-même.
\end{defin}

\newpage

\begin{attention}
1 n'est pas un nombre premier.
\end{attention}

\begin{thm}
Soit $n$ un entier supérieur ou égal à 2 non premier.

Alors, $n$ admet un diviseur premier inférieur ou égal à $\sqrt{n}$.
\end{thm}

\begin{Exemple}
\numprint{943} admet un diviseur premier inférieur ou égal à 30 car $\sqrt{\numprint{943}}\approx30,7$.
\end{Exemple}

\begin{thm}
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{thm}[petit théorème de Fermat]
Soit $a$ un entier naturel.

Si $p$ est un nombre premier ne divisant pas $a$ alors $a^{p-1} \equiv 1 \pod{p}.$
\end{thm}

\begin{Exemple}
$p=7$ ne divise pas $a=13$ donc, d'après le petit théorème de Fermat,
\[
13^{7-1}\equiv1\pod{7} \qquad\text{soit}\qquad 13^6\equiv1\pod{7}
\]
\end{Exemple}


\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
