# Introduction aux mathématiques/Entiers naturels

L'essentiel de ce chapitre est détaillé dans les leçons « Axiomes de Peano » et « Arithmétique ».

## Axiomatique de Peano

L'ensemble des entiers naturels, noté $\mathbb {N}$, est défini par les axiomes de Peano :
* L'ensemble possède un élément particulier que l'on note 0 ;
* Chaque élément n possède un successeur que l'on note S(n) ;
* 0 n'est le successeur d'aucun élément ;
* si deux éléments ont le même successeur, ils sont égaux ;
* Toute partie de $\mathbb {N}$ contenant 0 et stable par S est égale à $\mathbb {N}$ tout entier.

## Suite définie par une relation de récurrence

Grâce à l'axiome 5, on démontre :
Soient $f:E\rightarrow E$ et $a\in E$.
Alors il existe une unique suite $(u_{n})_{n\in \mathbb {N} }$ d'éléments de $E$ vérifiant
* $u_{0}=a$,
* $\forall n\in \mathbb {N} \quad u_{S(n)}=f(u_{n})$.

## Addition et multiplication dans $\mathbb {N}$

On note $1=S(0)$, puis $2,3,4,5,6,7,8,9$ les neufs premiers itérés de $0$. Pour ne pas à avoir recours à une infinité de symboles, on a trouvé un moyen plus malin, que vous connaissez depuis l'école élémentaire. On a bien sûr reconnu en $\mathbb {N}$ notre ensemble usuel pour compter ; ceci fera l’objet du prochain chapitre, mais avant cela il nous faut donner un sens à l’addition et à la multiplication.
Le théorème ci-dessus permet de définir l'addition et la multiplication dans $\mathbb {N}$ par :
    ${\begin{cases}&m+0=m\\\forall n\in \mathbb {N} \quad &m+S(n)=S(m+n),\end{cases}}\qquad {\begin{cases}&m\times 0=0\\\forall n\in \mathbb {N} \quad &m\times S(n)=(m\times n)+m.\end{cases}}$

### Remarques

   * $\forall m\in \mathbb {N} \quad m+1=S(m)$.
   * L'entier $m\times n$ est également noté $mn$.
* L'addition et la multiplication sur $\mathbb {N}$ sont associatives et commutatives.
* $0$ est neutre pour l'addition et $1$ est neutre pour la multiplication.
* La multiplication est distributive par rapport à l'addition.
* Tout élément $a\in \mathbb {N}$ est régulier pour l'addition, c'est-à-dire : $\forall c,c'\in \mathbb {N} \quad \left(a+c=a+c'\Rightarrow c=c'\right)$.

## Ordre sur $\mathbb {N}$

On définit ≤ à partir de l'addition :
    $\forall a,b\in \mathbb {N} \quad \left(a\leq b\Leftrightarrow \exists c\in \mathbb {N} \quad b=a+c\right)$
(l'entier $c$ est alors unique et noté $b-a$).
Alors :
* ≤ est une relation d'ordre sur $\mathbb {N}$ ;
* toute partie non vide de $\mathbb {N}$ admet un plus petit élément (en particulier, l'ordre est total) ;
* $\mathbb {N}$ lui-même a 0 pour plus petit élément ;
* le successeur d'un entier est son plus petit majorant strict.
De plus (exercice), ≤ est compatible avec l'addition et la multiplication, au sens où
    ${\begin{aligned}\forall a,b,c\in \mathbb {N} \quad &a\leq b\Leftrightarrow a+c\leq b+c\\&a\leq b\Rightarrow ac\leq bc.\end{aligned}}$

## Division euclidienne

On note $\mathbb {N} ^{*}:=\mathbb {N} \setminus \{0\}$.
Soit $(a,b)\in \mathbb {N} \times \mathbb {N} ^{*}$. Il existe un unique couple $(q,r)\in \mathbb {N} \times \mathbb {N}$, tel que $a=bq+r$ et $r<b$.
L'entier $q$ (resp. $r$) est appelé le quotient (resp. le reste) de la division euclidienne de $a$ par $b$.
Deux entiers $q$ et $r$ vérifient ces deux conditions si et seulement si $bq\leq a$, $r=a-bq$ et $a-bq<b$.
L'entier $r$ est donc uniquement déterminé en fonction de $q$, qui doit vérifier $bq\leq a<b(q+1)$, c'est-à-dire $q=\max\{k\in \mathbb {N} \mid bk\leq a\}$. Un tel entier $q$ (donc un tel couple $(q,r)$) est évidemment unique, et existe car $\{k\in \mathbb {N} \mid bk\leq a\}$ est non vide (il contient 0) et majoré (par $a$).

### Remarque

    On a alors : $a<b(q+1)$. En particulier, $\forall (a,b)\in \mathbb {N} \times \mathbb {N} ^{*}\quad \exists n\in \mathbb {N} \quad nb\geq a$. On résume ce fait en disant que l'ordre sur $\mathbb {N}$ est archimédien.
On définit sur $\mathbb {N}$ une relation binaire, la divisibilité par $\forall m,n\in \mathbb {N} \quad \left(m\mid n\Leftrightarrow \exists k\in \mathbb {N} \quad mk=n\right)$. Dans ce cas, on dit que $m$ divise $n$ ou que $n$ est un multiple de $m$. C'est une relation d'ordre. L'élément minimal est $1$ et maximal est $0$. On appelle nombre premier tout entier naturel admettant exactement deux diviseurs : $1$ et lui-même.

## Récurrences

On déduit immédiatement du cinquième axiome de Peano (voir supra), et de l'expression de $S(n)$ sous la forme $n+1$ :
Si ${\mathcal {P}}$ est une propriété telle que :
* ${\mathcal {P}}(0)$ est vraie — c'est l'initialisation de la récurrence,
* $\forall n\in \mathbb {N} \quad \left[{\mathcal {P}}(n)\Rightarrow {\mathcal {P}}(n+1)\right]$ — c'est l'hérédité,
alors $\forall n\in \mathbb {N} \quad {\mathcal {P}}(n)$ est vrai.
En appliquant ce théorème à ${\mathcal {P}}(n):={\mathcal {Q}}(n+n_{0})$, on obtient :
Soient $n_{0}\in \mathbb {N}$ et ${\mathcal {Q}}$ une propriété telle que :
* ${\mathcal {Q}}(n_{0})$ est vraie ;
* $\forall n\in \mathbb {N} \quad \left[\left(n\geq n_{0}{\text{ et }}{\mathcal {Q}}(n)\right)\Rightarrow {\mathcal {Q}}(n+1)\right]$.
Alors $\forall n\in \mathbb {N} \quad \left(n\geq n_{0}\Rightarrow {\mathcal {Q}}(n)\right)$ est vrai.
En appliquant le théorème à ${\mathcal {P}}(n):=\left[\forall k\in \mathbb {N} \quad \left(k\leq n\Rightarrow {\mathcal {R}}(k)\right)\right]$, que l'on écrit moins formellement ${\mathcal {R}}(0){\text{ et }}{\mathcal {R}}(1){\text{ et }}\dots {\text{ et }}{\mathcal {R}}(n)$, on obtient un autre corollaire :
Soit ${\mathcal {R}}$ une propriété telle que :
* ${\mathcal {R}}(0)$ est vraie — c'est l'initialisation de la récurrence ;
* $\forall n\in \mathbb {N} \quad \left[({\mathcal {R}}(0){\text{ et }}{\mathcal {R}}(1){\text{ et }}\dots {\text{ et }}{\mathcal {R}}(n))\Rightarrow {\mathcal {R}}(n+1)\right]$ — c'est l'hérédité.
Alors $\forall n\in \mathbb {N} \quad {\mathcal {R}}(n)$ est vrai.
Par contraposition, on déduit du corollaire précédent ou, directement, du cinquième axiome de Peano :
Soit ${\mathcal {R}}$ une propriété telle que :
    $\forall n\in \mathbb {N} \quad \left[\neg {\mathcal {R}}(n)\Rightarrow \exists k\in \mathbb {N} \quad k<n{\text{ et }}\neg {\mathcal {R}}(k)\right]$ (où $\neg$ est le symbole de négation).
Alors $\forall n\in \mathbb {N} \quad {\mathcal {R}}(n)$ est vrai.
| Relations binaires | Rudiments de combinatoire |