IT-University

Cours d’arithmétique

Table des matières

1 Arithmétique sur Z 1
1.1 Division euclidienne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Sur les nombres premiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Valuation p-adique d’un entier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 L’Algorithme d’Euclide et L’équation ax + by = c . . . . . . . . . . . . . . . . . . . . 6
1.5 Numération en base b d’un entier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2 Arithmétique sur Z/nZ 8

2.1 L’ensemble Z/nZ muni de la loi addition et multiplication . . . . . . . . . . . . . . . 8
2.2 Element inversible de Z/nZ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3 La fonction indicatrice d’Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4 Le Théorème Chinois et système d’équations congruences . . . . . . . . . . . . . . . 11

3 Applications 12
3.1 Introduction au cryptosystème RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.2 Projet d’Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1 Arithmétique sur Z
Dans toute la suite N et Z désigneront respectivement l’ensemble des entiers naturels (y compris
zéro) et l’ensemble des entiers relatifs. On rappel aussi qu’on dispose deux lois de composition sur
Z, qui à tout entiers x et y, la somme x + y et le produit xy. Pour tout entier x, on notera par
|x| la valeur absolue de x, i.e, le plus grand entre x et −x.

Theorem 1.1 (Propriété Fondamental de l’Arithmétique). Toute partie non vide de N admet
un plus petit élément.

Preuve. On a déjà une preuve en cours d’analyse.

Il est important de noter qu’on peut avoir presque tout les résultats importants en arithmétique
élémentaire à partir de cette propriété. Donc, le titre de ”fondamental” qu’on lui donne est bien
justifié.

1
1.1 Division euclidienne
Theorem 1.2. Soient a et b deux entiers tels que b ̸= 0. Il existe un unique couple (q, r) ∈ Z × Z
tel que l’on ait:

ˆ a = qb + r;

ˆ 0 ≤ r < |b|.

Définition 1.3. Soient a et b deux éléments de Z. On dit que b divise a ou que b est un diviseur
de a, ou bien encore que a est un multiple de b s’il existe k entier tel que

a = bk.

Si b est non nul, cette condition signifie que le reste de la division euclidienne de a par b est nul.

Exercice 1.1.

1. Quels sont le quotient et le reste de la division euclidienne:

ˆ de 456765 par 641;

ˆ de -456765 par 641;
ˆ de 456765 par -641.

2. Soient a et n deux entiers naturels non nuls. Montrer que a − 1 divise an − 1.

3. Déterminer tous les entiers naturels n tels que n + 1 divise n2 + 1.

1.2 Sur les nombres premiers

Définition 1.4. On appelle nombre premier tout entier p ≥ 2 dont les seuls diviseurs positifs sont
1 et p.

Exemples 1.5. Donner la liste des nombres premiers inférieurs à 100.

Dans toute la suite, notons par P l’ensemble des nombres premiers.

Theorem 1.6. L’ensemble P des nombres premiers est infini.

Preuve.

Lemme 1.7. Soit p un entier supérieur à 2. Alors, p est premier si et seulement si p n’est pas le
produit de deux entiers strictement plus grands que 1.

Preuve. Exercice.

Lemme 1.8. Tout entier supérieur ou égal à 2 est un produit de nombres premiers. En particulier,
tout entier n ≥ 2 possède un diviseur premier.

Preuve. Procéder par récurrence, puis utiliser le lemme précédent.

2
Lemme 1.9 (Lemme d’Euclide). Si un nombre premier divise un produit d’entiers relatifs, il divise
l’un de ces entiers. En particulier, si un nombre premier divise un produit de nombres premiers, il
est égal à l’un d’eux.

Theorem 1.10 (Théorème Fondamental de l’Arithmétique). Tout entier n ≥ 2 s’écrit de

façon unique sous la forme:
n = pn1 1 pn2 2 · · · pnr r , (1)
où les ni sont des entiers naturels non nuls, et où les pi sont des nombres premiers vérifiant
pi−1 < pi pour tout i = 2, . . . , r. On dit que l’égalité (1) est la décomposition de n en produit de
nombres premiers.

Preuve.

Maintenant, pour qu’on puisse factoriser un entier, une question naturel se pose: Comment décider
si un entier naturel n ≥ 2 est un nombre premier ou non?
Il existe de nombreux tests permettant parfois de reconnaı̂tre si un entier est premier ou non. C’est
toute une théorie qu’on appelle tests de primalité. Il sera difficile pour nous d’aborder ce sujet en
première année. Par contre, le résultat suivant est utile:

Proposition 1.11. Soit n un entier supérieure ou égal à 2. Si n n’est pas premier, alors n possède
un diviseur premier p vérifiant l’inégalité p2 ≤ n.

Preuve. Exercice.

Exemples 1.12. En utilisant le résultat précédent, on va montrer √ que n = 641 est premier. Si
641 n’était pas premier, n admet un diviseur premier inférieur à 641 ≤ 26. Les nombres premiers
plus petits que 25 sont 2, 3, 5, 7, 11, 13, 17, 19 et 23. On vérifiera alors qu’aucun de ces nombres
ne divise 641 en utilisant le théorème de la division euclidienne.

Soit N un entier naturel supérieur ou égal à 2. Il existe un procéder pour déterminer tout les
nombres premiers inférieurs à N. Le plus connu s’appelle le crible d’Eratosthène. Le procéder
de criblage utilise seulement l’opération de multiplication d’entiers. Le principe est le suivant:

ˆ On écrit d’abord dans un tableau tous les entiers jusqu’à N ;

ˆ Puisque 2 est un nombre premier, On raye ensuite tous les multiples de 2 du tableau, autres
que 2;

ˆ On garde le premier plus petit entier qui n’a pas encore rayé (qui est 3 en cet stade). Puis,
on raye tous les multiples de 3, autres que 3;

ˆ A chaque étape on raye tous les multiples du plus petit entier qui n’a pas encore été rayé;
√
ˆ On arrête si on avait tous cribler tout les entiers inférieurs à N . Tout les restes sont des
nombres premiers.

Par exemple, si on veut avoir la liste de nombres premiers √ inférieurs à 100, on raye tous les multiples
de 2, 3, 5 et 7 (qui sont les nombres premiers inférieurs à 100 = 10). On peut aussi, bien évidement,
utiliser ce crible en testant si un nombre est premier ou non.

3
Exercice 1.2.
1. Montrer que 3571 est un nombre premier.
2. Montrer que si 2n − 1 est un nombre premier, il en est de même de n. Un nombre de la forme
2n − 1, avec n premier, s’appelle un nombre de Mersenne.
3. Montrer que si 2n + 1 est premier, alors n est une puissance de 2. Un nombre de la forme
n n
22 + 1 s’appelle un nombre de Fermat. Montrer que pour n = 1, 2, 3 et 4 le nombre 22 + 1
est premier. Mais par contre, 232 + 1 n’est pas premier.
4. Démontrer que l’entier 1 + 2 + 22 + 23 + . . . + 22019 n’est pas premier.
5. Implémenter sur C ou C++ le crible d’Eratosthène. En déduire le 100001 ième nombre
premier. Donner la liste de nombres premiers inférieurs à 2000000.
6. Trouver le plus grand facteur premier du nombre 600851475143.

1.3 Valuation p-adique d’un entier

Dans cette sous-section, n et p désigneront successivement un entier relatif et un nombre premier.
L’application
vp : Z −→ N ∪ {+∞}
définie par:
i). Si l’on a n ≥ 2, alors vp (n) est l’exposant de p dans la décomposition de n en produit de
nombres premiers. Plus précisément:
ˆ Si p ne divise pas n, on a vp (n) = 0;
ˆ Si n = pn1 1 pn2 2 . . . pnr r est la décomposition de n en produit de nombres premiers (ni ≥ 1),
on a:
vpi (n) = ni pour i = 1, 2, . . . , r.
ii). On pose vp (0) = +∞ et vp (1) = 0;
iii). Si n ≥ 1, on a vp (−n) = vp (n).
est appelé valuation p-adique. On dit aussi vp (n) est la valuation p-adique de n.
Comme un exemple, Posons n = 539000. On a n = 23 · 53 · 72 · 11, de sorte que l’on a v2 (n) =
3, v5 (n) = 3, v7 (n) = 2, v11 (n) = 1 et donc pour tout nombre premier p distinct de 2, 5, 7 et 11,
on a vp (n) = 0.
Ainsi, on peut écrire le Théorème Fondamental de l’Arithmétique comme suit:
Tout entier relatif n non nul s’écrit de manière unique, à l’ordre près des facteurs,
sous la forme : Y
n=ϵ pvp (n)
p∈P

où ϵ = −1 si n ≤ −1 et ϵ = 1 si n ≥ 1.
Il est important de noter que:

vp (n) ≥ 1 si et seulement si p divise n.

4
Proposition 1.13. Soient a et b deux entiers relatifs et p un nombre premier. On a:
i). vp (ab) = vp (a) + vp (b);

ii). vp (a + b) ≥ Min(vp (a), vp (b)). Si de plus, vp (a) ̸= vp (b), on a vp (a + b) = Min(vp (a), vp (b));

iii). Pour que a divise b, il faut et il suffit que l’on ait vp (a) ≤ vp (b) pour tout p ∈ P.
Preuve. Exercice.

Maintenant soient a et b deux entiers non tous nuls. Considérons les entiers naturels d et m définis
par:
Y Y
d:= pMin(vp (a),vp (b)) , m:= pMax(vp (a),vp (b)) .
p∈P p∈P

L’entier d ainsi défini vérifie les deux propriétés suivantes:

ˆ L’entier d est un diviseur commun à a et b;

ˆ Tout diviseur commun à a et b divise d.

Tandis que l’entier m satisfait les deux conditions suivantes:
ˆ L’entier m est un multiple commun à a et b;

ˆ Tout multiple commun à a et b est un multiple de m.

Les entiers d et m sont appelés respectivement le plus grand commun divise et le plus petit
commum multiple de a et b. On les note respectivement par pgcd(a, b) et ppcm(a, b).
Définition 1.14. On dit que a et b sont premiers entre eux si pgcd(a, b) = 1. Ainsi, pgcd(a, b) = 1
si et seulement si pour tout p ∈ P, on a Min(vp (a), vp (b)) = 0.
Exercice 1.3.
1. Calculer v2 (10560). Pour tout p ∈ P calculer vp (196000).
√
2. En utilisant l’application valuation p-adique, démontrer que 2 n’appartient pas à l’ensemble
Q des nombres rationnels. Soit a un nombre rationnel strictement positif. Donner une
√
condition nécessaire et suffisante pour que a appartienne à Q.

3. Soient p et q deux nombres premiers distincts. Montrer que pq divise pq−1 + q p−1 − 1.

4. Déterminer le pgcd et le ppcm de 2800 et 120.

5. Trouver tous les couples d’entiers naturels (a, b) pour lesquels on a pgcd(a, b) = 5 et ppcm(a, b) =
8160.
˚ et leur
6. Soient a et b deux entiers non tous nuls. Notons respectivement par d et m leur pgcd
ppcm.
˚ Montrer que:
a b
i). Les entiers d et d sont premiers entre eux;
ii). dm = |ab|;

5
1.4 L’Algorithme d’Euclide et L’équation ax + by = c
Dans cet sous-section, considérons deux entiers a et b tels que a ≥ b. Notre but est de donner en
détail un algorithme (utilisant seulement la division euclidienne) pour déterminer non seulement le
pgcd de a et b, mais aussi de résoudre l’équation du type ax + by = c dans Z2 où c est un entier
donné.
Le théorème suivant est fondamental:

Theorem 1.15 (Théorème de Bézout). Il existe deux entiers relatifs u et v tel que l’on ait:

pgcd(a, b) = au + bv.

De plus, les entiers a et b sont premiers entre eux si et seulement si il existe deux entiers u et v
tels que au + bv = 1.

Considérons maintenant les trois suites (ri ), (ui ) et vi associées à a et b définies comme suit:

ˆ r0 = a et r1 = b. Pour i ≥ 2, on définit ri comme étant le reste de la division euclidienne de

ri−2 par ri−1 ;

ˆ u0 = 1 et u1 = 0. Pour i ≥ 2, on pose ui = ui−2 − ui−1 qi−1 où qi−1 est le quotient de la

division euclidienne de ri−2 par ri−1 ;

ˆ v0 = 0 et v1 = 1. Pour i ≥ 2, on pose vi = vi−2 − vi−1 qi−1 .

On peut montrer que la suite des restes (ri ) est une suite décroissante minorée donc convergente.
Sa limite est 0, i.e, il existe n ∈ N, tel que:

rn ̸= 0 et rn+1 = 0.

De plus:

Theorem 1.16.
rn = pgcd(a, b) = aun + bvn .

Il peut être commode de présenter les étapes de calculs sous la forme du tableau suivant :

q1 q2 ··· qn
r0 = a r1 = b r2 ··· rn rn+1 = 0
u0 = 1 u1 = 0 u2 ··· un
v0 = 0 v1 = 1 v2 ··· vn

Pour mieux comprendre l’algorithme ci-dessus, voici un exemple concret que l’étudiant sera prié de
refaire: Prenons a = 17640 et b = 525.

35 1 1 2
17640 525 315 210 105 0
1 0 1 -1 2
0 1 -33 34 -67

6
Ainsi on a:
pgcd(a, b) = 105 = 17640 × 2 + 525 × (−67).
Maintenant passons à la résolution dans Z2 d’équation du type

ax + by = c

où c est un entier donné. Notons par S l’ensemble des couples d’entiers (x, y) qui vérifient cet
équation. En utilisant tout ce qu’on a fait jusqu’ici on a le résultat suivant:

Theorem 1.17. Soit d le pgcd de a et b. Posons a′ = a

d et b′ = db . Alors:

ˆ L’ensemble S est non vide si et seulement si d divise c;

ˆ Si d divise c et que (x0 , y0 ) ∈ Z2 est une solution particulière, on a:

S = (x0 + ka′ , y0 − kb′ ) | k ∈ Z .



Il est important de noter que si l’équation admet de solutions (i.e d divise c), on peut prendre
comme solution particulière le couple (x0 = u dc , y0 = v dc ) où u et v sont des entiers obtenus en
utilisant l’algorithme étendu d’Euclide.
Exercice 1.4.

1. Pour tout n entier naturel, déterminer le pgcd de 5n + 2 et 12n + 5.

2. Soit n un entier supérieur ou égal à 1. Déterminer le pgcd de 9n + 4 et 2n − 1.

3. Déterminer tout les entiers n de quatre chiffres tels que les restes des divisions euclidiennes
de 21685 et 33509 par n soient respectivement 37 et 53.

4. Déterminer tout les couples (x, y) ∈ Z2 tels que 47x − 111y = 1.

5. On dispose d’un récipient de 8 litres et d’un de 12 litres. Montrer qu’on peut remplir un
bassin avec exactement 200 litres d’eau, en utilisant les deux récipients pour verser de l’eau
dans le bassin ou pour en retirer.

6. Implémenter sur C ou C++ l’algorithme étendu d’Euclide avec comme ”input” deux entiers
a et b et comme ”output” le pgcd ainsi que les entiers u et v tels que au + bv = pgcd(a, b)).

1.5 Numération en base b d’un entier

Soient b et N deux entiers naturels tels que b ≥ 2.

Theorem 1.18. On peut écrire N de manière unique sous la forme:

x = an bn + an−1 bn−1 + . . . + a1 b + a0 ,
où n est un entier naturel, où a0 , . . . , an sont des entiers tels que 0 ≤ ai ≤ b−1 et où an est non nul.
On dit que N = an an−1 · · · a1 a0 est l’écriture de N en base b et l’on écrit parfois N = (an · · · a0 )b
ou N = an · · · a0 b .

Preuve. On a un résultat plus général déjà prouvé en cours d’analyse.

7
Exercice 1.5.
1. Déterminer l’écriture en base 3 de 733456.

2. Soit N un entier naturel. Trouver une condition nécessaire et suffisante simple pour que n
soit divisible, respectivement, par 2, 3, 5 et par 9.

3. Soit N = (abcabc)10 un entier écrit en base 10. Montrer que N est divisible par 77.

4. Soit N = (an an−1 · · · a1 a0 )10 l’écriture de N en base 10. Montrer que

n
X
N est divisible par 11 si et seulement si (−1)i ai = 0.
i=0

5. Déterminer les nombres de deux chiffres qui s’écrivent ab en base 10 et ba en base 7.

6. Implémenter sur C ou C++ la conversion d’un entier naturel en base quelconque.

2 Arithmétique sur Z/nZ

2.1 L’ensemble Z/nZ muni de la loi addition et multiplication
Soit n un entier naturel non nul. Pour tout entier a et b, on dit que a est congruent à b modulo n
s’il a le même reste que b après division euclidienne par n. Si c’est le cas on écrit:

a ≡ b mod n.

Soit a un entier. L’ensemble des entiers congruents à a modulo n est noté par a, i.e:

a:= {b ∈ Z | a ≡ b mod n} .

Ainsi:

a ≡ b mod n si et seulement si a = b.
Il est important de noter que si a, b, c et d sont des entiers, alors on a les propriétés suivantes:
ˆ a ≡ a mod n;

ˆ Si a ≡ b mod n, alors b ≡ a mod n;

ˆ Si a ≡ b mod n et b ≡ c mod n, on a a ≡ c mod n;

ˆ Si a ≡ b mod n et c ≡ d mod n, alors a + c ≡ b + c mod n et ac ≡ bd mod n.

Finalement, l’ensemble Z/nZ est définie par:

Z/nZ:= {a | a ∈ Z} .

Comme les restes possibles après division euclidienne par n sont: 0, 1, 2, . . . , n − 1, on conclut que:

Z/nZ = 0, 1, 2, . . . , n − 1 .

8
Maintenant on va munir Z/nZ de deux lois binaires, à savoir la loi addition et la multiplication,
induites par celles de Z. D’après les propriétés ci-dessus, on conclut qu’on a, pour tout a et b dans
Z/nZ:

ˆ a + b = a + b;

ˆ a · b = ab.

S’il n’y a pas de confusion, on pourra omettre la barre sur les entiers. Mais, l’étudiant doit se
souvenir toujours dans quel ensemble il travaille.

Exemples 2.1. Pour n = 6, on a les tables suivantes:

Pour l’addition:
+ 0 1 2 3 4 5
0 0 1 2 3 4 5
1 1 2 3 4 5 0
2 2 3 4 5 0 1
3 3 4 5 0 1 2
4 4 5 0 1 2 3
5 5 0 1 2 3 4

Pour la multiplication:

× 0 1 2 3 4 5
0 0 0 0 0 0 0
1 0 1 2 3 4 5
2 0 2 4 0 2 4
3 0 3 0 3 0 3
4 0 4 2 0 4 2
5 0 5 4 3 2 1

2.2 Element inversible de Z/nZ

Soit a un entier. On dit que a est inversible dans Z/nZ s’il existe un entier u tel que

u·a=1

C’est à dire:
au ≡ 1 mod n.
Si c’est le cas, on dit que u est l’inverse de a dans Z/nZ. Noter bien que u est aussi inversible et
que a est son inverse.
L’ensemble des éléments inversibles de Z/nZ est noté par (Z/nZ)× . D’après la table de multipli-
cation ci-dessus, on a par exemple:

(Z/6Z)× = 1, 5 .


L’inverse de 1 est lui-même, de même pour 5.

9
Theorem 2.2. Soit a un entier. L’élément a de Z/nZ est inversible si et seulement si a et n sont
premiers entre eux. C’est à dire:
(Z/nZ)× = {a ∈ Z/nZ | pgcd(a, n) = 1} .
Preuve. Supposons que a est inversible. Donc, il existe un entier u tel que au ≡ 1 mod n. C’est à
dire, il existe un entier v tel que au = 1 + nv. D’après le théorème de Bézout, comme au − nv = 1,
où u et v sont des entiers, alors pgcd(a, n) = 1. Supposons maintenant que pgcd(a, n) = 1. D’après
Bézout encore, ils existent deux entiers u et v tels que au + nv = 1. Dans, Z/nZ, on a au + nv =
au + nv = au = 1 car nv = 0. D’où a est inversible dans Z/nZ.
Ainsi, pour vérifier si un élément a est inversible dans Z/nZ, il suffit de calculer le pgcd de a et n.
S’ils sont premiers entre eux, on conclut que a est inversible. Pour calculer l’inverse, on cherche un
couple d’entier (u, v) tel que
au + nv = 1
en utilisant l’algorithme d’Euclide. Ainsi, l’inverse de a est u.
Exercice 2.2.
1. Déterminer l’ensemble (Z/32Z)× . Montrer que 19 est inversible dans Z/32/Z, puis calculer
son inverse.
2. Soit p un nombre premier. Déterminer l’ensemble (Z/pZ)× .
3. Calculer l’inverse de 641 dans Z/16065209631001Z.

2.3 La fonction indicatrice d’Euler

Soit n un entier naturel non nul. La fonction φ de N vers N définie par:
φ(n):=#(Z/nZ)×
est appelée fonction indicatrice d’Euler. Autrement dit: φ(n) est le nombre des entiers
naturels premiers avec n et inférieurs à n. Elle vérifie les propriétés suivantes:
ˆ Si p est un nombre premier, pour tout entier naturel k ≥ 1, on a:
φ(pk ) = pk − pk−1 ;

ˆ Si n et m sont des entiers naturels non nuls premiers entre eux, on a:

φ(nm) = φ(n)φ(m).

D’où:
Theorem 2.3. Si n = pr11 pr22 · · · prkk la décomposition de n en facteurs premiers, on a:
k  
Y 1
φ(n) = n 1− .
pi
i=1
Ceci nous amène à énoncer l’un des théorèmes les plus importants en arithmétique:
Theorem 2.4 (Euler). Soit a un entier premier avec n. Alors:
aφ(n) ≡ 1 mod n.

10
Exercice 2.3

1. Calculer φ(100) et φ(600851475143).

2. Posons a = (1035125)5642 . Déterminer le reste de la division euclidienne de a par 17.

2020
3. Trouver le dernier chiffre (écrit en base 10) de l’entier 37 .

4. Soient p un nombre premier impair et a, b deux entiers non divisibles par p, tels que p divise
a2 + b2 . Montrer que l’on a p ≡ 1 mod 4.

5. Montrer que 13 divise 270 + 370 .

2.4 Le Théorème Chinois et système d’équations congruences

Soient n et m deux entiers naturels non nuls. Considérons le système d’équations suivant:
(
x ≡ a mod n;
(2)
x ≡ b mod m.

où a et b sont des entiers.

Le théorème Chinois résout cet système dans Z/nmZ comme suit:

Theorem 2.5 (Théorème Chinois). Le système d’équations (2) admet

x = bun + avm

comme solution unique dans Z/nmZ où les entiers u et v vérifient l’équation:

un + vm = 1.

Exercice 2.4

1. Résoudre dans Z/437Z le système suivant:

(
x ≡ 7 mod 19;
x ≡ 10 mod 23.

2. Résoudre dans Z le système suivant:

(
x ≡ 3 mod 101;
x ≡ 98 mod 641.

3. Déterminer le plus petit entier naturel multiple de 7 et congru à 1 modulo 2, 3, 4, 5 et 6.

11
3 Applications
3.1 Introduction au cryptosystème RSA
La cryptographie est l’étude de la science des communications par des messages codés qui ne
pourront être lus que par leur destinataire. Un cryptosystème est un tel mode de communication.
La cryptographie suscite en fait de l’intérêt depuis l’antiquité, compte tenu de la nécessité de pouvoir
faire parvenir des messages qui ne puissent pas être déchiffrés par un hh intrus ii . L’algorithme
RSA, qui a été découvert par Rivest, Shamir et Adleman en 1977, a constitué de ce point de vue
une très importante avancée. C’est un algorithme à clé publique. Son efficacité repose sur le fait
qu?il est difficile de factoriser un entier ayant disons plus de deux cents chiffres dans son écriture
décimale i.e. dans son écriture en base 10.
Voici le Principe du cryptosystème RSA:Si un utilisateur A veut utiliser le cryptosystème RSA
pour qu’il puisse recevoir un message d’un autre utilisateur B, il doit procéder comme suit:
1. Il choisit deux grands nombres premiers p et q et calcule n = pq. On choisit ces deux nombres
premiers de tels sorte qu’il est ”impossible” pour d’autre personne de factoriser l’entier naturel
n;
2. Choisir un entier e premier avec φ(n) tel que 1 < e < φ(n). La classe de e modulo φ(n) est
donc inversible dans Z/φ(n)Z;
3. L’utilisateur détermine ensuite l’entier d, l’inverse de e dans Z/φ(n)Z;
4. Il publie à la fin le couple (e, n), qui est sa clé publique, et il conserve en secret le couple
(d, φ(n)) ainsi que les nombres premiers p et q , qui est sa clé secrète.
Toute personne voulant écrire un message a l’utilisateur A utilise la clé public (e, n) pour
chiffre le message. Tandis que l’utilisateur utilise sa clé secrète pour déchiffrer le message
crypter.
Maintenant, si l’utilisateur B veut envoyer un message m à A, il doit procéder comme suit:
ˆ Il calcule tout simplement x = me et envoie la classe x de x modulo Z/nZ. Tout le monde
peut recevoir la valeur x, mais si on ne possède pas la clé secrète de A, on n’est pas sensé
pouvoir déchiffrer le message facilement.
Enfin, si l’utilisateur A veut déchiffrer le message envoyer par B, il calcule xd = med dans Z/φ(n)Z.
Comme ed ≡ 1 modφ(n). On a
ed = 1 + kφ(n)
pour un certain entier k. Or d’après le théorème d’Euler, dans Z/nZ, on a:
mkφ(n) ≡ 1mod n.
D’où:
xd = med ≡ m mod n.
C’est ainsi, l’utilisateur pourra obtenir le message m.
Un exemple concret sera dirigé en classe.

3.2 Projet d’Euler

12