Arithmétique

L’arithmétique, c’est la science des nombres.

Au sens élémentaire, on s’intéresse aux nombres entiers naturels et à leurs propriétés vis-à-vis des opérations d’addition et multiplication (et donc soustraction, division, racines, etc.), ce qui amène naturellement à considérer aussi les entiers relatifs, les rationnels, et certains réels.

Arithmétique de Peano

Si on suppose naïvement disposer d’un ensemble de tous les nombres (et qu’on jette un voile pudique sur la manière de définir ce dernier), par exemple l’ensemble $\mathbf R$ des réels, alors l’ensemble $\mathbf N$ des entiers naturels est le plus petit ensemble contenant $0$ et clos par successeur $ S: x \mapsto x+1$.

Cet ensemble valide en particulier le principe de récurrence: il suffit de prouver qu’une propriété est vérifiée par $0$ et stable par successeur pour l’établir pour tous les éléments de $\mathbf N$.

Une manière formelle d’axiomatiser les entiers, c’est de renverser cette démarche : c’est l’idée de l’arithmétique de Peano. Plus précisément, on se donne des axiomes imposant que :

• $\mathbf N$ est muni d’un élément $0$ et d’une injection $S:\mathbf N\hookrightarrow \mathbf N$;
• $0$ n’est pas un successeur;
• toute propriété vérifiée par $0$ et stable par $S$ est vérifiée sur tout $\mathbf N$ (c’est l’axiome de récurrence).

(Si on veut être plus formel encore, il faut préciser le système logique dans lequel on se place, mais on n’est pas en cours de logique…)

En particulier tout élément de $\mathbf N^\bullet=\mathbf N\setminus\{0\}$ est un successeur. Et lorsqu’on se donne une fonction $f:\mathbf N\to\mathbf N$ et un élément $a\in\mathbf{N}$, on construit l’itération $f^n(a)$ par récurrence sur $n\in\mathbf{N}$.

La somme et le produit sont alors définis par itération:

• $m+n$ est obtenu en appliquant $n$ fois $S$ à $m$;
• $m×n$ est obtenu en ajoutant $n$ fois $m$ à $0$.

On démontre alors (toujours par une série de récurrences à partir des définitions) que $+$ et $×$ sont chacune associative et commutative, avec $0$ (resp. $1=S(0)$) comme élément neutre: chacune des structures $(\mathbf N, +)$ et $(\mathbf N,×)$ est un monoïde commutatif. Par ailleurs, $×$ est distributive par rapport à $+$ (et $0$ absorbant pour $×$): $(\mathbf N, +, ×)$ est un semi-anneau commutatif. Par ailleurs, ce semi-anneau $(\mathbf N,+,×)$ est positif ($a+b=0$ implique $a=b=0$), intègre ($ab=0$ implique $a=0$ ou $b=0$) et simplifiable (si $k\not=0$ et $ka=kb$ alors $a=b$).

On munit $\mathbf N$ d’une relation d’ordre en posant $m\le n$ s’il existe $p$ tel que $m+p=n$: le fait que c’est bien une relation d’ordre (réflexive, transitive, antisymétrique) découle encore des définitions (et en particulier du principe de récurrence). Par ailleurs on a $m<n$ ssi $S(m)\le n$. L’addition d’un entier est strictement croissante; la multiplication par un entier (resp. un entier non nul) est croissante (resp. strictement croissante).

Le principe de récurrence peut alors être reformulé en récurrence forte: si une propriété est vérifiée pour un élément quelconque dès qu’elle est vérifiée pour tous ses minorants stricts ($\forall n\in\mathbf{N},\,(\forall k<n,\, P(k))\Rightarrow P(n)$), alors elle est vérifiée sur tout $\mathbf{N}$. De manière équivalente, l’ordre sur $\mathbf{N}$ est bien fondé (ou nœthérien): toute partie non vide admet un minimum; ou, toujours de manière équivalente, il n’y a pas de suite infinie strictement décroissante.

Division euclidienne

Une notion cruciale dans cette structure est celle de division euclidienne: pour tous $a\in\mathbf N$ et $b\in\mathbf N^\bullet$, il existe un unique couple $(q,r)$ d’entiers tels que $a = qb+r$ et $0\le r\lt b$. On note $q=a÷b$ le quotient et $r=a\mod b$ le reste.

Exercices

• Savez-vous redémontrer l’unicité?
• Vous souvenez-vous de l’algorithme qui prouve l’existence?
• Savez-vous redémontrer la correction de cet algorithme?
• Réalisez cet algorithme en Python (définir une fonction division(a,b) qui renvoie le couple (q,r)).

Maintenant qu’on l’a fait à la main, rappelons que le quotient se calcule en Python avec // et le reste avec %; par ailleurs, la fonction divmod(a,b) calcule directement le couple a//b,a%b.

Représentation en base quelconque

Si on fixe $B>1$, alors tout entier $n\in\mathbf{N}$ tel que $n< B^k$ admet une unique écriture sous la forme \[ n = \sum_{i=0}^{k-1} c_i B^i \] avec $ 0\le c_i < B $ pour $ 0\le i< k$. La longueur de l’écriture de $n$ en base $B$, qu’on pourra noter $|n|_B$, est le plus petit $k$ tel que $n< B^k$ (en particulier $|n|_B=0$ ssi $n=0$).

Exercices

• Savez-vous redémontrer l’unicité?
• Vous souvenez-vous de l’algorithme qui prouve l’existence?
• Savez-vous redémontrer la correction de cet algorithme?
• Réalisez cet algorithme en Python (définissez une fonction representation(n,B) qui renvoie la liste c des $ c_i $, pour $0\le i<|n|_B$) dans l’ordre que vous voulez).
• Et, tant qu’on y est, définissez une fonction valeur(c,B) qui calcule la somme étant données la liste c des coefficients et la base B.
• Et déduisez-en une fonction conversion(c,B1,B2) qui transforme une écriture de la base B1 à la base B2.

Divisibilité

On dit que $d$ divise $m$ et on node $d\mid m$ s’il existe $q$ tel que $m=dq$ — autrement dit $m\mod d=0$. Si de plus $m\not=0$, alors $q=m÷d$. La relation ainsi définie est une relation d’ordre (large) sur $\mathbf N$.

Exercices

• Savez-vous prouver que c’est bien une relation d’ordre?
• Y a-t-il un plus petit élément? Un plus grand?

PGCD et PPCM

Tout couple $(a,b)$ d’entiers naturels admet un unique plus grand commun diviseur $a\wedge b$, c’est-à-dire qu’il existe un diviseur commun $d$ de $a$ et $b$ ($d\mid a$ et $d\mid b$) tel que tout autre diviseur commun divise aussi $d$. Autrement dit, $a\wedge b$ est la borne inférieure de $\{ a,b\}$ pour l’ordre de divisibilité.

De la même manière, tout couple $(a,b)$ d’entiers naturels admet un unique plus petit commun multiple $a\vee b$, qui est la borne supérieure de $\{ a,b\}$.

La divisibilité a ainsi une structure de treillis (avec $1$ comme plus petit élément, et $0$ comme plus grand élément).

Ces deux opérations sont donc chacune associative et commutative, avec $0$ (resp. $1$) comme élément neutre: chacune définit un semi-anneau commutatif sur $\mathbf N$. De plus, chacune est distributive par rapport à l’autre, $1$ est absorbant pour $\wedge$ et $0$ pour $\vee$ (le treillis est distributif).

Exercices

• L’unicité est évidente, mais vous souvenez-vous de l’algorithme d’Euclide, qui démontre l’existence du PGCD?
• Réalisez cet algorithme en Python (définir une fonction pgcd_euclide(a,b)).
• Si c’était trop facile pour vous, montrez la correction de l’algorithme du PGCD binaire et réalisez-le en Python.
• Vérifiez que $ka\wedge kb = k(a\wedge b)$.
• Déduisez-en le lemme de Gauss: si $a\mid bc$ et $a\wedge b=1$ alors $a\mid c$ (ça peut aussi se prouver en utilisant Bézout, mais ici on essaie de se contenter de parler d’entiers naturels).

Primalité et factorisation

Un entier naturel $p$ est premier s’il a exactement deux diviseurs: $1$ et lui-même (en particulier $p\not=1$). Et on dit que $a$ est premier avec $b$ si $a\wedge b=1$. Quand $p$ est premier alors pour tout $b$, on a nécessairement $p\wedge b=p$ (si $p\mid b$) ou $p\wedge b=1$ (sinon).

Exercices

• Décrivez un algorithme naïf pour tester si un nombre est premier: on cherche un diviseur en testant $2$ puis tous les impairs à partir de $3$ (en remarquant que si $ab=n$ alors $a^2\le n$ ou $b^2\le n$, pensez aussi à vous arrêter assez tôt). Notez que lorsque $n$ n’est pas premier, on obtient une factorisation de $n$ (et par construction, le plus petit des deux facteurs est premier).
• Réalisez cet algorithme en Python : écrivez une fonction factorise(n) qui renvoie un couple (p,a) avec n == p*a et p le plus petit facteur premier de n (en particulier n est premier ssi a==1).
• Que pensez-vous de son efficacité sur de grands nombres?

On sait faire mieux, en théorie et en pratique, pour tester la primalité. Pour la factorisation, c’est un autre problème….

Décomposition en facteurs premiers

Le théorème fondamental de l’arithmétique nous dit que tout entier naturel non nul admet une unique écriture comme produit de puissances de facteurs premiers deux-à-deux distincts. Formellement: pour tout $n\in\mathbf{N}$, il existe un unique ensemble fini $\{p_1<\cdots<p_k\}$ de nombres premiers et une unique suite finie $(a_1,…,a_k)$ d’entiers strictement positifs tels que \[ n = \prod_{i=1}^k p_i^{a_i} \;.\]

Exercices

• Vérifiez que le lemme de Gauss assure l’unicité de la décomposition.
• Vérifiez l’existence (c’est facile par récurrence forte).
• Déduisez de votre preuve d’existence de la décomposition un algorithme pour la calculer.
• À nouveau, que pensez-vous de son efficacité sur de grands nombres?