Table des matières

Introduction 2

1 Logique 5
1.1 Logique assertionnelle ou propositionelle . . . . . . . . . . . . . . . . . 5
1.1.1 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.2 But du calcul propositionnel . . . . . . . . . . . . . . . . . . . . 5
1.1.3 Syntaxe et évaluation des propositions . . . . . . . . . . . . . . . 6
1.1.4 Propriétés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2 A RITHMÉTIQUE . 10
2.1 Divisibilité dans les entiers . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Plus grand commun diviseur, Plus pétit commun multiple . . . . . . . . . 13
2.2.1 Définitions et propriétés . . . . . . . . . . . . . . . . . . . . . . 13
2.2.2 Résolution d’équations diophantiennes linéaires . . . . . . . . . . 14
2.3 Entiers relativement premiers . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3.1 Définitions et propriétés . . . . . . . . . . . . . . . . . . . . . . 15
2.4 Les nombres premiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.4.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.4.2 Propriétés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.5 Quelques familles de nombres premiers . . . . . . . . . . . . . . . . . . 20
2.5.1 Les grands nombres premiers . . . . . . . . . . . . . . . . . . . 20
2.5.2 Les premiers de Sophie Germain . . . . . . . . . . . . . . . . . . 21
2.5.3 Les factoriels et primoriels premiers . . . . . . . . . . . . . . . . 22
2.6 Production des nombres premiers . . . . . . . . . . . . . . . . . . . . . . 22
2.6.1 A partir les nombres de Fermat et/ou de Mersennes . . . . . . . . 23
2.6.2 Formules de nombres premiers . . . . . . . . . . . . . . . . . . . 23
2.6.3 Nombres premiers dans une progressions Arithmetique . . . . . . 24
2.7 T HÉORIE DES C ONGRUENCES . . . . . . . . . . . . . . . . . . . . . . . 24
2.7.1 La congruence modulo . . . . . . . . . . . . . . . . . . . . . . . 24
2.7.2 Classes résidues et conséquences . . . . . . . . . . . . . . . . . . 26
2.8 L OI DE RÉCIPROCITÉ QUADRATIQUE . . . . . . . . . . . . . . . . . . . 30
2.8.1 Généralité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.8.2 Utilisation des symboles de Jacobi . . . . . . . . . . . . . . . . 31
2.8.3 Symbol de Legendre . . . . . . . . . . . . . . . . . . . . . . . . 31
2.8.4 Symbol de Jacobi . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.9 Numération . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.9.1 Bases de numération . . . . . . . . . . . . . . . . . . . . . . . . 33

1
2.9.2 Quelques systèmes de numération les plus usuels . . . . . . . . . 34
2.9.3 Congruences particulières-Critères de divisibilité par 3, 4, 5, 9, 11
et 25 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
Introduction

La logique mathématique se fonde sur les premières tentatives de traitement formel

des mathématiques, dues à Leibniz et Lambert (fin 16ème siècle - début 17ème siècle).
Leibniz a en particulier introduit une grande partie de la notation mathématique moderne
(usage des quantificateurs, symbole d’intégration, etc.). Toutefois on ne peut parler de
logique mathématique qu’à partir du milieu du 19ème siècle, avec les travaux de George
Boole (et dans une moindre mesure ceux d’Auguste De Morgan) qui introduit un calcul de
vérité où les combinaisons logiques comme la conjonction, la disjonction et l’implication,
sont des opérations analogues à l’addition ou la multiplication des entiers, mais portant
sur les valeurs de vérité faux et vrai (ou 0 et 1) ; ces opérations booléennes se définissent
au moyen de tables de vérité. Le calcul de Boole véhiculait l’idée apparemment para-
doxale, mais qui devait s’avérer spectaculaires fructueuse, que le langage logique pouvait
se définir mathématiquement et devenir un objet d’étude pour les mathématiciens. Tou-
tefois il ne permettait pas encore de résoudre les problèmes de fondements. Dès lors,
nombre de mathématiciens ont cherché à l’étendre au cadre général du raisonnement ma-
thématique et on a vu apparaître les systèmes logiques formalisés ; l’un des premiers est
dû à Frege au tournant du 20ème siècle. En 1900 au cours d’une très célèbre conférence au
congrès international des mathématiciens à Paris, David Hilbert a proposé une liste des
23 problèmes non résolus les plus importants des mathématiques d’alors. Le deuxième
était celui de la cohérence de l’arithmétique, c’est-à-dire de démontrer par des moyens
finitistes la non-contradiction des axiomes de l’arithmétique.
Le programme de Hilbert a suscité de nombreux travaux en logique dans le premier
quart du siècle, notamment le développement de systèmes d’axiomes pour les mathé-
matiques : les axiomes de Peano pour l’arithmétique, ceux de Zermelo complétés par
Skolem et Fraenkel pour la théorie des ensembles et le développement par Whitehead et
Russell d’un programme de formalisation des mathématiques. C’est également la période
où apparaissent les principes fondateurs de la théorie des modèles : notion de modèle
d’une théorie et théorvme de L´’owenheim-Skolem. En 1929 Kurt G´’odel montre dans sa
thèse de doctorat son théorème de complétude qui énonce le succès de l’entreprise de
formalisation des mathématiques : tout raisonnement mathématique peut en principe être
formalisé dans le calcul des prédicats. Ce théorème a été accueilli comme une avancée no-
table vers la résolution du programme de Hilbert, mais un an plus tard, G´’odel démontrait
le théorème d’incomplétude (publié en 1931) qui montrait irréfutablement l’impossibilité
de réaliser ce programme. Ce résultat négatif n’a toutefois pas arrêté l’essor de la logique
mathématique. Les années 1930 ont vu arriver une nouvelle génération de logiciens an-
glais et américains, notamment Alonzo Church, Alan Turing, Stephen Kleene, Haskell
Curry et Emil Post, qui ont grandement contribué à la définition de la notion d’algorithme
et au développement de la théorie de la complexité algorithmique (théorie de la calculabi-

3
lité, théorie de la complexité des algorithmes). La théorie de la démonstration de Hilbert
a également continué à se développer avec les travaux de Gerhard Gentzen qui a produit
la première démonstration de cohérence relative et a initié ainsi un programme de clas-
sification des théories axiomatiques. Le résultat le plus spectaculaire de l’après-guerre
est dê à Paul Cohen qui démontre en utilisant la méthode du forcing, l’indépendance
de l’hypothèse du continu en théorie des ensembles, résolvant ainsi le 1er problème de
Hilbert. Mais la logique mathématique subit également une révolution due à l’apparition
de l’informatique ; la découverte de la correspondance de Curry-Howard, qui relie les
preuves formelles au lambda-calcul de Church et donne un contenu calculatoire aux dé-
monstrations, va déclencher un vaste programme de recherche. La logique classique est
la première formalisation du langage et du raisonnement mathématique développée à par-
tir de la fin du 19ème siècle en logique mathématique. Appelée simplement logique à ses
débuts, c’est l’apparition d’autres systèmes logiques formels, notamment pour la logique
intuitionniste, qui a suscité l’adjonction de l’adjectif classique au terme logique.
Il est important d’avoir un langage rigoureux. La langue française est souvent ambigüe.
Prenons l’exemple de la conjonction «ou» ; au restaurant «fromage ou dessert» signifie
l’un ou l’autre mais pas les deux. Par contre si dans un jeu de carte on cherche «les as ou
les coeurs» alors il ne faut pas exclure l’as de coeur. Autre exemple : que répondre à la
question «As-tu 15 000 francs en poche ?» si l’on dispose de 20 000 francs ?
XIl y a des notions difficiles à expliquer avec des mots : par exemple la continuité
d’une fonction est souvent expliquée par «on trace le graphe sans lever le crayon». Il
est clair que c’est une définition peu satisfaisante. Voici la définition mathématique de la
continuité d’une fonction f : I −→ R en un pont x0 se traduit par :

∀ ε > 0, ∃ δ > 0, ∀ x ∈ I, |x − x0 | < δ =⇒ | f (x) − f (x0 )| < ε.

XEnfin les mathématiques tentent de distinguer le vrai du faux. Par exemple «Est-ce
qu’une augmentation de vingt pour cent, puis de trente pour cent est plus intéressante
qu’une augmentation de cinquante pour cent ?». Vous pouvez penser «oui» ou «non»,
mais pour en être sûr il faut suivre une démarche logique qui mène à la conclusion. Cette
démarche doit être convaincante pour vous mais aussi pour les autres. On parle de raison-
nement.
La logique classique est caractérisée par des postulats qui la fondent et la différencient
de la logique intuitionniste, exprimés dans le formalisme du calcul des propositions ou du
calcul des prédicats . La logique est utilisée en informatique pour modéliser de manière
formelle des ”objets” rencontrés par les informaticiens ; par exemple : Bases de données,
Bases de connaissances, Pré-post conditions d’une procédure, . . . etc. l’informaticien doit
être capable de se servir du modèle et raisonner sur celui-ci, comme la validation d’un
modèle de données, prise de décision à partir des faits et d’une base de connaissances,
preuve de correction d’une procédure/d’un programme. La logique est à la base de l’étude
des raisonnements, c’est-à-dire des déductions que l’on peut faire sur les modèles formels.
Le but de ce cours est d’étudier la base de logique mathématique (calcul propositionnel et
calcul des prédicats) ainsi que les systèmes fondamentaux de numération afin de donner
aux étudiants une base de notions qui le serviront en Informatique.

Dr. Euloge TCHAMMOU

Chapitre 1

Logique

1.1 Logique assertionnelle ou propositionelle

1.1.1 Généralités
Une assertion dans une théorie mathématique est une phrase à laquelle on peut attri-
buer une et une seule valeur de vérité, à savoir vrai (V ou 1 en abrégé) ou faux (F ou 0 en
abrégé). En d’autres termes, une assertion est un énoncé (mathématique pour ce qui nous
concerne dans ce cours) auquel on peut attribuer la valeur de vérité Vrai (V ) ou Faux (F)
mais jamais les deux à la fois (Principe du tiers exclu). Une assertion P vraie est appe-
lée proposition. Selon l’importance que l’on donne à la proposition au sein de la théorie,
celle-ci pourra aussi porter le nom de théorème, corollaire, lemme,... Un théorème est une
proposition jugée importante dans le développement de la théorie. Un corollaire est une
proposition qui est conséquence immédiate d’une proposition déjà démontrée. Un lemme
est une proposition intermédiaire utilisée au cours de la démonstration d’une ou d’autres
propositions. Les axiomes 1 sont les phrases de la théorie que l’on admet au départ comme
étant vraies. En fonction de leur importance, ils sont parfois considérés donc comme des
théorèmes, avec la particularité qu’ils ne sont pas à être démontrés. En mathématiques et
logique moderne, ils sont parfois confondus avec les postulats.
Ici, nous appelerons «Proposition» une assertion, donc un énoncé pouvant être vrai ou
faux.

Exemple 1 1. «7 est un entier naturel premier» est une proposition.

2. «13» n’est pas une proposition.
√
3. « 2 ∈ Q» est une proposition fausse.
4. «13 est un entier naturel premier» est une proposition vraie.

1.1.2 But du calcul propositionnel

Toute théorie mathématique T débute par le choix de ses axiomes ou ses postulats.
Ces propositions de base et leurs négations permettent de construire les autres assertions
de T . NotonsP la classe des propositions de la théorie T . Cette dernière évolue au fur et
à mesure de la découverte et de l’étude d’éléments de P, et de l’obtention de leurs valeurs
de vérité. En opérant sur les éléments de P on obtient encore des éléments de P, dont on

5
étudie les valeurs de vérité grâce à la définition des opérateurs de base et grâce à quelques
régles de base dites régles logiques : c’est là la démarche du calcul propositionnel dont le
but est d’étudier et de mettre en place ces règles logiques. Ce calcul étudie comment la
fausseté ou la vérité d’une assertion complexe est fonction de la fausseté ou de la vérité
des assertions élémentaires qui la composent. C’est donc un calcul bivalent n’admettant
classiquement que deux valeurs de vérité possibles desquels il se préocccupe uniquement,
sans s’intéresser du sens des propositions ou de leur contenu. Il est alors important de
connaître la syntaxe à la base de ces propositions et comment ces dernières sont évaluées.

1.1.3 Syntaxe et évaluation des propositions

Syntaxe
Les propositions (parfois appelée expressions booléennes) sont construites avec :
• des constantes booléennes que sont Vrai et Faux,
• de variables booléennes (qui peuvent prendre les valeurs Vrai ou Faux seulement),
et
• des opérateurs booléens plus souvent appelés connecteurs logiques. Ils permettent
de créer de nouvelles propositions à partir de la donnée d’une ou de plusieurs propositions.

Définition des opérateurs booléens

On distingue deux catégories d’opérateurs booléens à savoir les opérateurs booléens
unaires et les opérateurs booléens binaires.

Définition 1.1.1 (Opérateurs booléens unaires) Ce sont les opérateurs booléens prenant
un seul argument. Ils sont au nombre de quatre (04).

Id ¬
V V V F F
F V F V F
La plus connue est la négation notée. Etant donnée une proposition p, on appelle négation
de p notée ¬p ou p̄, la proposition qui est vraie lorsque p est fausse et fausse lorsque p
est vraie.

Définition 1.1.2 (Opérateurs booléens binaires) Ce sont les opérateurs booléens prenant
deux arguments. Ils sont au nombre de seize (16).

∨ ⇐ ⇒ ⇔ ∧ 6∧ 6∨
V V V V V V V V V V F F F F F F F F
V F V V V V F F F F V V V V F F F F
F V V V F F V V F F V V F F V V F F
F F V F V F V F V F V F V F V F V F
Parmi les opérateurs booléens binaires les plus utilisés, on peut citer :
X≡, ⇔ = : équivalence, égalité,
X6≡, 6⇔ = : inéquivalence, inégalité,
X¬ : négation, non,

Dr. Euloge TCHAMMOU

 X∨ : dijonction, ou,
X∧ : conjonction, et,
X⇒ : implication, si... alors,
X⇐ : conséquence.

Ordre de priorité
En tant qu’opérateurs, le tableau ci-après rend compte des règles de préséance entre
ces connecteurs logiques : l’ordre étant décroissant de gauche à droite, ceux situès dans
la même case ont la même priorité, de même qu’un opérateur et sa négation.

¬ ∧, ∨ ⇒, ⇐ ⇔, ≡

(a) Équivalence-Équivalence logique

L’opérateur ≡ est à distinguer du connecteur logique ⇔. Soient p et q deux pro-
positions. Si
• p est vrai lorsque q est vrai, et p est faux lorsque q est faux, alors on dit que
p et q sont logiquement équivalentes, et on note p ≡ q. Dans le cas contraire, on
note p 6≡ q. Par contre p et q étant des propositions, la notation p ⇔ q désigne une
proposition. La proposition p ⇔ q (lire p équivalent à q) est : vraie lorsque p et q
sont simultanément vraies ou simultanément fausses, et fausse dans tous les autres
cas.
Table de vérité
p q p⇔q
V V V
V F F
F V F
F F V
Soient x et y deux réels. Les propositions suivantes sont vraies.
• x2 ≤ 9 ⇔ (x ∈ [−3; 3]).

• x2 = y2 ⇔ (x = y ou x = −y).

• (x ≤ y) ⇔ (x = y ou x < y).
• (x ≤ 0) ⇔ (|x| = −x).
• (x ≥ 0) ⇔ (|x| = x).
(b) La disjonction ∨.
Étant données deux propositions p et q, la proposition «p ou q» notée p ∨ q est la
proposition qui est vraie lorsque l’une au moins des propositions p et q est vraie
et fausse lorque les deux propositions sont simultanément fausses.
Table de vérité
p q p∨q
V V V
V F V
F V V
F F F
Dr. Euloge TCHAMMOU
 (c) Le ou exclusif 6⇔.
Le ou exclusif (rendu par soit... soit... ; ou bien... ) s’exprime par l’utilisation de
l’inéquivalence 6⇔. Étant données deux propositions p et q, cet opérateur ne rend
la valeur vrai que lorsqu’exactement l’une des deux propositions est vraie, et, elle
est fausse dans les deux autres cas.
Table de vérité
p q p 6⇔ q
V V F
V F V
F V V
F F F
(d) La conjonction ∧.
Étant données deux propositions p et q, la proposition «p et q» notée p ∧ q est la
proposition qui n’est vraie que lorsque les propositions p et q sont simultanément
vraies. Elle est donc fausse si et seulement l’une au moins des propositions p et q
est fausse.
Table de vérité
p q p∧q
V V V
V F F
F V F
F F F
(e) L’implication =⇒.
Étant données deux propositions p et q, la proposition «p implique q» notée p =⇒
q est la proposition qui n’est fausse que lorsque la proposition p est vraie et q ne
l’est pas.
Table de vérité
p q p =⇒ q
V V V
V F F
F V V
F F V

Satisfiabilité et validité
Définition 1.1.3 Soit E une expression booléenne donnée. On dit que
. E est satisfaite dans un état si elle a la valeur vrai dans cet état.
. E est satisfiable s’il y a un état dans lequel elle est satisfaite.
. E est valide si elle est satisfaite dans tous les états.
. E est une tautologie lorsqu’elle est une expression booléenne valide.

Exemple 2 1. L’expression 2x − 5 > 0 est satisfaite dans l’état (x, 3). C’est donc
une expression satisfiable. Mais elle n’est pas valide, car n’étant pas satisfaite
dans l’état (x, 0).

Dr. Euloge TCHAMMOU

 2. Considérons deux propositions p et q. L’expression p ⇐⇒ p est une tautologie.
Par contre les expressions p ∨ q et p ∧ q sont satisfiables, mais non valides.

1.1.4 Propriétés
A XIOMES 1.1.1 - (p ⇐⇒ p) ≡ Vrai (Réflexivité).
- (p ⇐⇒ q) ≡ (q ⇐⇒ p) (Symétrie).
- (p ⇐⇒ (q ⇐⇒ q)) ≡ ((p ⇐⇒ q) ⇐⇒ r) (Associativité). On écrit alors simplement
p ⇐⇒ q ⇐⇒ r.

P ROPRIÉTÉS 1.1.1

Dr. Euloge TCHAMMOU

Chapitre 2

A RITHMÉTIQUE .

La théorie des nombres est l’étude ( des propriétés ) des nombres en occurrence les
entiers.

Rappel
— L’ensemble des entiers est noté Z = {· · · , −3, −2, −1, 0, 1, 2, 3, · · · } ;
— L’ensemble des entiers naturels est noté N = {0, 1, 2, 3, · · · }
NB : Z est aussi appelé "ensemble des entiers relatifs" et alors N est "l’ensemble des
entiers relatifs positifs".

2.1 Divisibilité dans les entiers

D ÉFINITION 2.1.1
Soient a et b 6= 0 deux entiers.
On dit que a est un multiple de b ou que b est un diviseur( ou un facteur) de a s’il existe
un entier k tel que a = b · k.
— On note b|a pour signifier que "b 6= 0 divise a" ;
— L’ensemble des multiples d’un entier a est l’ensemble noté
|a|Z = {· · · , −3a, −2a, −a, 0, a, 2a, 3a, · · · }.

P ROPRIÉTÉS 2.1.1
1. Tout entier non nul divise 0 (zéro).
2. 1 divise tout entier.
3. Tout entier non nul est divisible par lui-même.

Preuve.
1. Il suffit d’écrire 0 = a × 0 ∀ a ∈ Z∗
2. Ici il suffit d’écrire a = a × 1 ∀a∈Z
3. Il se déduit de 2.

P ROPRIÉTÉS 2.1.2
Soient a, b c et d des éléments de Z∗ ( entiers non nuls).

10
 1. Si a|b et b|c alors a|c ( transitivité).
2. Si a|b alors |a| ≤ |b|.
3. Si a|b et b|a alors a = ± b (antisymétrie).
4. Si a|b, a|c alors a| mb + nc pour tout (m, n) ∈ Z2 .
5. Si a|b et c|d alors ac|bd

Preuve.
1. Supposons a|b et b|c.
Alors il existe (t,t 0 ) ∈ Z∗ × Z∗ tels que b = at et c = bt 0 . Ainsi, c = (at)t 0 = a(tt 0 ).
D’où le résultat.
2. a|b implique qu’il existe t ∈ Z∗ tels que b = at et |b| = |a| · |t|. D’où le résultat.
3. D’après la transitivité, on a : a = a(tt 0 ) pour un certain (t,t 0 ) ∈ Z∗ × Z∗ . Donc
tt 0 = 1 c’est-à dire t 0 = t ∈ {−1, 1}. D’où le résultat.
4. a|b et c|d alors il existe (t,t 0 ) ∈ Z∗ × Z∗ tels que b = at et d = ct 0 . Donc bd =
(at)(ct 0 ) = ac(tt 0 ).

E XERCICE 1 Soient n et d deux entiers tels que d divise 5n + 4 et 8n − 5.

1. Justfier que d divise 53.
2. En déduire les valeurs possibles de d.

E XERCICE 2
On considère le nombre An = n(n + 1)(n + 2), n ∈ Z.
1. Justifier que 2|An , pour tout n ∈ Z.
2. Pour n pair, An est-il divisible par 8 ?

Théorème 2.1.1 (Algorithme de division)

Soient a et b deux entiers avec b > 0.
Il existe un unique couple d’entiers (q, r) tel que a = b · q + r avec 0 ≤ r < b

NB : On dit qu’on a éffectué la division euclidienne de a par b.

— a est le dividende ;
— b le diviseur ;
— q le quotient ;
— r le reste
Preuve. Nous allons procéder en deux étapes.
1ère étape : Supposons que a ≥ 0.
0 = 0 · b + 0. On peut alors considérer a > 0.
L’ensemble bN n’est pas majoré alors il existe n ∈ N tel que a < bn. a > 0 et N est
minoré alors A = {n ∈ N, bn > a} n’est pas vide et possède un plus pétit élément k > 0.
On a k − 1 ∈ N et k − 1 ∈/ A ainsi b(k − 1) ≤ a < bk. On prend q = k − 1 et r = a − bq.
Unicité :
Si a = bq + r = bq0 + r0 avec 0 ≤ r < b et 0 ≤ r0 < b alors −b < r − r0 < b et r − r0 =
b(q − q). Donc r = r0 car r − r0 est un multiple de b strictement contenu dans ] − b, b[. Et
0

puisque b 6= 0 on obtient q = q0 .

Dr. Euloge TCHAMMOU

 2ème étape : Supposons que a < 0.
On a −a > 0 et d’après ce qui précède, il existe un unique (q, r) ∈ N2 tel que −a = bq + r
avec 0 ≤ r < b. Ce qui implique que a = b(−q)−r = b(−q−1)+b−r. On a 0 ≤ b−r < b
alors on prend le couple (−q − 1, b − r) dont l’unicité vient de celui de (q, r).

C OROLLAIRE 2.1.1 (A LGORITHME DE DIVISION )

Soient a et b deux entiers avec b 6= 0.
Il existe un unique couple d’entiers (q, r) tel que a = b · q + r avec 0 ≤ r < |b|

E XERCICE 3
Compléter le tableau suivant.
Dividende Diviseur Quotient Reste
25 7
32 -3
-48 9
-38 -5
15 21
-8 10

E XERCICE 4
Soit a un entier.
1. Quels sont les restes possibles dans la division euclidienne de a par 4.
2. Prouver que si a est impair alors 8 divise a2 − 1.

D ÉFINITION 2.1.2 ( N OMBRES AMIABLES )

On dit que deux entiers sont amis (ou amiables) si la somme des diviseurs positifs autres
que lui-même de chacun de ces deux nombres est égale à l’autre nombre.

E XEMPLE 2.1.1
Les nombres 220 et 284 sont amiables.

E XERCICE 5 Prouver que

(a) 1 184 et 1 210 sont amiables.
(b) 2 620 et 2 924 sont amiables.

D ÉFINITION 2.1.3 (N OMBRES PARFAITS )

Un nombre parfait, est un entier naturel qui est égal à la somme de ses diviseurs stricts.

E XEMPLE 2.1.2
Les nombres 6 et 28 sont parfaits.

D ÉFINITION 2.1.4 (N OMBRES T RIANGULAIRES )

n(n+1)
Un nombre triangulaire, est un entier naturel de la forme Tn = 2 où n > 0 est un
entier.

D ÉFINITION 2.1.5 (N OMBRES DE T HABIT )

Un nombre de Thabit, est un entier naturel de la forme Kn = 3 × 2n − 1 où n > 0 est un
entier.

Dr. Euloge TCHAMMOU

Remarque 2.1.1
Un nombre de Thabit en binaire se présente sous la forme : 10 1| ·{z
· · 1}.
nfois
Par exemple, K3 = 2310 = 101112 .

E XERCICE 6
1. Citer 4 nombres triangulaires plus grands que 6.
2. Justifier que les nombres 496 et 8128 sont parfaits.
3. Démontrer qu’un entier naturel pair est parfait si et seulement s’il est de la forme
2n−1 (2n − 1), avec n ∈ N, 2n − 1 premier.
4. Justifier que sont amiables.

2.2 Plus grand commun diviseur, Plus pétit commun mul-

tiple
2.2.1 Définitions et propriétés
Théorème 2.2.1
Soient a et b deux entiers.
Il existe un unique entier positif µ vérifiant : ∀ n ∈ Z, a|n et b|n ⇔ µ|n

Preuve. Soient a et b deux entiers. aZ ∩ bZ est un idéal de Z, donc principal. Ainsi il

existe µZ tel que aZ ∩ bZ = µZ. On prend µ ∈ N car µZ = (−µ)Z.
S’il existe µ 0 ∈ N tel que µ 0 Z = aZ ∩ bZ alors on a µ|µ 0 et µ 0 |µ ; donc µ = ±µ 0
d’après la proposition 2.1.2. On obtient donc µ = µ 0 car ils sont tous positifs.
Soit n ∈ Z.
a|n et b|n ⇔ n ∈ aZ ∩ bZ = µZ. D’où µ|n

D ÉFINITION 2.2.1
L’entier µ est le plus pétit commun multiple positif de a et b. On le note ppcm(a, b).

Théorème 2.2.2
Soient a et b deux entiers.
Il existe un unique entier positif δ qui satisfait à : ∀ d ∈ Z, d|a et d|b ⇔ d|δ

Preuve. Soient a et b deux entiers. aZ + bZ est un idéal de Z alors il existe δ N tel que
aZ + bZ = δ Z. L’unicité de δ se montre de la même manière que celle de µ précédente.
Soit dZ∗ .

d|a et d|b ⇔ d|(au + bv), ∀(u, v) ∈ Z2 ( d’après 2.1.2).

⇔ aZ + bZ = δ Z ⊂ dZ
⇔ d|δ

D ÉFINITION 2.2.2
L’entier δ est le plus grand commun diviseur de a et b. On le note pgcd(a, b) ou a ∧ b.

Dr. Euloge TCHAMMOU

E XEMPLE 2.2.1
Soient a ∈ Z∗ .
pgcd(a, 0) = |a|, pgcd(a, 1) = 1, ppcm(a, 0) = 0, ppcm(a, 1) = |a|, ppcm(−3, 4) =
12

P ROPRIÉTÉS 2.2.1
Soient a, b, et c des entiers.
1. ppcm(ac, bc) = |c| · ppcm(a, b).
2. pgcd(ac, bc) = |c| · pgcd(a, b).
3. ppcm(a, b) · pgcd(a, b) = |ab|.

Proposition 2.2.1 ( Algorithme d’Euclide)

Soient a et b deux entiers tels que |a| > |b|.
— Si b = 0 alors pgcd(a, b) = pgcd(a, 0) = |a|.
— Si b 6= 0 alors pgcd(a, b) = pgcd(b, r), où r est le reste de la division euclidienne
de a par b.
L’algorithme d’Euclide consiste à réitérer la deuxième formule jusqu’à ce que l’on tombe
sur un reste nul puis on applique la première formule.

Remarque 2.2.1 (Principe)

Soient a et b deux entiers (|b| < |a|).
Si a n’est pas un multiple de b alors il existe un entier positif k et les entiers q1 , · · · , qk , r1 , · · · , rk
pour que :

a = q1 · b + r1 , 0 < r1 < |b|

b = q2 · r1 + r2 , 0 < r2 < r1
r1 = q3 · r2 + r3 , 0 < r3 < r2
.. ..
. .
rk−3 = qk−1 · rk−2 + rk−3 , 0 < rk−3 < rk−2
rk−2 = qk · rk−1 , rk = 0

E XERCICE 7
1. Détermine ppcm(6, −15, 33), pgcd(−6, −15) et pgcd(6, −15, 35).
2. Applique l’Algorithme d’Euclide pour trouver le pgcd de 2772 et 390.

2.2.2 Résolution d’équations diophantiennes linéaires

D ÉFINITION 2.2.3
Une équation diophantienne linéaire est une équation polynomiale de degré 1 à coéffi-
cients entiers et dont les solutions sont entières. Elle est de la forme a1 x1 + a2 x2 + · · · +
an xn = k avec k ∈ Z∗ et les ai (1 ≤ i ≤ n) des entiers donnés.

E XEMPLE 2.2.2
3x + 2y = 3, 64x + 108y = 2

Théorème 2.2.3
Soient a, b des entiers non nuls.

Dr. Euloge TCHAMMOU

 1. Il existe d’entiers (x, y) solution de l’équation diophantienne ax +by = pgcd(a, b).
2. Soit k ∈ Z. L’équation ax + by = k est résoluble en entiers si et seulement si
pgcd(a, b) divise k.

Preuve.

E XEMPLE 2.2.3
Résolvons dans Z, l’équation 803x + 154y = pgcd(803, 154)
— Nous déterminons d’abord pgcd(803, 154) par l’algorithme d’Euclide. On a :

803 = 5 × 154 + 33
154 = 4 × 33 + 22
33 = 1 × 22 + 11
22 = 2 × 11 + 0 donc pgcd(803, 154) = 11

— L’équation devient
803x + 154y = 11.
En reprenant la technique inverse de l’algorithme d’Euclide, on a :

11 = 33 − 1 × 22
= 33 − 1 × (154 − 4 × 33) = 5 × 33 − 154
= −154 + 5 × (803 − 5 × 154) =
= 5 × 803 − 26 × 154

D’où (x0 , y0 ) = (5, −26) est solution. On déduit toutes les solutions à partir de
cette solution.

E XERCICE 8
Résoudre les équations diophantiennes suivantes.
1. 64x + 108y = 4
2. 64x + 108y = 1
3. 52x + 18y = 24

2.3 Entiers relativement premiers

2.3.1 Définitions et propriétés
D ÉFINITION 2.3.1
Deux entiers a et b sont dit premiers entre eux (ou relativement premiers) si et seulement
si pgcd(a, b) = 1

Remarque 2.3.1
pgcd(a, b) = 1 ⇔ aZ + bZ = Z

Dr. Euloge TCHAMMOU

Théorème 2.3.1 (Bézout)
Pour tous entiers a et b, on a : pgcd(a, b) = 1 ⇔ ∃ (u, v) ∈ Z2 , au + bv = 1

Preuve. On sait aZ + bZ = δ Z avec δ = pgcd(a, b)

pgcd(a, b) = 1 ⇔ aZ + bZ = Z
⇔ aZ + bZ =< 1 >
⇔ ∃(u, v) ∈ Z2 , au + bv = 1.

Théorème 2.3.2 (Gauss)

a|bc et pgcd(a, b) = 1 alors a|c

Preuve. a|bc implique qu’il existe t ∈ Z tel que bc = at. Or pgcd(a, b) = 1 ⇔ ∃ (u, v) ∈
Z2 , au + bv = 1.

au + bv = 1 ⇒ tau + tbv = t
⇒ bcu + tbv = t
⇒ ab(cu + tv) = at = bc
⇒ a(cu + tv) = c car Z a la propriété de simplification

D’où le résultat.

Théorème 2.3.3
(a|c et b|c et pgcd(a, b) = 1 ) alors ab|c

Preuve. a|c et b|c implique qu’ils existent t et t 0 tel que c = at = bt 0 alors b divise at donc
b|t car pgcd(a, b) = 1 (d’après ce qui précède). Il existe alors t1 ∈ Z tel que t = bt1 . Ainsi
c = abt1 , d’où ab|c

2.4 Les nombres premiers

2.4.1 Définitions
D ÉFINITION 2.4.1
On dit qu’un entier p > 1 est premier s’il admet exactement deux diviseurs positifs dis-
tincts ( 1 et lui-même).

E XEMPLE 2.4.1
2, 3, 5, 7, 11, 13, 17, 19, · · ·

D ÉFINITION 2.4.2
Un entier naturel qui n’est pas premier est dit composé.

D ÉFINITION 2.4.3 (N OMBRES PREMIERS JUMEAUX )

Deux nombres premiers p et q, (p < q), sont dits jumeaux si q = p + 2. On note (p, q)
couple de nombres premiers jumeaux.

Dr. Euloge TCHAMMOU

E XEMPLE 2.4.2
On a les premiers nombres premiers jumeaux suivants (3, 5), (5, 7), (11, 13), (17, 19),
(29, 31).

Remarque 2.4.1
Hormis la distance entres la paire de nombres premiers {2; 3}, la distance |p − q| = 2 est
la plus petite distance possible entre deux nombres premiers p et q.

D ÉFINITION 2.4.4 (P REMIER CIRCULAIRE )

Un nombre premier circulaire est un nombre premier qui reste premier en permutant
circulairement ses chiffres

E XEMPLE 2.4.3
Les nombres premiers suivants sont circulaires : 37, 131, 199.

D ÉFINITION 2.4.5 (P REMIER PRESQUE CIRCULAIRE )

Un nombre premier presque circulaire est un nombre premier dont toutes les permutations
sont des nombres premiers, sauf une.

E XERCICE 9
L’entier 1193 est-il un nombre premier circulaire ? un nombre premier presque circu-
laire ? Justifier votre réponse.

2.4.2 Propriétés
Théorème 2.4.1 (Euclide)
L’ensemble des entiers premiers est infini.

Preuve. Soit P l’ensemble des nombres premiers. On a P 6= 0.

/
Supposons que P est fini avec P = {p1 , · · · , pk }.
k
L’entier a = 1 + ∏ pi est superieur à 2, donc admet un diviseur premier p j ∈ P. Alors
 i=1 
k
p j divise 1 = a − ∏ pi ce qui est impossible. D’où le résultat.
i=1

Théorème 2.4.2 (Euclide)

Tour entier n supérieur ou égal à 2 a au moins un diviseur premier.

Preuve. Pour tout entier n ≥ 2 l’ensemble Dn des diviseurs strictement positifs de n a

au moins deux éléments, 1 et n ; donc Dn \ {1} est non vide dans N \ {0, 1} et il admet
un plus petit élément p qui est nécessairement premier. En effet si p n’est pas premier il
admet un diviseur q tel que 2 < q < p avec q qui divise n, ce qui contredit le caractère
minimal de p.

C OROLLAIRE 2.4.1
Tout entier relatif n ∈ Z \ {−1, 0, 1} a au moins un diviseur premier.

Preuve. Tout diviseur premier de |n| ≥ 2 convient. Un entier naturel non premier s’écrit
donc n = pq avec p ≥ 2 premier q un entier relatif.

Dr. Euloge TCHAMMOU

Remarque 2.4.2
Le Corollaire ci-dessus est aussi enoncé comme suit :
Tout entier composé admet au moins un facteur premier.

Un diviseur premier de n ≥ 2, est nécessairement inférieur ou égal à n.√En fait, pour

n non premier, on peut toujours en trouver un qui est inférieur ou égal à n, c’est p =
min (Dn \ {1}).

P ROPRIÉTÉ 2.4.1
supérieur ou égal à 2 qui est composé a au moins un diviseur premier p tel
Tout entier n √
que 2 ≤ p ≤ n.

Preuve. En supposant n composé et en gardant les notations de la démonstration du théo-

rème précédent, on a vu que p = min (Dn \ {1}) est un diviseur premier de n. On a donc
n = pq avec 2 ≤ q ≤ n (on a q 6= 1 puisque n√n’est pas premier) et q ∈ Dn \ {1}, ce qui
implique que p ≤ q et p2 ≤ pq = n, soit p ≤ n.

E XERCICE 10
√
Prouver que le nombre p est irrationnel pour tout entier premier p.

Proposition 2.4.1
Soit p un entier naturel premier. Pour tout entier naturel non nul n, on a soit p divise n,
soit p premier avec n.

Preuve. Comme δ = gcd(p, n) divise p, on a soit δ = p et p divise n, soit δ = 1 et p est

premier avec n.

Proposition 2.4.2
Deux nombres premiers distincts sont premiers entre eux.

Preuve. Facile

Proposition 2.4.3
Un entier p ≥ 2 est premier si, et seulement si, il est premier avec tout entier compris
entre 1 et p − 1.

Preuve. Si p est premier, comme il ne divise pas k ∈ {1, · · · , p − 1}, il est premier avec k.
Réciproquement si p n’est pas premier, il s’écrit alors p = ab avec a ≥ 2, b ≥ 2 et p n’est
pas premier avec a ∈ {1, · · · , p − 1}

Proposition 2.4.4
Tout couple de nombres premiers jumeaux, à l’exception du couple (3, 5), est de la forme
(6n − 1, 6n + 1) pour un certain entier n.

Preuve. En effet, tout triplet d’entiers consécutifs comporte au moins un multiple de

2 (éventuellement deux) et un seul multiple de 3 ; l’entier qui se trouve entre les deux
nombres premiers jumeaux est à la fois ce multiple de 2 et ce multiple de 3, car cela ne
peut pas être l’un des nombres premiers.

Dr. Euloge TCHAMMOU

E XERCICE 11
Trouver 7 couples de nombres premiers jumeaux.
Théorème 2.4.3 (fondamental de l’Arithmetique)
Tout entier |a| ≥ 2 non premier peut s’écrire comme un produit de nombres premiers.
Cette décomposition est unique à l’ordre des facteurs près.
C’est-à dire qu’il existe une collection unique de nombres premiers p1 , p2 , · · · , pk et
d’entiers positifs α1 , α2 , · · · , αk tel que a = ± pα1 1 pα2 2 · · · pαk k
Preuve. On démontre tout d’abord l’existence d’une telle décomposition par récurrence
sur a ≥ 2.
Pour a = 2, on a déjà la décomposition.
Supposons le résultat acquis pour tout entier k compris entre 2 et a ≥ 2.
Si a + 1 est premier, on a déjà la décomposition, sinon on écrit a + 1 = pq avec p et q
compris entre 2 et a et il suffit d’utiliser l’hypothèse de récurrence pour p et q.
L’unicité d’une telle décomposition peut aussi se montrer par récurrence sur a ≥ 2. Le
résultat est évident pour a = 2.
Supposons le acquis pour tout entier k compris entre 2 et a ≥ 2.
Si a + 1 a deux décompositions :
β β β
a + 1 = pα1 1 × pα2 2 · · · pαr r = q1 1 × q2 2 · · · qs s
où les pi [resp. q j ] sont premiers deux à deux distincts et les αi [resp. β j ] entiers naturels
β β β
non nuls.L’entier p1 est premier et divise le produit q1 1 × q2 2 · · · qs s , il divise donc néces-
sairement l’un des qk . L’entier qk étant également premier la seule possibilité est p1 = qk
. En simplifiant par p1 on se ramène à la décomposition d’un entier inférieur ou égal à a
et il suffit alors d’utiliser l’hypothèse de récurrence pour conclure.
E XERCICE 12
Montrer que si n > 4 est un entier composé alors n divise (n − 1)!.
P ROPOSITIONS 2.4.1 (U TILITÉ DE DÉCOMPOSITION AU CALCUL DE PPCM , PGCD )
Soient a et b deux entiers composés dont les décompositions en facteurs premiers sont :
k k β
a = ± ∏ pαi i et b = ± ∏ pi i où les αi et βi sont des entiers naturels.
i=1 i=1
k max(αi ,βi ) k min(αi ,βi )
Alors ppcm(a, b) = ∏ pi et pgcd(a, b) = ∏ pi
i=1 i=1

E XEMPLE 2.4.4
1. 2016 = 25 · 32 · 7, 2160 = 24 · 33 · 5. On a :
ppcm(2160, 2016) = 25 · 33 · 5 · 7 et pgcd(2160, 2016) = 24 · 32 .
2. On utilise aussi la décompositions en facteurs premiers pour déterminer le nombres
de diviseurs positifs d’un entier.
On peut déterminer celui de 308 = 22 · 7 · 11 via un arbre de dénombrement.
C OROLLAIRE 2.4.2
Si a est un entier composé de factorisation (ou décomposition) a = ± ps11 ps22 · · · pskk alors
le nombre de ces diviseurs positifs est :
(s1 + 1)(s2 + 1) · · · (sk + 1)

Dr. Euloge TCHAMMOU

Théorème 2.4.4
Soit p un entier premier
1. ∀ a ∈ Z, pgcd(a, p) = 1 ou pgcd(a, p) = p.
2. ∀ (a, b) ∈ Z2 , si p|ab alors p|a ou p|b.
3. Soient p1 , p2 , · · · , pk des entiers premiers.
Si p|p1 p2 · · · pk alors ∃ j ∈ {1, 2, · · · , k} tel que p = p j .

E XERCICE 13
1. Déterminer le nombres de diviseurs positifs de chacun des nombres 2016, 1056 et
1119.
2. Déterminer ppcm(2016, 1056 ) et pgcd(4032, 2 × 1119).

E XERCICE 14
Soit k, m et n des entiers tel que gcd(m, n) = 1.
On suppose qu’un nombre premier p > 2 divise gcd(km2 + 4, kn2 − 4).
Justifier que p ne divise aucun des entier k, m et n.

2.5 Quelques familles de nombres premiers

2.5.1 Les grands nombres premiers
Les grands nombres premiers trouvés sont pour la plupart les nombres de Mersenne
ou celui de Fermat.

D ÉFINITION 2.5.1 (L ES NOMBRES DE F ERMAT )

n
Un nombre de Fermat est tout entier de la forme Fn = 22 + 1 où n est un entier naturel.

E XEMPLE 2.5.1
7 8
F0 = 3, F1 = 5, F2 = 17, F3 = 257, F4 = 65537, F7 = 22 + 1, F8 = 22 + 1, · · · .

Remarque 2.5.1 (Euler)

Tous les nombres de Fermat ne sont pas premiers :

F5 = 4294967297 = 641 × 6700417,

F6 = 18446744073709551617 = 274177 × 67280421310721.

D ÉFINITION 2.5.2 ( L ES NOMBRES DE M ERSENNE )

Les nombres de Mersenne sont les entiers Mn de la forme 2n − 1.

E XEMPLE 2.5.2
M2 = 3, M3 = 7, M4 = 15, M5 = 31, M6 = 63, M7 = 127, M8 = 255, · · · .

Attention
Tous les nombres de Mersenne ne sont pas premiers : M8 = 3 × 5 × 17, M11 = 2047 =
23 × 89, · · · .

Dr. Euloge TCHAMMOU

E XEMPLE 2.5.3
Le plus grand nombre de Mersenne premier connu ce jour 07-Dec-2018 est 282589933 − 1,
24862048 chiffres. C’est le 51ème trouver jusque là.Pour plus informatique voir le site
GIMPS (Great Internet Mersenne Prime Search) [5].
Les nombres de Fermat premiers record sont disponible sur le site [6].

E XERCICE 15
1. Justifier qu’un entier x est un nombre de Fermat si et seulement si ln(ln(x−1))−ln(ln
ln 2
2)
∈
N.
2. L’entier dont l’écriture hexadécimale est 8 · 1015 est-il un nombre de Fermat ?

E XERCICE 16
Soient a ≥ 2, m ≥ 2 deux entiers et p = am − 1.
1. Montrer que si p est premier alors a = 2 et m est premier.
2. La réciproque est-elle vraie ?

E XERCICE 17 (N OMBRES PARFAITS PAIRS )

Soit n un entier premier.
1. Justifier que si 2n − 1 est premier alors le nombre 2n−1 (2n − 1) est un nombre
parfait.
2. Donner alors cinq nombres parfaits.

2.5.2 Les premiers de Sophie Germain

D ÉFINITION 2.5.3
Un nombre premier p est appelé nombre premier de Sophie Germain si 2p + 1 est aussi
un nombre premier. Dans ce cas, 2p + 1 est appelé nombre premier sûr.

E XEMPLE 2.5.4
2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, · · · sont des nombres premiers de Sophie
Germain.

E XERCICE 18
Les nombres suivants : 59, 179, 491, 983, 1103, 1223, 1259, 1289, 1397. sont-ils
1. des premiers de Sophie Germain ? Justifier.
2. des premiers sûr ? Justifier.

Remarque 2.5.2
Le premiers de Sophie Germain record, en 2016, est 2 618 163 402 417 × 21290000 − 1 [4],
les deux nombres possèdent 388 342

Il y a une Conjecture qui dit qu’il existe une infinité de nombres premier de Sophie
Germain

D ÉFINITION 2.5.4 (C HAÎNE DE C UNNINGHAM )

Une suite {p, 2p + 1, 2(2p + 1) + 1, · · · } de nombres premiers de Sophie Germain est
appelée une chaîne de Cunningham de première espèce.

Dr. Euloge TCHAMMOU

E XEMPLE 2.5.5
L’ensemble (ordonné) {2, 5, 11, 23, 47} est une chaîne de Cunningham.

Remarque 2.5.3
Dans une chaîne de Cunningham, à l’exception du premier élément et du dernier élément,
chaque élément est à la fois un nombre premier de Sophie Germain et un nombre premier
sûr. Le premier élément dans la chaîne est un nombre premier de Sophie Germain et le
dernier un nombre premier sûr.

E XERCICE 19
Donner deux chaînes de Cunningham.

2.5.3 Les factoriels et primoriels premiers

D ÉFINITION 2.5.5 ( FACTORIELLE PREMIÈRE )
Un nombre premier de la forme n! + 1 ou n! − 1 est appelé factorielle première.

E XEMPLE 2.5.6

1. L’entier n! + 1 est premier pour n = 1, 2, 3, 11, 27, 37, 41, · · ·

2. L’entier n! − 1 est premier pour n = 3, 4, 6, 7, 12, 14, 30, 32, · · ·

D ÉFINITION 2.5.6
Soit p un nombre premier. Le primoriel p est l’entier défini par p# = 2 × 3 × 5 × 7 × · · · ×
p.

D ÉFINITION 2.5.7 ( PRIMORIELLE PREMIÈRE )

Une primorielle première est un nombre premier de la forme p# + 1 ou p# − 1.

E XEMPLE 2.5.7

1. L’entier p# + 1 est premier pour p = 2, 3, 5, 7, 11, 31, · · ·

2. L’entier p# − 1 est premier pour p = 3, 5, 11, 13, 41, · · ·

2.6 Production des nombres premiers

Une façon naïve de produire tous les nombres premiers plus petit qu’un entier N fixé
à l’avance, consiste à mettre en oeuvre le crible d’Eratosthène : on écrit tous les entiers
inférieur ou égal à N puis on supprime tous les multiples de 2 qui sont supérieur à
2, puis les multiples de 3 qui sont supérieur à 3 ; et ainsi de suite. À chaque étape, on
sélectionne le premier nombre non barré strictement supérieur au nombre premier dont
on vient de supprimer tous les multiples : celui-ci est un nombre premier. La liste obtenue
est celle de tous les premiers inférieur ou égal à N.
Bien entendu l’algorithme proposé n’est pas efficace, on en cherche d’autres. En outre
on peut aussi s’intéresser aux problématiques suivantes :
— comment produire de nombreux nombres premiers ?
— comment battre le record du monde du plus grand nombre premier ?

Dr. Euloge TCHAMMOU

2.6.1 A partir les nombres de Fermat et/ou de Mersennes
P ROPRIÉTÉ 2.6.1
Fn −1
Soit n ∈ N∗ . Le nombre de Fermat fn est premier si et seulement si Fn divise 1 + 3 2 .

La preuve utilise des notions qui ne sont pas encore vu.

P ROPRIÉTÉ 2.6.2
Soit n ≥ 2 un entier. Si le nombre de Mersenne Mn = 2n − 1 est premier alors n est un
nombre pemier.

Preuve. Elle repose sur l’identité x pq − 1 = (xq − 1)(xq(p−1) + · · · + xq + 1)

La réciproque de cette proposition est fausse comme le montre 211 − 1 = 23 × 89.

2.6.2 Formules de nombres premiers

Les formules existantes pour la génération de nombres premiers utilisent la fonction
partie entière notée ici par b•c. Elle est donner par : ∀ x ∈ R,

bxc = {n ∈ Z; n ≤ x < n + 1}.

Théorème 2.6.1 (Roland Yéléhada et Minac )

Pour tout n ∈ N,   
(n + 1)! + 1 (n + 1)!
t(n) = 2 + n −
n+2 n+2
donne toujours un nombre premier.

Plus précisément, si on enlève le nombre 2 dans la suite (t(n))n∈N , on obtient la liste

des nombres premiers dans l’ordre croissant.

Théorème 2.6.2 (Minac et Willans en 1995)

Soit m ≥ 2 un entier. On pose π(1) = 0
m   
( j − 1)! + 1 ( j − 1)
π(m) = ∑ −
j=2 j j

alors le n-ème nombre premier pn est donné par

n
$ 1/n %
2
n
pn = 1 + ∑ .
m=1 1 + π(m)

Il existent d’autres formules telles que celle de Ruiz, (en 2000) et la tentative par une
suite récurrente de Rowland, (en 2008). Mais comme on peut le constater avec celles
données ci-dessus ces formules sont aussi lourde pour manipulation.

Dr. Euloge TCHAMMOU

2.6.3 Nombres premiers dans une progressions Arithmetique
Théorème 2.6.3 (Dirichlet, 1842)
Soit k et l deux entiers strictement positifs premiers entre eux. La suite (l +nk)n≥1 contient
une infinité de nombres premiers

E XEMPLE 2.6.1
Considerons la suite (un )n≥1 où un = 3n + 1.
Les nombres premiers 7, 13, 19, 31, · · · sont des éléments de cette suite.

Théorème 2.6.4 (Dirichlet en 1842)

Soit π(x, k, l) le cardinal de l’ensemble

{p, premier/ p ≤ x et p ≡ 1 (mod k)}.

Alors pour x assez grand on a

x
π(x, k, l) ∼ .
ϕ(k) log x
Recherches
1. Trouver s’ils existent d’autres types de nombres premiers (avec propriétés parti-
culières). Par exemple les nombres premiers de Woodall ?
2. La suite (n2 + 1)n≥1 contient-elle une infinité de nombres premiers ?
3. Nombres économes, équidistants et prodigues.
Ecrivez des programme non coûteux en temps (consistant) pour généner ces types de
nombres ! ! !

2.7 T HÉORIE DES C ONGRUENCES

Etant donné un entier n ≥ 2, l’arithmétique modulo n consiste à faire des calculs sur
les restes dans la division euclidienne des entiers par n.

2.7.1 La congruence modulo

D ÉFINITION 2.7.1
Soient a, b des entiers et n un entier naturel non nul.
Si n divise a − b, on dit que a est congru à b modulo n et on écrit a ≡ b (mod n).
Dans le cas contraire, on dit que a est non congru à b modulo n et on écrit a 6≡ b
(mod n)

E XEMPLE 2.7.1
100 ≡ 9 (mod 13), 2022 ≡ 2 (mod 10), 3341 ≡ 2 (mod 7).

E XEMPLE 2.7.2 ( UNE UTILITÉ )

1. Je me couche à 22h00 et je dors pendant 07h. Quelle heure sera t-il au réveil ?
2. Aujourd’hui on est mardi (2ème jour de la semaine). Quel jour sera-t-on dans 65
jours ?

Dr. Euloge TCHAMMOU

P ROPRIÉTÉS 2.7.1 (Relation d’équivalence)
Soient a, b et c des entiers et n un entier naturel non nul.
1. a ≡ a (mod n). On dit que la relation de congruence modulo n est réflexive.
2. Si a ≡ b (mod n), alors b ≡ a (mod n). On dit que la relation de congruence
modulo n est symétrique.
3. Si a ≡ b (mod n) et b ≡ c (mod n), alors a ≡ c (mod m). On dit que la relation
de congruence modulo n est transitive.

On résume la propriété précédente en disant que la relation de congruence modulo n dans

Z est une relation d’équivalence. De façon générale une relation d’équivalence sur un
ensemble non vide E est une relation binaire sur E qui est à la fois réflexive, symétrique
et transitive :
(a) ∀ a ∈ E, aRa (réflexivité).
(b) ∀ (a, b) ∈ E 2 , aRb =⇒ bRa (symétrie).
(c) ∀ (a, b, c) ∈ E 3 , (aRb) ∧ (bRc) =⇒ aRc (transitivité).

P ROPRIÉTÉS 2.7.2 (Compatibilité avec l’addition et la multiplication dans Z)

Soient a, b, c, d des entiers et n un entier naturel non nul.
1. Si a ≡ b (mod n) et c ≡ d (mod n) alors a + c ≡ b + d (mod n). On dit que la
relation de congruence modulo n est compatible avec l’addition dans Z.
2. Si a ≡ b (mod n) et c ≡ d (mod n) alors ac ≡ bd (mod n). On dit que la relation
de congruence modulo n est compatible avec la multiplication dans Z.

Remarque 2.7.1 Pour tous entiers a et b et pour tous entiers naturels non nuls n et k, on
a:
(a ≡ b (mod n)) =⇒ ak ≡ bk (mod n) .

P ROPRIÉTÉS 2.7.3
Soient a, b, c, d des entiers et n un entier naturel non nul.
1. Si a ≡ b (mod n) et d divise n, d > 0, alors a ≡ b (mod d)
2. Si a ≡ b (mod n) alors ac ≡ bc (mod nc) pour tout entier c > 0.
3. Soit f est une fonction polynomiale à coefficients entiers.
Si a ≡ b (mod n) alors f (a) ≡ f (b) (mod n)
4. Si (n1 , n2 , · · · , nk ) est une famille d’entiers naturels non nuls et a ≡ b (mod ni )
pour tout i ∈ {1, 2, · · · , k}, alors a ≡ b (mod ppcm(n1 , n2 , · · · , nk ))
5. Si a ≡ b (mod n), alors pgcd(a, n) = pgcd(b, n).

Théorème 2.7.1 (Loi d’annulation)

m
1. ax ≡ ay (mod m) ⇔ x ≡ y (mod pgcd(a,m) )
2. Si ax ≡ ay (mod m) et pgcd(a, m) = 1 ⇒ x ≡ y (mod m)

E XERCICE 20
1. Déterminer le dernier chiffre (chiffre des unités) du nombre 720 .

Dr. Euloge TCHAMMOU

 2. Montrer que 220 ≡ 1 (mod 41)
19
3. Déduire que 41 divise ∑ 2k .
k=0

E XERCICE 21
Le R.I.B. (Relevé d’Identité Bancaire) est un nombre constitué de gauche à droite de la
façon suivante :
Code de la banque Code du guichet Numéro de compte clé
| {z }| {z }| {z } | {z }
5 chiffres 5 chiffres 11 chiffres 2 chiff
Pour calculer la clé de contrôle d’un RIB, on considère le nombre a formé par les 21
premiers chiffres ; on calcule le reste r de la division euclidienne de N = 100 × a par 97 ;
la clé R.I.B est 97 − r.
Soit le RIB (incomplet)
Code de la banque Code du guichet Numéro de compte clé
12345 25896 35715942681 ? .

1. Soit n ∈ {2, · · · , 19}. Donner dans un tableau les restes des divisions euclidiennes
de 10n par 97.
2. Calculer la clé de contrôle d’un RIB.

2.7.2 Classes résidues et conséquences

D ÉFINITION 2.7.2
Soient m ≥ 2, a, b des entiers.
1. Si a ≡ b (mod m), alors b est appelé un résidu de a (mod m).
2. La classe de congruence (ou classe de résidus) de a (mod m) est l’ensemble
{a + km, k ∈ Z}
3. Un système complet de résidus de a (mod m) est un ensemble d’entiers contenant
un élément de chaque classe.
4. Un système modulaire de réduction (mod m) est un ensemble d’entiers ri avec
pgcd(ri , m) = 1 où pour tout a relativement premier avec m, il existe ri tel que
a ≡ ri (mod m).

D ÉFINITION 2.7.3 ( FONCTION ARITHMÉTIQUE MULTIPLICATIVE )

1. Une fonction Arithmetique est tout application de N \ {0} dans C.
2. Une fonction Arithmetique g est dite multiplicative si g(1) 6= 0 et g(pq) = g(p)g(q)
pour tout entiers (strictement) positifs p et q premiers entre eux. Elle est dite com-
plètement multiplicative si g(pq) = g(p)g(q) pour tout entiers (strictement) posi-
tifs p et q.

E XERCICE 22

1. Soit g une fonction Arithmetique. Justifier que si g est multiplicative alors g(1) = 1.
2. Soit a ∈ R. Justifier que Na donné par Na (n) = na pour tout n ∈ N \ {0}, est une
fonction Arithmetique multiplicative.

Dr. Euloge TCHAMMOU

D ÉFINITION 2.7.4 ( FONCTION D ’E ULER )
La fonction ϕ : N → N ; m 7→ card{a ∈ N∗ , a < m et pgcd(a, m) = 1} est appelée fonction
d’Euler.

E XEMPLE 2.7.3 ϕ(12) =

Remarque 2.7.2
— La fonction d’Euler est multiplicative.
— Le système modulaire de réduction (mod m) est un groupe multiplicatif conte-
nant ϕ(m) éléments.

P ROPRIÉTÉ 2.7.1
Soient n un entier naturel non nul et p un entier premier. On a :

ϕ(pn ) = pn − pn−1

Preuve. Par recurrence sur n.

C OROLLAIRE 2.7.1 Soit m ∈ N∗ . Si la décomposition

 en  produit de facteurs premiers est
1
m = ∏ p , alors ϕ(m) = ∏ (p − p
α α α−1 ) = m ∏ 1− p .
p|m p|m p|m

Théorème 2.7.2 (Euler)

Soient a et m des entiers avec m > 0.
Si pgcd(a, m) = 1 alors aϕ(m) ≡ 1 (mod m).

Preuve. pgcd(a, m) = 1 alors la classe ā, résidu de a (mod m) est un élément du système
modolaire de réduction (mod m). Ainsi il est inversible (car le système modolaire de
réduction (mod m) est un groupe multiplicatif). Par ailleurs l’ordre de ā divise l’ordre
du système modolaire de réduction (mod m) qui est ϕ(m). Donc (ā)ϕ(m) = 1̄ = aϕ(m) .
D’où aϕ(m) ≡ 1 (mod m)
On déduit le résultat suivant qu’on appelle " le petit théorème de Fermat".

Théorème 2.7.3 (Fermat)

Soient p un entier premier et a entier. On a : a p ≡ a (mod p)
De plus Si p ne divise pas a (c-à d pgcd(a, p) = 1), alors a p−1 ≡ 1 (mod p).

Preuve. p étant premier et ne divise pas a alors pgcd(a, p) = 1 et ϕ(p) = p − 1. Le

Théorème d’Euler implique donc a p−1 ≡ 1 (mod p)
En multipliant cette congruence par a, on obtient a p ≡ a (mod p).

Proposition 2.7.1
Soient a et b des entiers et p un entier premier. On a : a2 ≡ b2 (mod p) ⇒ a ≡ ±b
(mod p)

Preuve. a2 ≡ b2 (mod p) ⇒ a2 − b2 = (a − b)(a + b) ≡ 0 (mod p)

Un retour sur la Production des nombres premiers

Dr. Euloge TCHAMMOU

Théorème 2.7.4 (Wilson)
Un entier p ≥ 2 est premier si et seulement si (p − 1)! ≡ −1 (mod p)

P ROPOSITIONS 2.7.1 (AUTRES )

1. x2 ≡ 1 (mod p) ⇔ x ≡ ±1 (mod p)
2. x2 ≡ −1 (mod p) admet de solutions si et seulement si p = 2 ou p ≡ 1 (mod 4)

E XERCICE 23 1. Déterminer les systèmes modulaires de réduction (mod 11) et

(mod 14).
2. Calculer ϕ(27), ϕ(31), ϕ(483), ϕ(5096).

Résulat. 23


Théorème 2.7.5 (des restes chinois)

Soient m, n des entiers naturels et a, b entiers. Le système de congruences
(
x ≡ a (mod m)
x ≡ b (mod n)

est résoluble si et seulement si a ≡ b (mod pgcd(m, n)). Dans le cas où une solution
x0 existe, x est aussi solution si et seulement si x ≡ x0 (mod ppcm(m, n)).

Preuve. Supposons que le système admet de solutions. Alors il existent t,t 0 entiers tel que
x = a + tm = b + t 0 n. Donc a − b = t 0 n − tm ≡ 0 (mod pgcd(m, n)).
Réciproquement si a ≡ b (mod pgcd(m, n)), alors a − b ≡ 0 (mod pgcd(m, n)) et
d’après Bézout, il existent t,t 0 entiers tel que a − b = tm + t 0 n ce qui implique que a +
(−t)m = b + t 0 n. D’où le système admet de solutions.
( Soit x0 une autre solution,(on :
x0 ≡ a ≡ x (mod m) x0 − x ≡ 0 (mod m)
⇒
x0 ≡ b ≡ x (mod n) x0 − x ≡ 0 (mod n)
Donc x0 − x ≡ 0 (mod ppcm(m, n))
Réciproquement, x0 − x ≡ 0 (mod ppcm(m, n)) implique que x0 − x ≡ 0 (mod m) et
x0 − x ≡ 0 (mod n). D’où le résultat.

Théorème 2.7.6 (généralisé)

Soit m1 , · · · , mk une suite d’entiers positifs premiers entre eux deux à deux. Alors le sys-
tème de congruences : 

 x ≡ a1 (mod m1 )

x ≡ a (mod m )
2 2


 ···
x ≡ ak (mod mk )


a une solution unique x (mod M = m1 · m2 · · · mk )

x = a1 M1 y1 + · · · + ak Mk yk

avec Mi = M/mi et yi Mi ≡ 1 (mod mi )

Dr. Euloge TCHAMMOU

E XEMPLE 2.7.4
Résolvons 
x ≡ 1
 (mod 3)
x≡2 (mod 5)

x≡3 (mod 7)


Posons M = 3 × 5 × 7 = 105, M1 = 105

3 = 35, M2 = 105
5 = 21, M3 = 105
7 = 15

y1 × 35 ≡ 1 (mod 3)
 y1 = 2

y2 × 21 ≡ 1 (mod 5) on prend y2 = 1
 
y3 × 15 ≡ 1 (mod 7) y3 = 1
 

x = (1 × 35 × 2) + (2 × 21 × 1) + (3 × 15 × 1) = 157 ≡ 52 (mod 105)

E XEMPLE 2.7.5
Lorsque les mi ne sont pas premiers
 entres eux deux à deux.
x ≡ 1 (mod 2)
( 
x ≡ 1 (mod 6)
⇔ x ≡ 1 (mod 3)
x ≡ 4 (mod 15) 
x ≡ 4 (mod 5)

(
x ≡ 1 (mod 3)
x ≡ 4 (mod 15) ⇔
x ≡ 4 (mod 5)

E XERCICE 24
Dans l’armée de Han Xing il y a entre 1000 et 1100 soldats. Combien cette armée
comporte-t-elle de soldats si, rangés par 3 colonnes, il reste 2 soldats, rangés par 5 co-
lonnes, il reste 3 soldats et, rangés par 7 colonnes, il reste 2 soldats ?

Théorème 2.7.7
Soient a, b des entiers et m un entier naturel.
L’équation ax ≡ b (mod m) admet de solution si et seulement si pgcd(a, m) divise b.
Si pgcd(a, m) divise b l’équation admet exactement d solutions.

Preuve. Posons pgcd(a, m) = d

ax ≡ b (mod m) équivaut à qu’il existe t ∈ Z tel que b = ax − tm. Ce qui admet de
solution si et seulement si pgcd(a, m) divise b.
Soient x1 , x solutions de ax ≡ b (mod m). Alors il existe t ∈ Z tel que a(x − x1 ) = mt.
Donc da (x − x1 ) = md t et comme pgcd( da , md ) = 1 alors md divise x − x1 . D’où x1 = x + k md
pour un certain k ∈ Z.
Maintenant il faut remarquer que les d entiers de la forme xi = x + i md , 0 ≤ i ≤ d − 1 sont
tous solutions et deux à deux incongrus modulo m. D’où le résultat.

C OROLLAIRE 2.7.2
Soient a, b des entiers et m un entier naturel.
Si pgcd(a, m) = 1 alors l’équation ax ≡ b (mod m) admet une seule solution (mod m).

Remarque 2.7.3
Soient a, b, c des entiers et m un entier naturel.
L’équation ax + by ≡ c (mod m) admet de solution si et seulement si pgcd(a, b, m)
divise c.

Dr. Euloge TCHAMMOU

Théorème 2.7.8
Soient a, b, c, d, r, s des entiers et m un entier naturel. Le système
(
ax + by ≡ r (mod m)
cx + dy ≡ s (mod m)

admet une unique solution (mod m) lorsque pgcd(ad − bc, m) = 1

E XERCICE 25
1. Déterminer le reste dans la division euclidienne de 52022 par 11.
2. Justifie que le produit de trois entiers consécutifs est divisible par 3.
3. Soit n ≥ 2 un entier. Montrer que n5 − n est divisible par 30.

E XERCICE 26
1. Résoudre 20x ≡ 4 (mod 30).
2. Montrer que si pgcd(a, 42) = 1 alors 168 divise a6 − 1.
3. Prouver que a7 ≡ a (mod 42), ∀a ∈ Z (utiliser le petit Théorème de Fermat).
4. Prouver Φ(3n) = 3Φ(n) si et seulement si 3 divise n.

2.8 L OI DE RÉCIPROCITÉ QUADRATIQUE

2.8.1 Généralité
Soit p un nombres premier impair.
La question qui prevaut ici est comment résoudre l’équation

ax2 + bx + c ≡ 0 (mod p) (2.1)

où p est un entier premier impair et a 6≡ 0 (mod p) (c’est-à dire a ∧ p = 1).

Définition 2.8.1 Soit p un entier naturel premier impair et soit a un entier tel que p ne
divise pas a.
On dit que a est un résidu quadratique modulo p ou un carré modulo p lorsque l’équa-
tion x2 ≡ a(mod p) admet de solutions dans Z.
Dans le cas contraire, on dira que a est non-résidu quadratique modulo p.

E XEMPLE 2.8.1 13 - 3 et on a : 3 ≡ 42 (mod 13). Donc 3 est un résidu quadratique modulo

13.

Remarque 2.8.1
Si a ≡ b (mod p), alors a est résidu quadratique de p si et seulement si b est résidu
quadratique" de p.

Théorème 2.8.1 (Critère d’Euler)

p−1
Un entier a tel que pgcd(a, p) = 1 est résidu quadratique de p si et seulement si a 2 ≡ 1
(mod p).

Dr. Euloge TCHAMMOU

C OROLLAIRE 2.8.1 p−1
Un entier a tel que pgcd(a, p) = 1 est résidu non quadratique de p si a 2 ≡ −1 (mod p).

Théorème 2.8.2 (Loi de réciprocité quadratique)   

q
Soient p et q deux entiers naturels premiers impairs distincts. Alors , on a : qp p =
p−1 q−1
(−1) 2 2 .

Exemple 3 On a 15508 45



47 = 47 car 15508 ≡ 45(mod 47). Donc
15508 32 ×5 3 2 5




47 = 47 = 47 47
3 2


47
= 1 et d’après la loi de réciprocité quadratique, on a :
5 5−1 47−1 47 47
47
= (−1)
2 (
5 ) = ( 5 ).
2
47 2


5 = 5 car 47 ≡ 2(mod 5)
2


5 ne divise pas 2 et c’est un non résidu quadratique modulo 5, donc 5 = −1. Ainsi
15508


47 = −1

Corollaire 2.8.1 Soient p et q deux entiers naturels premiers impairs distincts.

1. Si l’un au moins des nombres premiers p et q est congru à 1 modulo 4, alors p est
un résidu quadratique modulo q si et seulement si q en est un modulo p.

2. Si p et q sont tous deux congrus à 3 modulo 4, alors p est un résidu quadratique

modulo q si et seulement si q est non résidu quadratique modulo p.

2.8.2 Utilisation des symboles de Jacobi

2.8.3 Symbol de Legendre
D ÉFINITION 2.8.1 (S YMBOL DE L EGENDRE )
Soient a un entier et p 6= 2 premier. Le symbol de Legendre est défini par :

  
a 1 si a est résidu quadratique de p
= 0 si p divise a
p 
−1 si a est résidu non quadratique de p


P ROPRIÉTÉS 2.8.1
Soient p 6= 2 premier et a, b des entiers relativement premiers avec p.
   
1. Si a ≡ b (mod p), alors ap = bp
 2
2. ap = 1
  p−1
3. ap ≡ a 2 (mod p)
    
4. ab p = p
a b
p

Dr. Euloge TCHAMMOU

     p−1
1 −1
5. p= 1 et = (−1) 2 . On déduit que
p
(
 
−1 1 si p ≡ 1 (mod 4)
p =
−1 si p ≡ 3 (mod 4)
(
  1 si p ≡ 1 (mod 8) ou p ≡ 7 (mod 8)
6. 2p = .
−1 si p ≡ 3 (mod 8) ou p ≡ 5 (mod 8)
p2 −1
 
On déduit que 2p = (−1) 8

Théorème 2.8.3 (Loi de reciprocité quadratique)

Soient p et q deux entiers premiers impairs.
  
q p (q−1)(p−1)
= (−1) 4
p q

C OROLLAIRE 2.8.2
Si p et q sont des entiers premiers impairs alors
   (
q p 1 si p ≡ 1 (mod 4) ou q ≡ 1 (mod 4)
=
p q −1 si p ≡ q ≡ 3 (mod 4)

E XERCICE 27
Soient p et q deux entiers premiers impairs. Vérifier que
 
   p
q q  si p ≡ 1 (mod 4) ou q ≡ 1 (mod 4)
=
p − p si p ≡ q ≡ 3 (mod 4)
q

P ROPRIÉTÉS 2.8.2
Soient p un entier premier impair et a un entier relativement premier avec p.
1. Si la factorisation est a = ±2k0 pk11 pk22 · · · pkr r alors
     k0  k1  kr
a ±1 2 p1 pr
= ···
p p p p p

2.   (
3 1 si p ≡ ±1 (mod 12)
=
p −1 si p ≡ ±5 (mod 12)

2.8.4 Symbol de Jacobi

D ÉFINITION 2.8.2 (S YMBOL DE JACOBI )
Soient a et b > 1 deux entiers relativement premiers. Si b = pk11 pk22 · · · pkr r est la décompo-
sition en facteurs premiers de b alors on définit le symbol de Jacobi par
a  k1  k2  kr
a a a
= ··· .
b p1 p2 pr

Dr. Euloge TCHAMMOU

E XEMPLE 2.8.2
3 3 2 3 3





20 = 2 5 = 5 = −1.

E XERCICE 28
Soient a, b et c des entiers positifs que gcd(b, c) = 1.
1. Justifier que pour tous a > 0 et tous b ≥ 2 on a : a2 b2 + 4a < (ab + 1)2 .
2. En deduire que si (a, b) 6= (0, 0), (1, 0) alors l’entier (a2 b2 +4a) n’est pas un carré
parfait.
 2 2 
3. Calculer le symbole a b 3+4a selon les valeur des entiers a et b.
4. Prouver aussi que pour tous a > 0 et tous c ≥ 2, (a2 c2 − 4a) n’est pas un carré
parfait.
5. Soit p ≡ 3 (mod 4) un nombre premier qui divise a. On pose X = (ab2 + 4)(ac2 −
4).
(a) Verifier que pour (a, b, c) = (4, 7, 3), (4, 7, 17), X est un carré parfait.
 
(b) Calculer le symbole Xp puis conclure.

E XERCICE 29
1. Résoudre
(a) 3x2 + 9x + 7 ≡ 0 (mod 13) ;
(b) x2 − x ≡ 7 (mod 3).
2. Montrer que 3 est résidu quadratique modulo 23.
3. Trouver la valeur de : −72

11
215

131 ; 23 ; 253 .

2.9 Numération
2.9.1 Bases de numération
Toutes les civilisations anciennes de Chine, Mésopotamie, Égypte, Amérique du Sud,...
ont inventé un système de numération. Mais ces différents systèmes de numération ne per-
mettaient pas d’effectuer facilement les opérations.
Le système décimal (base dix) a l’avantage de rendre simples toutes les opérations.
Le système binaire (base deux) est adapté à l’Informatique qui utilise également se
système hexadécimal (base seize) pour réduire la taille de l’écriture des nombres (code
ASCII).
Nous admettons la proposition suivante :

Proposition 2.9.1 Soit b ≥ 2 un entier naturel.

p
Tout entier naturel non nul x s’écrit de façon unique ∑ ak bk , où les ak sont des entiers
k=0
naturels tels que 0 ≤ ak < b et a p 6= 0.

On écrit x = a p a p−1 ...a0 p écriture est appelée l’écriture de x en base b.

Par convention, les écritures ”sans barres” sont en base 10.

Dr. Euloge TCHAMMOU

 p
b
Remarque 2.9.1 Soit x = a p a p−1 ...a2 a1 a0 = ∑ ak bk = a pb p + a p−1b p−1 + ... + a2b2 +
k=0
a1 b + a0 .
• On a x = b(a p b p−1 + a p−1 b p−2 + ... + a2 b + a1 ) + a0 , avec 0 ≤ a0 < b.
Donc q0 = a p a p−1 ...a2 a1 b et a0 sont respectivement le quotient et le reste de la divi-
sion euclidienne de x par b.
• On a q0 = b(a p b p−2 + a p−1 b p−3 + ... + a3 b + a2 ) + a1 , avec 0 ≤ a1 < b.
Donc q1 = a p a p−1 ...a2 b et a1 sont respectivement le quotient et le reste de la division
euclidienne de q0 par b.
On peut ainsi déterminer de proche en proche l’écriture de x en base b.

E XEMPLE 2.9.1

Pour écrire un entier naturel en base b, les chiffres utilisés sont 0; 1; ..., b − 1.

2.9.2 Quelques systèmes de numération les plus usuels

Les systèmes de numération les plus usuels sont : le système décimal (base dix), le
système binaire (base deux), le système octal (base huit), le système hexadécimal (base
seize).

Système binaire
Pour écrire un entier naturel en base deux, les chiffres utilisés sont 0 et 1.

E XEMPLE 2.9.2 1. Écrivons en base 2 le nombre 367.

2
2. Écrivons en système décimal le nombre 110100111 .

Système octal
C’est le système de numération de base huit. Pour écrire un entier naturel dans une
telle base, les chiffres utilisés sont 0; 1; ..., 6 et 7.

E XEMPLE 2.9.3 1. Écrivons en système octal le nombre 2022.

8 8 8
2. Écrivons en système décimal les nombres 12340567 , 76504321 et 272 .

Système hexadécimal
C’est le système de numération de base seize. Pour écrire un entier naturel dans une
telle base, les chiffres utilisés sont 0; 1; ..., 9 A, B, C, D, E et F, où A, B, C, D, E et F
reprśentent respectivement 10; 11; 12; 13; 14 et 15.
16 16
E XEMPLE 2.9.4 1. Écrivons en système décimal les nombre FAC et F0A5 .
2. Écrivons en système hexadécimal les nombres 2022, 765043219 et 2988.

Dr. Euloge TCHAMMOU

2.9.3 Congruences particulières-Critères de divisibilité par 3, 4, 5, 9,
11 et 25
Dans chacun des exercices suivants, x désigne un entier naturel non nul décriture dé-
cimale a p a p−1 ...a2 a1 a0 .

E XERCICE 30 (Congruence modulo 5-Critère de divisibilité par 5)

1. Démontrer x ≡ a0 (mod 5).
2. En déduire le critère de divisibilité par 5.
3. Déterminer les restes des divisions euclidiennes par 5 de 2022, 76528639, 2340
et 79783.

E XERCICE 31 (Congruence modulo 4 et 25-Critères de divisibilité par 4 et 25)

1. Démontrer x ≡ a1 a0 (mod 4) et x ≡ a1 a0 (mod 25).
2. En déduire les critères de divisibilité par 4 et par 25.
3. Déterminer les restes des divisions euclidiennes par 4 et par 25 de 2022, 76528639,
2340 et 79783.

E XERCICE 32 (Congruence modulo 3 et 9-Critères de divisibilité par 3 et 9)

p p
1. Démontrer x ≡ ∑ ak (mod 3) et x ≡ ∑ ak (mod 9).
k=0 k=0
2. En déduire les critères de divisibilité par 3 et par 9.
3. Déterminer les restes des divisions euclidiennes par 3 et par 9 de 2022, 76528639,
2340 et 79783.

E XERCICE 33 (Congruence modulo 11-Critère de divisibilité par 11)

p
1. Démontrer x ≡ ∑ (−1)k ak (mod 11).
k=0
2. En déduire le critère de divisibilité par 11.
3. Déterminer les restes des divisions euclidiennes par 11 de 2022, 76528639, 2340
et 79783.

Dr. Euloge TCHAMMOU

Bibliographie

[1] http ://mathworld.wolfram.com/NumberTheory.html

[2] Alain Togbé, Elementary arithmetic and cryptography, Course CIMPA at IMSP, July
7-19, 2014
[3] Michel Waldschmidt, An elementary introduction to Cryptography, Course CASPAM
at BZU Multan, Nov. 23, 2015
[4] http ://primes.utm.edu/largest.html
[5] https ://www.mersenne.org/primes/
[6] http ://primes.utm.edu/top20/page.php ?id=12

36