L2 Informatique Année 2023-2024

HAI306X : Arithmétique
Polycopié de cours

Basé sur le polycopié de cours de HAI306X de Nicolas Saby et sur le livre "Arithmétique et
cryptologie" de Gilles Bailly-Maitre

I) Induction structurelle et construction des entiers

a) Ensemble défini inductivement/ type récursif
Comment définiriez-vous les entiers naturels comme des objets Java ?
Un exemple peut être trouvé ici :
[Link]
Regardant de près ce code, celui-ci repose, comme toutes les définitions récursives (ou inductives)
sur :
– un cas de base
– l’appel récursif.
De très nombreuses structures informatiques sont définies de cette manière.

 Définition 1 (Définition inductive). Une définition inductive d’un ensemble d’objets O

est donnée par :
– un ensemble d’éléments initiaux I ⊆ O
– des constructeurs (=applications de Ok → O, k ⩾ 1)

Exemple 2. Les mots Soit A un ensemble fini de lettres.

– Un élément minimal : "le mot vide ϵ est un mot"
– Autant de constructeurs unaires a : mot → mot que de lettres a ∈ A : "si a ∈ A et s est
un mot, alors a.s est un mot"

Exemple 3. Les arbres binaires Soit L un ensemble d’étiquettes.

– Éléments minimaux : " une racine étiquetée par e ∈ L est un arbre binaire
– Constructeurs : "si e ∈ L et A1 et A2 sont des arbres binaires, alors Tree(e, A1 , A2 ) est
un arbre binaire.

Exemple 4. Les formules logiques Soit P0 un ensemble de variables propositionnelles.

– Éléments minimaux : "si P est une variable propositionnelle, alors P est une formule
propositionnelle"
– Constructeurs :
— Si ϕ est une formule propositionnelle, alors ¬ϕ est une formule propositionnelle.
— Si ϕ1 et ϕ2 sont des formules propositionnelles, alors ϕ1 ∨ ϕ2 est une formule
propositionnelle.
— Si ϕ1 et ϕ2 sont des formules propositionnelles, alors ϕ1 ∧ ϕ2 est une formule
propositionnelle.

 Définition 5 (injectivité). Une application f : E 7→ E est injective si chaque élément a un

unique antécédent :
∀x, y ∈ E, f (x) = f (y) =⇒ x = y

Exemple 6. L’application N → N qui a n associe 0 si n est pair et 1 sinon n’est pas

injective. L’application R → R x 7→ x3 est injective.

 Définition 7 (N). L’ensemble des entiers naturels, noté N, est défini inductivement par :
– Un élément minimal : "0 est un entier naturel"

1
L2 Informatique Année 2023-2024

– Un constructeur unaire injectif : s : N at → N at − {0} : "si n est un entier naturel, alors

s(n) est un entier naturel non nul."
s(n) est appelé le successeur de n. n est le prédecesseur de s(n).

 Définition 8. Un ensemble inductif est le plus petit ensemble engendré par les éléments
minimaux et les constructeurs.

L’intérêt de cette définition récursive est qu’elle permet de mettre en oeuvre des techniques de
preuve très efficaces

b) Ordre bien fondé

 Définition 9 (Relation d’ordre). Soit E un ensemble, muni d’un sous-ensemble O de
E × E, O est une relation d’ordre sur E si pour tous éléments x, y et z de E :
– (Réflexivité) (x, x) ∈ O
– (Transitivité) si (x, y) ∈ O et (y, z) ∈ O, alors (x, z) ∈ O,
– (Anti-symétrie) si (x, y) ∈ O et (y, x) ∈ O, alors x = y,
On note x ⩽ y pour tout couple (x, y) ∈ O.

 Définition 10 (Ordre strict). Soit E un ensemble, muni d’un sous-ensemble O de E × E,

O est un ordre strict sur E si pour tous éléments x, y et z de E :
– Si (x, y) ∈ O, alors (x, y) ∈
/O
– (Transitivité) Si (x, y) ∈ O et (y, z) ∈ O, alors (x, z) ∈ O.
On note x < y pour tout couple (x, y) ∈ O.

 Définition 11 (Ordre total). Un ordre ⩽ (resp. un ordre strict <) est total si deux éléments
sont toujorus comparables :

∀x, y ∈ E, x ⩽ y ou y ⩽ x (resp. x < y ou y < x )

 Définition 12 (Ensemble bien fondé). Un ensemble E muni d’un ordre stricte < est
bien fondé si et seulement s’il n’existe aucune chaîne infinie décroissante (c’est-à-dire de la forme
a0 > a1 > . . . ).

Exemple 13. Ordres stricts pas bien fondées :

– les entiers, et l’ordre < usuel :
4 > 3 > 2 > 1 > 0 > −1 > −2 > . . .
– les mots sur un alphabet et l’ordre dictionnaire
b > ab > aab > aaab > . . ..
– les entiers rationnel et l’ordre < usuel.
4.2 > 4.19 > 4.119 > . . .

Exemple 14. Ordres stricts bien fondées :

– les entiers naturels {0, 1, 2, . . .} et l’ordre usuel <.
– les entiers positifs {1, 2, . . .} et l’ordre a < b ssi a divise b et a ̸= b.
– les ensembles finis et l’ordre usuel ⊂.
– les mots sur un alphabet et l’ordre s < t ssi s est un sous-mot strict de t.
– l’ensemble N × N, et l’ordre (n1, n2) < (m1, m2) ssi n1 < m1 et n2 < m2.
– l’ensemble N × N, et l’ordre lexicographique (n1, n2) < (m1, m2) ssi n1 < m1 ou n1 = m1
et n2 < m2.
– les noeuds d’un graphe orienté acyclique et l’ordre aRb ssi il y une arête de a vers b.

2
L2 Informatique Année 2023-2024

3 Théorème 15. Soient donnés un ensemble A quelconque, un ordre strict bien fondé ⊏ sur
A (dont M est son ensemble d’éléments minimaux), et une propriété P sur A.

Si
1. pour tout élément minimal m ∈ M on a P(m)
2. le fait que P(k) soit vérifiée pour tout élément k⊏x implique P(x)
alors
pour tout a ∈ A on a P (a)

Démonstration. On montre le théorème par l’absurde en supposant les hypothèses vérifiées et

qu’il existe un a0 ∈ A tel que P (a0 ) ne soit pas vérifiée.
Comme l’hypothèse 1) est vérifiée, a0 ∈ / M donc a0 n’est pas minimal pour l’ordre bien fondé.
D’après l’hypothèse 2), il existe a1 ⊏ a0 tel que P (a1 ) ne soit pas vérifié. En appliquant le même
raisonnement à a1 et aux éléments suivants, on obtient une suite (ak )k ⩾ 0 d’éléments verifiant
ak+1 ⊏ ak et tels que P (ak ) ne soit pas vérifié, ce qui contredit le fait que ⊏ soit bien fondé.

ü Remarque 16. Pour prouver la conclusion ∀a ∈ A.P (a) (la propriété P est vraie sur tous
les éléments de A) il faut prouver :
– Chaque cas de base P (m) où m ∈ M, sans utiliser d’hypothèse supplémentaire,
– Le cas inductif P (x), en utilisant les hypothèses d’induction (plusieurs) {P (k) | k ∈
A et k ⊏ x}.

? Question 17. Considérons la fonction f : N × N → N définie par


 0 si n = 0 et m = 0
f (n, m) = 1 + f (n, m − 1) si m > 0
f (n − 1, n) si n > 0 et m = 0


1. f est-elle bien définie ?

2. que calcule f ?

Réponse 18. On raisonne par induction sur N 2 muni de l’ordre lexicographique pour montrer
que la fonction est bien définie et que on a f (n, m) = n(n+1)
2 + m. Pour le prouver, on applique
n(n+1)
l’induction bien fondée à la propriété P(n, m) ≡ f (n, m) = 2 + m dans N × N.

c) Induction structurelle
Exemple 19. Le code suivant est-il correct ? Pourquoi ?
public class maListe {
int tete;
maListe queue;
maListe(int dbt, maListe fin){
tete=dbt;
queue=fin;
}
int longueur(){
if([Link]==null){
return 1; }
else{return (1+[Link]());
}
}

3
L2 Informatique Année 2023-2024

maListe concat(int dbt){

return new maListe(dbt, this);
}
}

 Définition 20. On considère la définition inductive d’un ensemble X donnée par des règles
de la forme :
– Si a1 , . . . , an ∈ X alors f (a1 , . . . , an ) ∈ X ,
où f est un constructeur n-aire
On construit un ordre, appelé sous-structure ⊏ (qui est strict et bien fondé) en associant à chaque
constructeur f les couples a1 ⊏ f (a1 , . . . , an ), . . . , an ⊏ f (a1 , . . . , an ).

ü Remarque 21. – Les cas de base correspondent aux éléments minimaux

– Les cas inductifs sont les constructeurs avec 1 ou plus d’arguments.

Exemple 22. – Les mots sur un alphabet, où n ⊏ a.n pour toute lettre a et tout mot
n.
– Les arbres arbres binaires, où Ai ⊏ ab(A1 , A2 ) (i = 1, 2) pour tous les arbres A1 et A2 .
– Les entiers naturels, où n ⊏ n + 1 (notée plutôt <). Par transitivité, on a alors

∀n ∈ N, ∀m ∈ N, m < n ⇐⇒ ∃p ∈ N∗ , n = m + p.

3 Proposition 23. Un ensemble défini par induction structurelle muni de la relation sous-
structure est un ensemble bien fondé.

3 Théorème 24 (Principe d’induction structurelle.). Soient donnés un ensemble X dé-

fini par induction structurelle et muni de l’ordre sous-structure et une propriété P sur X .

Si
1. pour tout élément minimal m ∈ M on a P(m)
2. pour chacun des constructeurs c : X k → X , le fait que P(a1 ), . . . , P(ak ) soient vérifiées
implique P(c(a1 , . . . , ak ))
alors
pour tout a ∈ A on a P (a)

Exemple 25. On définit une fonction concat sur les mots comme suit :

concat(ϵ, k) := k
concat(a.l, k) := [Link](l, k)
Soit m un mot et soit P la propriété suivante :

P (m) = ”concat(concat(m, v1 ), v2 ) = concat(m, concat(v1 , v2 ))”

Démontrer par induction la propriété P pour tout les mots.

Exemple 26. Soit a un arbre binaire et soit P la propriété suivante :

P (a) = ”#f euilles(a) = #noeuds_internes(a) + 1”

Démontrer par induction la propriété P pour tout les arbres binaires.

4
L2 Informatique Année 2023-2024

d) Induction sur les entiers

3 Théorème 27 (Principe de récurrence). Soit P une propriété sur les entiers naturels.
Soit X un sous-ensemble de N dont l’élément minimal est m.
Si
– P (m) est vrai,
– Le fait que P (x) soit vrai implique que P (x + 1) est vrai,
alors
pour tout n ∈ X on a que P (n) est vrai.

ü Remarque 28. Pour prouver la conclusion ∀n ∈ X .P (n) (la propriété P est vraie sur tous
les entiers de l’ensemble X ) il faut prouver :
– Le cas de base P (m), sans utiliser d’hypothèse supplémentaire,
– Le cas inductif P (x + 1), en utilisant l’hypothèse d’induction P (x) (une seule hypothèse
d’induction).

? Question 29. En combien de mouvements au minimum est-il possible de résoudre le problème

de la tour de Hanoï (amener tous les disques sur le poteau de droite) à n disques ?

3 Théorème 30 (Principe de récurrence forte). Soit P une propriété sur les entiers
naturels. Soit X un sous-ensemble de N dont l’élément minimal est m.
Si
– P (m) est vrai,
– Le fait que P (k) soit vrai pour tout élément k < x implique que P (x) est vrai,
alors
pour tout n ∈ X on a que P (n) est vrai.

ü Remarque 31. Pour prouver la conclusion ∀n ∈ X .P (n) (la propriété P est vraie sur tous
les entiers de l’ensemble X ) il faut prouver :
– Le cas de base P (m), sans utiliser d’hypothèse supplémentaire,
– Le cas inductif P (x), en utilisant les hypothèses d’induction (plusieurs) {P (k) | k ∈
X et k < x}.

Exemple 32. – Algorithme de tri (par exemple, tri fusion)

– Montrer que tout entier n > 0 admet une expression binaire (càd qu’il existe ci ∈ {0; 1}
tq n = cr 2r + cr−1 2r−1 + . . . + c0 20 )

e) Opérations sur les entiers

La définition récursive précédente permet de définir des lois sur l’ensemble des entiers N.

Addition

3 Théorème 33. Définition de l’addition : Il existe une loi de composition interne, appelée
addition sur l’ensemble des entiers. Elle est définie par les deux règles suivantes :

(1) ∀n ∈ N, ∀m ∈ N, n + 0 = n
(2) ∀n ∈ N, ∀m ∈ N, n + s(m) = s(n + m).

La règle (1) exprime que 0 est neutre pour l’addition.

La règle (2) définit l’addition par récurrence et prolonge l’idée intuitive que s(n) n’est rien d’autre
que n + 1.

5
L2 Informatique Année 2023-2024

Démonstration. En effet pour n ∈ N, on a :

n + 1 = n + s(0) = s(n + 0) = s(n)

On vient donc de définir n + 1 comme une réécriture de s(n).

Montrons maintenant que la somme de deux entiers quelconques est toujours calculable.
Soit donc n ∈ N un entier. Et considérons l’ensemble M des entiers m pour lesquels, la somme
n + m est calculable.
Par la propriété (1), cet ensemble contient 0 et par la propriété (2), il est stable par l’application
successeur, puisque la propriété (2) dit précisément que si je sais calculer n + m, alors je sais
calculer n+s(m) c’est-à-dire que si m ∈ M , alors s(m) ∈ M . La définition inductive de N comme
plus petit ensemble contenant 0 et clos par s implique que M = N.

3 Théorème 34.
1. Associativité : La loi + est une loi associative :

∀n ∈ N, ∀m ∈ N, ∀p ∈ N, m + (n + p) = (m + n) + p

2. Commutativité : La loi + est une loi commutative :

∀n ∈ N, ∀m ∈ N, n + m = m + n

3. Tout élément de N est régulier :

∀n ∈ N, ∀m ∈ N, ∀p ∈ N, [m + n = m + p] ⇐⇒ [n = p]

Cette propriété exprime que tout entier est simplifiable dans une égalité.
4. Seul 0 admet un opposé dans N.
Démonstration. Voir TD1 exercice 7 pour les deux premiers points.

Montrons que tout élément est régulier. Soient n et p deux entiers naturels. Montrons par récur-
rence sur m que
P (m) = ”n + m = p + m =⇒ n = p”.
Cas de base Comme 0 est le neutre pour l’addition, on a :n = n + 0 et p + 0 = p donc si
n + 0 = p + 0, alors n = p
Hérédité Supposons P (m) vraie pour un m ⩾ 0 et que l’on ait n + s(m) = p + s(m). Alors,
s(n + m) = s(p + m), or s est injective donc n + m = p + m, ce qui implique n = p par
hypothèse de récurrence.
Par principe de raisonnement par récurrence, P (m) est alors vrai pour tout entier naturel m ⩾ 0.

Montrons maintenant que 0 est le seul entier naturel avec un opposé. Raisonnons par l’absurde
et supposons qu’il existe un entier naturel non nul p avec un opposé, c’est-à-dire avec un entier
naturel q tel que q + p = 0. p est différent de 0 donc il peut s’écrire comme le successeur d’un
nombre p′ . On a alors :

q+p=0
q + s(p′ ) = 0
s(q + p′ ) = 0

Cette dernière égalité contredit le fait que 0 ne soit pas dans l’image de s. Par conséquent, il
n’existe aucun entier naturel non nul avec un opposé.

6
L2 Informatique Année 2023-2024

Multiplication
3 Théorème 35. Définition de la multiplication : Il existe une loi de composition interne,
appelée multiplication sur l’ensemble des entiers. Elle est définie par les deux règles suivantes :
(1) ∀n ∈ N, ∀m ∈ N, n × 0 = 0
(2) ∀n ∈ N, ∀m ∈ N, n × s(m) = (n × m) + n.
Comme pour l’addition, cette définition repose sur l’idée intuitive de la multiplication comme
addition itérée.
Démonstration. On procède comme pour l’addition.
Soit n ∈ N et considérons l’ensemble M des entiers m pour lesquels n × m est calculable.
La première propriété nous assure que 0 est bien dans M et la seconde propriété nous assure que
l’ensemble M est stable par l’opération successeur, puisque comme pour l’addition, elle exprime
que si je sais calculer n × m, alors je sais calculer n × s(m). La définition inductive de N comme
plus petit ensemble contenant 0 et clos par s implique que M = N.
3 Lemme 36. La multiplication vérifie la relation suivante :
∀n ∈ N, ∀m ∈ N, s(n) × m = n × m + m
Démonstration. Récurrence sur m. (à rédiger chez vous)
3 Théorème 37.
1. Distributivité : La multiplication est distributive sur l’addition à droite et à gauche :
∀m ∈ N, ∀n ∈ N, ∀p ∈ N, (m + n) × p = m × p + n × p
∀m ∈ N, ∀n ∈ N, ∀p ∈ N, p × (m + n) = p × m + p × n.
2. Associativité : La multiplication est une loi associative :
∀m ∈ N, ∀n ∈ N, ∀p ∈ N, m × (n × p) = (m × n) × p
3. Commutativité : La multiplication est une loi commutative :
∀m ∈ N, ∀n ∈ N, m × n = n × m
4. 0 est absorbant (c’est-à-dire n × 0 = 0 = 0 × n)
5. Le produit de deux éléments non nuls est non nul.
6. Le seul entier admettant un inverse est 1
Démonstration. 1. Distributivité : Fixant m et n, récurrence sur p (le faire proprement à la
maison).
2. Associativité : Récurrence sur ... (cherchez un peu vous-même !)
3. Commutativité : Récurrence (c’est un bon entraînement de la rédiger)
4. 0 est absorbant : hypothèse + commutativité
5. Soient n = s(n′ ) et m = s(m′ ) deux éléments non nuls. On a :
n × m = s(n′ ) × s(m′ ) = s(n) × m + s(n) = s(n + s(n) × m) ̸= 0
Car 0 n’est pas dans l’image de s.
6. 1 admet un inverse :
1 × 1 = 1 × s(0) = 1 × 0 + 1 = 1 (1)
Soit m = s(m′ ) inversible, d’inverse i ⩾ 1 :
1 = m × i = m′ × i + i
or i ⩾ 1 donc l’égalité n’est vérifiée que si m′ × i = 0, soit si m′ = 0 et m = 1.

7
L2 Informatique Année 2023-2024

Soustraction La soustraction n’est pas une loi interne, en ce sens qu’on ne peut pas toujours
la définir.
Soit n ∈ N et m ∈ N. S’il existe p ∈ N tel que n = m + p, alors on peut écrire p = n − m résultat
de la soustraction de m à n ou différence de n et m.

f) Sous-ensembles de N et ordre
La relation d’ordre strict "sous-structure" donnée par la clôture transitive de n′ < n si n = s(n′ )
est la relation d’ordre usuelle sur N :

m < n ⇔ ∃p ∈ N∗ : n = m + p

On peut lui associer la relation d’ordre (non stricte)

m ⩽ n ⇔ ∃p ∈ N : n = m + p

3 Théorème 38. La relation ⩽ est

– compatible avec l’addition :

∀n ∈ N, ∀m ∈ N, ∀p ∈ N, n ⩾ m ⇔ [(n + p) ⩾ (m + p)]

– compatible avec la multiplication :

∀n ∈ N, ∀m ∈ N, ∀p ∈ N, n ⩾ m ⇔ [(n × p) ⩾ (m × p)]

– une relation d’ordre totale :

∀n ∈ N, ∀m ∈ N, n ⩾ m ou m ⩾ n

Elle vérifie de plus les propriétés suivantes :

3 Théorème 39. Les relations d’ordre < et ⩽ sur les entiers vérifient :
1. ∀n ∈ N, 0 ⩽ n
2. ∀n ∈ N, 0 < n ⇔ n ̸= 0
3. ∀n, m ∈ N, 0 < n et 0 < m =⇒ 0 < n + m
4. ∀n ∈ N, ∄m ∈ N, n < m < n + 1

Démonstration. Les deux premiers points découlent directement des définitions : si n ̸= 0, n =

0 + n donc 0 < n.
Si n, m ∈ N, 0 < n et 0 < m, 0 < n et n < n + m d’où le résultat par transitivité.
Supposons qu’il existe deux entiers naturels n et m tels que n < m < n + 1, alors il existe deux
entiers naturels non nuls p et q tels que m = n + p et n + 1 = m + q = n + p + q. Comme n est
régulier, nous avons alors 1 = p + q or 1 ⩽ p et 1 ⩽ q d’où 2 ⩽ p + q et 2 ⩽ 1, ce qui est absurde :
il n’existe donc aucun couple d’entiers naturels n et m vérifiant n < m < n + 1.

 Définition 40. Soit A une partie non vide de N.

Un majorant (resp. majorant strict, minorant, minorant strict de A est un entier m
supérieur ou égal (resp. strictement supérieur, inférieur ou égal, strictement inférieur) à tout
élément de A.

Il découle du dernier point du Théorème 39 le résultat suivant :

3 Corollaire 41. – Le successeur d’un entier est le plus petit de ses majorants stricts.
– Le prédécesseur d’un entier, s’il existe, est le plus grand de ses majorants stricts.

8
L2 Informatique Année 2023-2024

 Définition 42. Soit A une partie non vide de N.

– Un élément de A est un minimum de A s’il est un minorant de A
– Un élément de A est un maximum de A s’il est un majorant de A

3 Théorème 43. – Toute partie non vide de N admet un minimum, nécessairement unique.
– Toute partie non vide et majorée de N admet un maximum, nécessairement unique.

Démonstration. On se sert du fait qu’il n’existe pas de suite infinie décroissante dans N. À vous
de réfléchir à quelle suite on a envie de considérer.

3 Théorème 44. L’ensemble N n’admet pas de maximum

Démonstration. Par l’absurde : Si un tel maximum m existait, que dire de s(m) ?

3 Théorème 45. Propriété d’Archimède Pour tout entier q et tout entier non nul p, il
existe un entier n tel que
np > q.
En d’autres termes, il n’existe pas d’entier infiniment grand qui ne saurait être dépassé par un
nombre fini de pas.

Démonstration. Si q > 0, qp > q donc n = q convient.

Si q = 0, n = 1 convient.

9
L2 Informatique Année 2023-2024

II) Annexes
a) Axiomes de Peano
 Définition 46. Il existe un ensemble noté N dont les éléments sont les entiers, dont l’un est
noté 0. Il est muni d’une application successeur s : N → N vérifiant les propriétés suivantes :
P1 L’application successeur s, est injective ;
P2 L’élément 0, nommé zéro n’a pas d’antécédent par s ;
P3 Tout sous-ensemble de N qui contient 0 et qui est stable par l’application successeur s
est égal à N.

Ainsi, 1 = s(0), 2 = s(s(0)), etc.

L’axiome P.3 est ce qu’on appelle le principe de récurrence :
Soit M un sous ensemble de N.
Si 0 appartient à M et si pour tout élément de M , le successeur de cet élément est
dans M , alors l’ensemble M est égal à l’ensemble N.

10