Module Mathématiques pour l’Informatique_ partie 10

Zahra Royer-SafouanaTabiou
Rappel : On appelle ainsi les ensembles de nombres : (cf. Wikipédia)

• , ensemble des entiers naturels.

• , ensemble des entiers relatifs.
• , ensemble des nombres décimaux.
• , ensemble des rationnels.
• , ensemble des nombres réels.
• , ensemble des nombres réels positifs ou nuls.
• , ensemble des nombres réels négatifs ou nuls.
• , ensemble des nombres complexes.
• , les mêmes ensembles privés de zéro.
• Par construction on a ⊂ ⊂ ⊂ ⊂ ⊂ .
≠ ≠ ≠ ≠ ≠

Exemples fondamentaux (suite)

Les ensembles numériques a , , , et munis de l’ordre naturel sont des

treillis distributifs non complémentés car ils ne sont pas bornés ; il n’y a pas
d’opération de complémentation non plus .
En effet, ∀ x, y , z ∈ IR , en distinguant les 3 cas possibles : x ≤ y ≤ z ; y ≤ x ≤ z
et z ≤ x ≤ y , on montre que :
min ( x, max ( y , z ) ) = max( min ( x, y ) , min( x, z ) ) .

∗ De manière générale, il est clair que tout ensemble totalement ordonné est
un treilli distributif.

* muni de l’ordre divise est un treillis distributif borné mais non

complémenté .
En effet : PGCD( a, b ) = a ∧ b et PPCM ( a, b ) = a ∨ b .
Le treillis est distributif : on le démontre facilement en utilisant les décompositions
en facteurs premiers et la distributivité de l’ordre naturel.
De plus le treillis est borné car tout élément divise 0 c’est le plus grand élément
et 1 divise tout élément , c’est le plus petit élément.
Etant donné x , on ne peut trouver d’entier n( x ) tel que PGCD( x, n( x ) ) = 1 et
PPCM ( x, n( x ) ) = 0 donc ce treillis n’est pas complémenté.
 (℘ ( E ) , ⊂ ) est un treillis distributif et complémenté. En effet pour tous
A, B ⊂ E , A ∨ B = A ∪ B et A ∧ B = A ∩ B ; ∅ est le plus petit élément et E
le plus grand élément. D’autre part si A est le complémentaire de A dans E
alors on a A ∩ A = ∅ et A ∪ A = E .
Si E n’est pas vide ou un singleton, (℘ ( E ) , ⊂ ) est une algèbre de Boole.
On démontre que toute algèbre de Boole finie peut être vue comme un
(℘ ( E ) , ⊂ ) Ce sont donc des prototypes.

Remarque : On sait que dans (℘ ( E ) , ⊂ ) toute partie admet une borne inférieure et
une borne supérieure. Un treillis qui a cette propriété est dit complet. Nous ne
développons pas les propriétés de ces treillis.
Chapitre 3 : Arithmétique
Exercices Tests : Voici une liste d’exercices. Si vous êtes capables de les
résoudre alors vous n’avez pas besoin du cours, dans le cas contraire, le
chapitre suivant vous apporte les compétences savoir et savoir faire,
pour résoudre ces exercices et tout problème qui se ramène aux
équations de congruence ou aux équations diophantiennes, et plus
généralement à un problème d’arithmétique.
• Le premier janvier 2011 sera un samedi. Quel jour de la semaine sera le
201ième jour de l’année 2011 ?

• Un objet vaut x € et y centimes. Par erreur vous payez y euros et x

centimes soit deux fois le prix plus 5 centimes. Quel est le prix de l’objet ?

• Deux enfants ont 100 billes à eux deux. Si le premier met ses billets par
paquets de 8, il lui en reste 7, et le second met ses billets par paquets de 10,
il lui en reste 7. Combien ont-ils de billes chacun ?

• Un restaurant propose un menu à 11 euros pour les adultes et à 7 euros pour

les enfants. A la fin de la journée, la recette est de 657 euros. Quel est le
nombre minimum de personnes qui ont été servies dans cette journée ? Le
nombre maximum ?

• Une compagnie pétrolière doit livrer 100 000 litres d’essence. Ses camions
citernes ont une capacité ont une 2400 litres ou de 4600 litres. Chaque
 citerne doit être pleine avant de prendre la route , autrement le roulis
pourrait représenter un danger . Est-il possible pour la compagnie
d’effectuer sa livraison ? Quel est le nombre minimal de camions qu’elle doit
utiliser ?

• Déterminer les triplets d’entiers ( x, y , z ) tel que 5 x + 7 y + 11z = 1

• Sophie vend des billets d’avion. Dans son agence, ouverte 7 jours 7, le rythme
de travail a une périodicité de 5 jours : elle travaille 4 jours de suite, puis
elle a droit à une journée de congé et puis ça recommence encore et
toujours.... Ce qu’elle aime surtout c’est avoir son congé le mercredi car ce
jour-là les musées sont ouverts tard le soir et elle a le temps d’en visiter
plusieurs. Aujourd’hui lundi, elle n’a pas le moral car elle est à son 4 ième jour
de travail d’affilé et ce n’est de sitôt que son congé tombera un mercredi.
• Dans combien de jours cette circonstance favorable va –t-elle se produire et
combien de jours faudra-t-il attendre pour qu’elle se produise à nouveau ?

→ L’arithmétique est l’étude des nombres en considérant la relation de divisibilité.

Elle est de nos jours redevenue centrale car les ordinateurs ne connaissent que les
nombres entiers.

→ La programmation utilise généralement le codage en binaire, les théories

s’appuient donc sur l’ensemble /2 noté souvent {0,1} muni des opérations que
nous avons introduit dans un précédent exemple.
Plus généralement, la cryptographie, les théories des codes détecteurs et des
codes correcteurs utilisent les ensembles /n appelés entiers modulo n.

Les équations de congruences, c’est à dire des équations à coefficients les

problèmes.
Le but de ce chapitre est de se familiariser aux notions, méthodes et techniques de
l’arithmétique, et leurs applications à l’étude de problèmes de congruence.
Beaucoup de problèmes conduisent à des équations diophantiennes, ce sont des
équations polynomiales à coefficients entiers dont on cherche des solutions
entières .
La plus célèbre de ces équations étant l’équation de Fermat
x n + y n = z n , n ∈ IN, n ≥ 2 .
Ce chapitre utilise les acquis des deux chapitres précédents.
Son but est de rappeler et de compléter les bases élémentaires d’arithmétique : la
division euclidienne, la décomposition en facteurs premiers, l’algorithme d’Euclide
pour le calcul du PGCD, PPCM .

Nous pourrons alors apporter des méthodes et techniques de résolution des

équation de Bezout : équation linéaire à coefficients entiers dont on cherche des
solutions entières .
Nous reviendrons pour finir sur les congruences et nous complèterons nos
connaissances sur les ensembles /n

La division euclidienne sur

Théorème 6(rappel) : Soient ( a, b ) ∈ x *.
Il existe un unique couple ( q, r ) ∈ 9 2 tels que a = bq + r et 0 ≤ r < b . La formule
a = bq + r et 0 ≤ r < b s’appelle division euclidienne de a par b ; q s’appelle le
quotient et r le reste de a par b . b divise a si et seulement si r = 0 .

→ Prenons par exemple :

a = 20 et b = − 6 ; on a 20 = ( − 6 ) × ( − 3) + 2 = ( − 6 ) × ( − 2 ) + 8 = ( − 6 ) × 5 + 50 ; on voit
qu’il existe plusieurs relations du type a = bq + r , ( q, r ) ∈ 2 si l’on impose pas la
condition 0 ≤ r < b .
20 = ( − 6 ) × ( − 3) + 2 est la division euclidienne de 20 par -6, la quotient est -3 et le
reste 2 mais 20 = ( − 6 ) × ( − 2) + 8 et 20 = ( − 6 ) × 5 + 50 ne sont pas des divisons
euclidienne.

Montrons que la condition 0 ≤ r < b assure effectivement l’unicité de ( q, r ) .

Supposons qu’il existe deux couples ( q, r ) et ( q ′ , r ′ ) vérifant 0 ≤ r < b ; 0 ≤ r ′ < b
et a = bq + r = bq ′ + r ′ . Il vient alors b( q − q ′ ) = r ′ − r . Si q n’était pas égal à q ′ on
aurait r − r ′ = b( q − q ′ ) ≥ b or 0 ≤ r < b ; 0 ≤ r ′ < b implique r ′ − r < b et
r − r ′ < b donc r − r ′ < b . On aboutit donc à une contradiction par conséquent on
nécessairement q = q ′ et par suite r = r ′ .
Nous admettons l’existence du couple ( q, r ) par la pratique que nous supposons
acquise. Enfin, la division euclidienne permet de savoir mettre en évidence la
relation « divise» entre entiers non nuls.

Rappelons aussi que « divise» est une relation d’ordre sur ∠* et seulement un
préordre sur *. Car sur *, a divise − a et − a divise a donc la relation n’est
pas antisymétrique). De manière générale, sur *, on a a divise b et b
divise a si et seulement si a = b .
En effet : a divise b ⇔ a = bq et b divise a ⇔ b = q ′ a . Il vient a = ( qq ′ ) a soit
qq ′ = 1 . D’où q = q ′ = 1 .

∗ Ensemble des multiples d’un entiers : Si a divise b , on dit que b est un

multiple de a . L’ensemble des multiples de a est noté a 9 ou ( a ) .
Par exemple 2 = ( 2 ) = { 2k , k ∈ } c’est l’ensemble des entiers pairs.

On a les propriétés suivantes a = ( − a) . Si a divise b alors b ⊂ a .

3.2 Nombres premiers

12 8

6 4 10

3 2 5

Ceci est le début du diagramme de Hasse (qui est infini) de la relation « divise sur
* . Il met en évidence une certaine organisation des entiers naturels.
En deuxième ligne apparaissent des entiers qui ne possèdent pour seuls diviseurs
que 1 et eux mêmes.
On les appelle des nombres premiers.
Ces nombres ont des propriétés qui les mettent au centre de l’arithmétique sur
ou .
La colonne centrale est occupée par les entiers de la forme 2 n , à gauche ceux de la
forme 2 n 3 m .
En continuant on observera qu’il est possible d’écrire tout entier naturel sous
forme de produits de nombres premiers.
Cette propriété peut s’étendre sans peine aux entiers relatifs, et le concept de
nombre premier peut être généralisé à .
Nous allons rappeler la notion de nombre premier, donner les moyens de les
identifier et de les utiliser. Dans , on appelle nombre premier tout entier naturel
qui n’admet pour diviseurs que 1 et lui- même. Voici les nombres premiers inférieurs
à 100 ; il y en a 25.
2 3 5 7 11 13 17 19 23 29 37 41 43 47
53 59 61 67 71 73 79 83 89 97
Dans , on appelle nombre premier un entier a dont la valeur absolue est un nombre
premier . Autrement dit a est premier si a n’admet que 3 diviseurs : 1 , a et
− a.
L’ensemble des nombres premiers dans est la réunion de l’ensemble des nombres
premiers entiers naturels et de l’ensemble de leurs opposés. Aussi les propriétés
seront énoncés sans perte de généralité pour les nombres premiers naturels .
Les lemmes suivants seront souvent utiles.
Lemme 1: Soit n ∈ , n > 1 ; le plus petit diviseur de n strictement supérieur à 1
est un nombre premier. Donc tout entier admet au moins un diviseur premier.

En effet, soit n > 1 . n divise n donc l’ensemble des diviseurs de n strictement

supérieur à 1 n’est pas vide. Par conséquent il admet un plus petit élément, disons
k . Si k n’était pas premier il admettrait un diviseur u > 1 , qui diviserait aussi n et
qui serait plus petit que k donc k ne serait plus le plus petit diviseur strictement
supérieur à 1 de n.
Observons quelques ensembles de diviseurs d’entiers naturels.
Ensemble des diviseurs de :
16 : {1, 2, 4, 8, 16}
45 : {1, 3, 5, 9, 15, 45}
100 : {1, 2, , 4, 5, 10, 20, 25, 50, 100}
458 : {1, 2, 229, 458}
4581 : {1, 3, 9, 509, 1527, 4581}
On observe que si k divise n alors n = kq , q divise n et k et q sont situés
symétriquement par rapport au milieu de la liste ; cette observation conduit au
lemme suivant :
Lemme 2: Soit n ∈ *, dans la liste des diviseurs de n , le produit de deux
diviseurs situés symétriquement par rapport au milieu de la liste est égal à n .

En effet : supposons que n = kq , 2 ≤ k , q < n . Alors q ≤ n ou bien q ≥ n car si

n
q ≤ n on a k = ≥ n .
q
On en déduit dès lors le premier test de primalité suivant :
Théorème 7: Soit n ∈ , n ≥ 3 . Si n n’est divisible par aucun des entiers compris entre 2 et
n alors n est premier.

Exemple : 229 est premier car 229 = 15,13 et aucun des nombres premiers
inférieurs à 15 à savoir 2 3 5 7 11 et 13 ne divise 229 .
On vérifie de même que 509 est premier.

D’après le lemme 1, tout entier naturel n ≥ 2 admet au moins un diviseur premier .

On peut dès lors par l’algorithme suivant trouver les diviseurs premiers puis
factorier n en produits de nombres premiers.
Méthode pour décomposer un entier en facteurs premiers
Déterminer le plus petit diviseur de n autre que 1 . Soit p1
Diviser n par p1 .
n
Si m = > 1 , recommencer à partir de 1 avec m.
p1
Nous pouvons énoncer :
Théorème 8: Tout entier naturel n ≥ 2 est soit un nombre premier soit un produit
de nombres premiers .
k

Dès lors n s’écrit sous la forme n = ∏i= 1

piα i = p1α 1 p 2α 2 ... p kα k où pi sont des nombres

premiers et les α i ∈ ∠* La décomposition est unique à une permutation près des

facteurs, autrement dit elle est déterminée de manière unique par les facteurs
premiers p i et leur exposant α i que l’on note v pi ( n ) On obtient ainsi la
décomposition en facteurs premiers de n . Pour un entier négatif a , si
k k
a = ∏
i= 1
p iα i = p1α 1 p 2α 2 ... p kα k alors a = − ∏ piα i = p1α 1 p 2α 2 ... p kα k est par définition la
i= 1

décomposition de a en facteurs premiers

Disposition pratique : pour exécuter cet algorithme on adopte disposition suivante
dans laquelle les facteurs premiers sont à droite, à la fin il suffit de multiplier tous
ces facteurs.
16 2
8 2
4 2 il vient 16 = 2 4 .
2 2
1

45 3
15 3
5 5 il vient 45 = 3 2 × 5 = 3 2 × 51
1

100 2
50 2
25 5 il vient 100 = 2 2 × 5 2
5 5
1

458 2
229 229
1 il vient 458 = 2 × 229 (nous montré que 229 est premier)

4581 3
1527 3
509 509 il vient 4581 = 3 2 × 509 (nous montré que 509 est premier)
1

45815 5
9163 7
1309 7 il vient 45815 = 5 × 7 2 × 11 × 17
187 11
17 17
1

∗ Il est évident que cet algorithme de factorisation n’est pas très efficace pour
des grands nombres(car trop lent). C’est sur ce constat que s’appuie les clés de
sécurité en cryptographie .

Voici un corollaire fondamental du théorème :

Corollaire : il existe une infinité de nombre premiers .

Preuve : D’après ce qui précède l’ensemble des nombres premiers (naturels) n’est
pas vide. Supposons qu’il existe k nombres premiers p1 ,...., p k .
Posons n = p1 .... p k .
n + 1 admet un diviseur premier p . Alors p est distinct de tous les pi car sinon p
diviserait n et n + 1 donc aussi leur différence c’est à dire 1. Ce qui est
impossible !
Rappelons que a divise b et a divise c alors a divise b ± c .
Cette démonstration donne aussi un moyen de lister de nouveaux nombres premiers
à partir de ce qu’on connait déjà. Il suffit de prendre p1 ,...., p k , de calculer
N = p1 .... p k + 1 et de factoriser N . Posons n = p1 .... p k . n + 1 aussi gan loin que
l’on veut . Par exemple de 2 , on construit 3 qui est premier, puis 7 puis 43 qui
sont premiers puis 2 × 3 × 7 × 43 + 1 = 1807 = 13 × 139 . On obtient deux nouveaux
nombres premiers : 13 et 139, et ainsi de suite.

3.3 PGCD et PPCM : identité de Bezout ; algorithme d’Euclide

Nous avons vu que * muni de l’ordre divise est un treillis distributif borné et
PGCD( a, b ) = a ∧ b (plus grand commun diviseur) et PPCM ( a, b ) = a ∨ b (plus petit
commun multiple).
Le plus petit et plus grand sont au sens de l’ordre divise, on peut alors généraliser
les deux concepts aux entiers relatifs.
PGCD et PPCM dans :Soit a1 ,...., a n ∈ , On appelle pgcd (plus grand commun
diviseur ) de a1 ,...., a n tout entier d vérifiant : d divise chacun des ai ; tout diviseur
commun à tous les ai divise d . Dès lors : si d est un pgcd de a1 ,...., a n alors − d
aussi Par conséquent le seul entier positif vérifiant i) et ii) s’appelle le PGCD de
a1 ,...., a n . On le note PGCD ( a1 ,...., a n ) ou a1 ∧ .... ∧ a n .
On appelle ppcm (plus petit commun multiple ) de a1 ,...., a n tout entier m vérifiant :
m ∈ ( a i ) , ∀ i ai tout multiple commun aux ai est un multiple de m . Autrement dit
( m ) = ( a1 ) ∩ ( a 2 ) ∩ .... ∩ ( a n )
Dès lors : si m est un ppcm de a1 ,...., a n alors − m aussi. Par conséquent le seul
entier positif vérifiant 1. et 2. s’appelle le PPCM de a1 ,...., a n . On le note PPCM
( a1 ,...., a n ) ou a1 ∨ .... ∨ a n .

Dans ce qui suit on convient d’écrire la décomposition en facteurs premiers sous

forme d’un produit contenant une infinité de termes en utilisant tous les nombres
premiers et en acceptant l’exposant 0.
∞
..... où v pi ( a ) = 0 si et
( a) ( a) ( a) ( a)
∏
v v v v
Donc si a ≥ 2 , on écrira a= p i pi = p1 p1 p 2 p2 ... p k p k
i= 1

seulement si pi divise a .
Seulement un nombre fini des v pi ( a ) ne sont pas nuls.
r

Dès lors si b = ∏
j= 1
qiγ i = q1γ 1 q 2γ 2 ...q kγ k où q j sont des nombres premiers et les γ j ∈ *

alors pour trouver l’ensemble des diviseurs communs il suffit de considérer les
facteurs premiers communs à a et b .
Enfin
/n {
= 0, 1,..., n − 1 .}
Par définition si r ∈ { 0,1,..., n − 1} , r = { qn + r , q ∈ Z } ensemble des entiers dont le
reste de la division euclidien par n est égal à r .
Généralement on écrit r = n + r .
Par exemple n = 0 = n ; n +1 = 1 ainsi de suite.
Fin.