Stage olympique de Saint-Malo

Cours  Arithmétique
Vendredi 1 août 2003

par

François Lo Jacomo

Table des matières

1 Introduction 2
2 Division euclidienne 3
3 Nombres premiers 6
4 Congruences 7
5 Exercices 11
6 Solution des exercices 13

1
1 Introduction
Quand vous avez appris l'addition et la multiplication, vous avez commencé par addi-
tionner et multiplier des entiers, puis des nombres décimaux, des nombres réels... et vous
avez sans doute eu la sensation que cela revenait au même : en tant qu'opérations, l'addition
des entiers ou des réels, la multiplication des entiers ou des réels se manipulent quasiment
de la même manière. Et pourtant, les entiers et les réels sont deux objets mathématiques
très diérents. L'arithmétique, l'étude des nombres entiers, est un chapitre à part et réputé
dicile des mathématiques, où certains problèmes d'apparence anodine peuvent rester des
siècles sans solution.
Il est donc fondamental, quand des nombres apparaissent dans un problème, de bien
voir s'il s'agit de nombres entiers ou de nombres réels, en sachant que les méthodes de
résolution n'ont rien à voir et la diculté est tout autre. Sauf lorsque cela sera précisé, les
nombres qui interviennent dans ce chapitre sont des entiers relatifs (positifs, négatifs ou
nuls), éléments de Z.

Une notion joue un rôle essentiel dans l'étude des nombres entiers, et elle est dénuée
de tout intérêt dans l'étude des nombres réels : la divisibilité. Un entier a est divisible par
un entier b s'il existe un entier q tel que a = bq . On dit également que b divise a, ou que b
est diviseur de a, et on note b|a.
Signalons tout de suite quelques propriétés immédiates de la divisibilité :
 tout entier a ∈ Z divise 0 et est divisible par 1 et a ;
 si a|b et b|c, alors a|c ;
 soit m un entier non nul, alors a|b si et seulement si ma|mb ;
 si a|b et a|c, alors a|bx + cy pour tous entiers x et y ; en particulier a|b − c et a|b + c.
Mais on peut citer encore plus fondamental que cela : le fait qu'il n'existe pas d'entier
strictement compris entre 0 et 1. Si, par exemple, b divise a et |b| > |a|, alors a = 0 ; sinon,
en écrivant a = bq , le quotient |q| = |a|
|b| serait un entier strictement compris entre 0 et 1.
Cela va nous permettre de résoudre un premier exercice :

Exercice : Trouver tous les couples d'entiers (a, b) supérieurs ou égaux à 2 tels que ab − 1
soit divisible par (a − 1) (b − 1).

Solution :
I Il est clair que ab−1 > a (b − 1) > (a − 1) (b − 1). Si ab−1 est divisible par (a − 1) (b − 1),
l'entier q tel que ab − 1 = q (a − 1) (b − 1) est nécessairement strictement supérieur à 1,
donc au moins égal à 2. Or :
µ ¶µ ¶
ab − 1 a b
<
(a − 1) (b − 1) a−1 b−1

Supposons a 6 b (a et b jouent des rôles symétriques).

a 1 b
=1+ >
a−1 a−1 b−1
Si en outre a > 4, on va avoir :
b a 4
6 6
b−1 a−1 3

2
d'où : µ ¶2
ab − 1 4
< <2
(a − 1) (b − 1) 3
Donc on a nécessairement a = 2 ou a = 3.
³ ´³ ´
a b
Si a = 2, a−1 b−1 6 22 = 4, donc q ne peut valoir que 2 ou 3. Pour q = 3,
ab − 1 = q (a − 1) (b − 1) devient 2b − 1 = 3 (b − 1) donc b = 2 ; pour q = 2, on obtient
2b − 1 = 2 (b −³1) qui
´ ³n'a pas
´ de¡solutions.
a b
¢2
Si a = 3, a−1 b−1 6 23 = 2, 25, donc q ne peut valoir que 2 et ab − 1 =
q (a − 1) (b − 1) devient 3b − 1 = 4 (b − 1) d'où b = 3.
Les seules solutions sont donc a = b = 2 et a = b = 3. J

Autre solution :
I Si ab − 1 est divisible par (a − 1) (b − 1), le facteur (a − 1) divise lui aussi ab − 1. Or il
divise b (a − 1), donc il divise la diérence (ab − 1) − b (a − 1) = b − 1. Et pour la même
raison (b − 1) divise a (b − 1), donc également a − 1. On en déduit que a − 1 = b − 1.
En eet, de manière très générale, si q et q 0 sont deux entiers tels que qq 0 = 1, alors soit
q = q 0 = 1, soit q = q 0 = −1 ; donc si x divise y et y divise x, il va exister deux entiers q
et q 0 tels que y = xq et x = yq 0 et donc tels que qq 0 = 1, ce qui entraîne x = y ou x = −y
(exclu en l'occurrence puisque a − 1 et b − 1 sont strictement positifs). Dès lors, a = b et
le problème se ramène à trouver a tel que
a2 − 1 a+1 2
2 = a−1 =1+ a−1
(a − 1)
soit entier, ce qui est vérié pour a − 1 = 1 et a − 1 = 2, et pour eux seuls. J

2 Division euclidienne
Les principales propriétés de la divisibilité des entiers découlent de la division eucli-
dienne :

Théorème 1 (Division euclidienne)

Soit b un entier strictement positif. Tout entier a ∈ Z s'écrit, de manière unique, a = bq + r

avec q ∈ Z et 0 6 r < b.

Le reste r de la division euclidienne joue un rôle plus important que le quotient q , et le

fait que r soit strictement inférieur à b est essentiel.
Pour prouver l'existence des entiers q et r, on considère la progression arithmétique
. . . , a + 2b, a + b, a, a − b, a − 2b, . . . et on appelle r = a − qb le plus petit terme positif ou nul
de la progression. Si r était supérieur ou égal à b, r −b = a−(q + 1) b serait un terme positif
ou nul de la progression, strictement inférieur à r, ce qui contredit l'hypothèse. Quant à
l'unicité, si a = bq + r = bq 0 + r0 , la diérence r − r0 = b (q 0 − q) est divisible par b. Or
|r − r0 | < b. Donc r − r0 = 0, ie r = r0 et q = q 0 .

La division euclidienne permet, pour commencer, de déterminer les diviseurs communs

à deux entiers a et b grâce à l'algorithme d'Euclide.

3
Algorithme d'Euclide
Soient a = a0 et b = a1 deux entiers strictement positifs tels que b < a. À titre
d'exemple, on peut choisir a = a0 = 1848 et b = a1 = 804. La division euclidienne leur
associe deux entiers positifs ou nuls q1 et a2 < a1 tels que a0 = a1 q1 + a2 . Dans notre
exemple, 1848 = 804 × 2 + 240. Si a2 est strictement positif (ici, a2 = 240), la division
euclidienne de a1 par a2 s'écrit a1 = a2 q2 + a3 , avec 0 6 a3 < a2 . Ici 804 = 240 × 3 + 84.
Et ainsi de suite :
a2 = a3 q3 + q4 240 = 84 × 2 + 72
..
. 84 = 72 × 1 + 12
jusqu'à ak−1 = ak qk + ak+1 72 = 12 × 6 + 0

avec ak+1 = 0. Ceci se produit inévitablement au bout d'un nombre ni d'opérations, car les
restes ai décroissent strictement, et il n'existe qu'un nombre ni d'entiers entre 0 et a1 . Soit
d = ak le dernier reste non nul. Dans notre exemple, d = 12. On a ak−1 = ak qk +ak+1 = ak qk
(puisque ak+1 = 0) donc d divise ak−1 : 12 divise 72. Et si d divise ai et ai+1 , d divise aussi
ai−1 = ai qi + ai+1 . Ici, 12 divise 72, 84, 240, 804 et 1848. L'entier d est donc un diviseur
commun à a = a0 et b = a1 .
Mais qui plus est, d est le plus grand diviseur commun à a et b, noté généralement
Pgcd (a, b) (abréviation de Plus Grand Commun Diviseur). C'est non seulement le plus
grand au sens où tout autre diviseur commun strictement positif de a et b est inférieur à d,
mais en outre, tout diviseur commun de a et b divise d. Cela se démontre en redescendant
diéremment l'algorithme d'Euclide : dans notre exemple :

240 = 1848 − 804 × 2 = a − 2b

84 = 804 − 240 × 3 = b − 3 (a − 2b) = −3a + 7b
72 = 240 − 84 × 2 = (a − 2b) − 2 (−3a + 7b) = 7a − 16b
12 = 84 − 72 = (−3a + 7b) − (7a − 16b) = −10a + 23b

De manière générale, si deux restes successifs de l'algorithme d'Euclide s'écrivent ai−1 =

ui−1 a + vi−1 b et ai = ui a + vi b, le reste suivant ai+1 = ai−1 − ai qi s'écrit bien aussi :

ai+1 = (ui−1 − ui qi ) a + (vi−1 − qi vi ) b = ui+1 a + vi+1 b

donc, de proche en proche, tous les restes de l'algorithme d'Euclide s'écrivent sous cette
forme, y compris le dernier reste non nul : d = au + bv .
Ceci prouve simultanément deux choses : ce dernier reste non nul de l'algorithme d'Eu-
clide est bien le plus grand diviseur commun de a et b, car tout diviseur commun de a et
b divise au + bv = d. Mais en outre :

Théorème 2 (Bézout)

Si d est le plus grand diviseur commun de deux entiers a et b (d = Pgcd (a, b)), il existe
deux entiers u et v tels que d = au + bv .

Cas particulier important : si a et b n'ont pas de diviseur commun autre que 1 et −1, on
dit que a et b sont premiers entre eux et il existe deux entiers u et v tels que au + bv = 1.

4
 Remarquons que u et v sont des entiers a priori quelconques ; ils ne sont pas uniques :
pour tout q , on a encore d = a (u − bq) + b (v + aq). Mais ils sont premiers entre eux :
s'ils avaient un diviseur commun d0 , dd0 diviserait au et bv donc d = au + bv , ce qui n'est
possible que si d0 = 1 ou −1. En choisissant, parmi les (u − bq), le reste de la division de
u par b, on peut imposer 0 6 u < b. Si b ne divise pas a (a et b strictement positifs), u est
non nul, donc on a également 0 > v > −a. En eet, d, diviseur de a, est inférieur ou égal
à a donc à au. Et au − b < 0, or d > 0.

De ce théorème de Bézout découle en particulier le théorème de Gauss :

Théorème 3 (Gauss)

Si a|bc et a est premier avec b, alors a|c.

En eet, puisque a et b sont premiers entre eux, il existe u et v tels que au + bv = 1.

Comme a divise bc, il divise a (uc) + (bc) v = (au + bv) c = c.

Le théorème de Gauss dit que si a est premier avec b et avec c, alors il est premier
avec le produit bc. En eet, tout diviseur d de a est premier avec b (si d et b avaient un
diviseur commun, celui-ci serait diviseur commun de a et b). Si a et bc avaient un diviseur
commun d, celui-ci, premier avec b, devrait diviser c, ce qui n'est pas possible car a et c
sont premiers entre eux.

Nous avons là une propriété forte de la divisibilité dans Z, il existe d'autres ensembles
de nombres où la divisibilité ne vérie pas le théorème de Gauss. Munis de ce théorème de
Gauss, nous sommes maintenant bien armés pour étudier la décomposition d'un entier en
facteurs premiers.
Mais avant cela, un mot de la notion de Ppcm (plus petit commun multiple), qui
complète utilement celle de Pgcd.

Ppcm et Pgcd
Soient a et b deux entiers strictement positifs. Il existe deux entiers strictement positifs
d et m tels que :
• d divise a et b, et tout diviseur commun de a et b divise d
• m est divisible par a et par b, et tout multiple commun de a et b est multiple de m.
d est le Pgcd de a et b, et m leur Ppcm (plus petit commun multiple). Ces deux entiers
vérient en outre dm = ab.
Nous avons déjà étudié le Pgcd, il reste à prouver les propriétés du Ppcm. Si n est
divisible par a et par b, n = aa0 = bb0 , donc n est divisible par d, Pgcd de a et b :
n a b
= · a0 = · b0
d d d
Or ad et db sont premiers entre eux : s'ils avaient un diviseur commun d0 , dd0 serait diviseur
commun de a et b, et d ne serait pas le Pgcd. ad divise db · b0 en étant premier avec db , donc
(théorème de Gauss) ad divise b0 : il existe q tel que b0 = ad ·q , ce qui entraîne n = bb0 = ab
d ·q .
ab ab b a
Tout multiple commun de a et b est donc multiple de d , et m = d = a · d = b · d est
bien multiple de a et de b, ce qui achève la démonstration.

5
 Remarquons au passage que si a et b sont premiers entre eux, leur Ppcm est égal à leur
produit, et tout multiple commun de a et b est multiple du produit ab. Plus généralement,
si a1 , a2 , . . . , ak sont k entiers deux à deux premiers entre eux, tout multiple commun
de a1 , a2 , . . . , ak est divisible par le produit a1 a2 . . . ak . Cela se démontre  de proche en
proche , par récurrence sur k , ak étant premier avec a1 a2 . . . ak−1 .

3 Nombres premiers
Dénition 1 Un entier naturel p > 1 est dit premier s'il a exactement deux diviseurs
naturels, 1 et p.

1 n'est pas premier ; tous les nombres premiers sauf 2 sont impairs.
Si n est un entier et p un nombre premier, soit p divise n, soit p est premier avec n. En
particulier, p est premier avec tous les entiers naturels strictement inférieurs à p.
Le plus petit diviseur naturel p > 1 d'un entier n est obligatoirement premier : s'il
admettait un diviseur strictement compris entre 1 et p, celui-ci diviserait n et p ne serait
pas le plus petit diviseur de n

Théorème 4 (Décomposition en facteurs premiers)

Tout entier naturel n se décompose d'une et d'une seule manière en un produit de facteurs
premiers  abstraction faite de l'ordre des facteurs.

Ce théorème fondamental se démontre en deux temps : existence de la décomposition

d'une part, unicité d'autre part. L'existence est assez simple : par l'absurde, supposons
qu'il existe des entiers naturels qui n'admettent pas de décomposition, et soit n le plus
petit d'entre eux. Soit n n'admet pas de diviseur strictement compris entre 1 et n, et n est
premier par dénition. Soit il admet un diviseur d, donc n = dq . Les entiers d et q sont
tous deux compris entre 1 et n donc tous deux admettent une décomposition en facteurs
premiers (puisque n est le plus petit n'admettant pas de décomposition). Le produit de ces
deux décompositions est une décomposition de n. Contradiction.
L'unicité nécessite le théorème de Gauss. Il est clair que deux nombres premiers dis-
tincts sont premiers entre eux. Supposons que n admette deux décompositions distinctes
et classons les nombres premiers par ordre croissant :

n = p1 p2 . . . pk = p01 p02 . . . p0k0

avec p1 6 p2 6 . . . 6 pk et p01 6 p02 6 . . . 6 p0k0 . Soit i le plus petit indice tel que pi 6= p0i .
n n
Le nombre n0 = p1 p2 ...p i−1
= p0 p0 ...p 0 est divisible par pi et par p0i . Or si pi < p0i , pi
1 2 i−1
est strictement inférieur à tous les facteurs premiers p0j de la seconde décomposition de n0
(puisque p0i 6 p0j pour i 6 j ), il est donc premier avec chacun de ces nombres premiers, et
d'après le théorème de Gauss, il est premier avec leur produit n0 , ce qui contredit le fait
que pi est, dans la première décomposition, un facteur premier de n0 . Il en va de même si
p0i < pi .

Deux  exercices  classiques pour mettre en application le théorème de Gauss et les

nombres premiers :

6
Exercice : Si p est un nombre premier, pour tout k strictement compris entre 0 et p, le
p!
coecient binomial Ckp = k!(p−k)! est divisible par p.

Solution :
I Rappelons que p! = 1 × 2 × . . . × p, avec 0! = 1! = 1. Les Ckp forment le triangle de
Pascal et la relation Ckp+1 = Ckp + Ck−1
p permet de prouver qu'ils sont tous des entiers.
L'important est que si p est premier, il apparaît au numérateur et pas au dénominateur,
donc on ne peut pas simplier par p. Autrement dit :

p! = Ckp · k! (p − k)!

Or p divise p! et est premier avec tous les entiers 1, . . . , k (car k < p), ainsi qu'avec
1, . . . , p − k (car k > 0), donc avec leur produit k! (p − k)!. Donc p divise Ckp . J

Exercice : Il existe une innité de nombre premiers.

Il s'agit en fait d'un résultat fondamental, mais qui donne lieu à tout un tas de dévelop-
pements pour préciser combien il existe de nombres premiers dans un intervalle donné. Les
premiers résultats obtenus dans ce domaine proviennent de la décomposition en facteurs
premiers de Cn2n .
Mais contentons-nous de ce premier résultat qui peut être traité en exercice et néan-
moins utilisé (le plus souvent implicitement) comme un théorème de cours :

Solution :
I Par l'absurde, supposons qu'il existe un nombre ni de nombres premiers p1 , p2 , . . . , pk .
Le nombre n = p1 p2 . . . pk + 1 est premier avec chacun de nombres premiers p1 , p2 , . . . , pn :
si pi divisait n, comme pi divise n − 1 = p1 p2 . . . pk , pi diviserait la diérence 1. Or n admet
au moins un facteur premier, qui n'appartient pas à {p1 , . . . , pk } ce qui prouve que cet
ensemble ne contient pas tous les nombres premiers. J

4 Congruences
Tout comme on distingue nombres pairs et nombres impairs ; multiples de 3, nombres
de la forme 3k + 1, nombres de la forme 3k + 2 ; plus généralement, on peut classer les
entiers en n classes modulo n, à savoir :

Dénition 2 a est congru à b modulo n si et seulement si a − b est divisible par n, ce qui

s'écrit :
a ≡ b (mod n) ⇐⇒ n| (a − b)

Il s'agit bien là d'une relation d'équivalence :

• a ≡ a (mod n) ;
• si a ≡ b (mod n), alors b ≡ a (mod n) ;
• si a ≡ b (mod n) et b ≡ c (mod n), alors a ≡ c (mod n).
Les classes d'équivalence, au nombre de n, constituent un ensemble ni noté Z/nZ. Et dans
cet ensemble, on peut dénir des opération du fait que :

7
 1. si a ≡ b (mod n) et a0 ≡ b0 (mod n), alors a + a0 ≡ b + b0 (mod n). En eet, si n
divise a − b et a0 − b0 , n divise (a + a0 ) − (b + b0 ) = (a − b) + (a0 − b0 ), ce qui permet
d'additionner les classes d'équivalence :

classe de a + classe de b = classe de (a + b)

et le résultat ne dépend pas du choix de a à l'intérieur d'une même classe ni du choix

du b à l'intérieur d'une même classe.
2. De même, si a ≡ b (mod n) et a0 ≡ b0 (mod n), alors aa0 ≡ bb0 (mod n), car si n
divise a − b et a0 − b0 , n divise aa0 − bb0 = a0 (a − b) + b (a0 − b0 ).
En particulier, si a ≡ b (mod n), a2 ≡ b2 (mod n) : on rappelle que a2 − b2 =
(a − b) (a + b). Plus généralement pour tout k > 0, ak ≡ bk (mod n) :
³ ´
ak − bk = (a − b) ak−1 + ak−2 b + . . . + abk−2 + bk−1

ce qu'on démontre en développant :

¡ ¢
a ¡ak−1 + ak−2 b + . . . + bk−1 ¢ = ak + ak−1 b + . . . + abk−1
− b ak−1 + . . . + abk−2 + bk−1 = − ak−1 b − . . . − abk−1 − bk

3. Il est clair en outre, que si ma ≡ mb (mod n) et si m est premier avec n, alors a ≡ b

(mod n). Il est possible de simplier modulo n à la condition que le nombre par lequel
on simplie soit premier avec n. En eet, si n divise ma − mb = m (a − b), en étant
premier avec m, n divise a − b, donc a ≡ b (mod n). Cette possibilité de simplier
est à la base du lemme fondamental sur les systèmes de résidus.

Système complet de résidus

Dénition 3 Un ensemble X = {x1 , x2 , . . . , xn } de n entiers est dit système complet de
résidus modulo n si pour tout entier x ∈ Z, il existe un et un seul xk tel que x ≡ xk
(mod n). Autrement dit si X contient un et un seul élément de chaque classe d'équivalence
modulo n.

Cette dénition sert essentiellement à énoncer le lemme suivant :

Lemme 5

Si X = {x1 , x2 , . . . , xn } est un système complet de résidus modulo n et si a est un entier

premier avec n, alors aX = {ax1 , ax2 , . . . , axn } est un système complet de résidus modulo
n.

En eet, si deux éléments de aX appartenaient à la même classe, c'est-à-dire si axi ≡

axj (mod n), n diviserait a (xi − xj ). Or n est premier avec a donc (théorème de Gauss) n
diviserait xi − xj : xi et xj appartiendraient à la même classe (xi ≡ xj (mod n)), ce qui est
contraire à l'hypothèse. Comme il existe exactement n classes modulo n et n éléments de
aX appartenant tous à des classes distinctes, aX contient un élément dans chaque classe
modulo n.

Le principal théorème résultant de ce lemme et le (petit) théorème de Fermat :

8
 Théorème 6 (Fermat)

Soit p un nombre premier et a un entier premier avec p (ou : non divisible par p). Alors
ap−1 ≡ 1 (mod p).
Il en résulte que ap ≡ a (mod p), ce dernier résultat étant vrai même si a est divisible
par p (donc pour tout a ∈ Z ).

Preuve :
I L'ensemble X = {0, 1, 2, . . . , p − 1} est un système complet de résidus modulo p. Donc
aX = {0, a, 2a, . . . , a (p − 1)} est un système complet de résidus modulo p puisque a est
premier avec p. Donc chaque i ∈ {1, . . . , p − 1} est congru modulo p, à un ki a et un seul
pour ki ∈ {1, . . . , p − 1}. Le produit :

1 × 2 × . . . × (p − 1)

est donc congru modulo p à :

a × 2a × . . . × (p − 1) a = ap−1 (1 × 2 × . . . × (p − 1))

Or 1×2×. . .×(p − 1) est premier avec p, car p est premier donc premier avec 1, 2, . . . , p−1.
Il en résulte après simplication que 1 est congru à ap−1 . J

Remarque : Si n n'est pas premier, alors on ne peut pas simplier par 1×2×. . .×(n − 1) qui
n'est pas premier avec n. Par contre, considérons l'ensemble X 0 des entiers de {1, . . . , n − 1}
qui sont premiers avec n. Il y en a ϕ (n), ϕ étant appelée la fonction indicatrice d'Euler.
Si x est premier avec n, ax est premier avec n puisque a est premier avec n. Donc
les éléments de aX 0 sont dans les mêmes classes que les éléments de X 0 à permutation
près. Autrement dit, le produit P des x ∈ X 0 est congru, modulo n, au produit des ax,
pour x ∈ X 0 , donc à aϕ(n) P . Comme P est premier avec n, aϕ(n) ≡ 1 (mod n). C'est
une généralisation du théorème de Fermat, toutefois moins importante que le théorème de
Fermat lui-même.

Exercice : Si d est le Pgcd de a et de b, montrer que 2d − 1 est le Pgcd de 2a − 1 et 2b − 1.

Solution :
I Il est clair que, si d divise a, 2d − 1 divise 2a − 1, car a = dq et :
³ ´³ ´
2dq − 1 = 2d − 1 2d(q−1) + 2d(q−2) + . . . + 2d + 1

De même, 2d − 1 divise 2b − 1. Si a divise b ou b divise a, cela sut à conclure. Sinon,

on peut trouver deux entiers u et v , 1 6 u < b et 1 6 v < a tels que d = ua − vb, d'après
une variante du théorème de Bézout. Alors :
³ ´
2d − 1 = (2ua − 1) − 2d 2vb − 1

et il est clair que tout diviseur commun de 2a − 1 et 2b − 1 divise 2ua − 1 et 2vb − 1, donc
2d − 1, ce qui prouve que 2d − 1 est le plus grand diviseur commun de 2a − 1 et 2b − 1. J

Exercice : Montrer que si n divise 2n + 1, alors n est divisible par 3.

9
Solution :
I Soit p le plus petit facteur premier de n. p divise 2n + 1, donc également 22n − 1 =
(2n + 1) (2n − 1). Or p divise 2p−1 − 1 d'après le théorème de Fermat. Donc p divise 2d − 1,
d étant le Pgcd de (p − 1) et 2n, d'après l'exercice précédent.
Mais p − 1 est premier avec n, puisque p − 1 < p et p est le plus petit facteur premier
de n, tout entier strictement inférieur à p est premier avec n. Donc Pgcd (p − 1, 2n) =
Pgcd (p − 1, 2) = 1 ou 2. En d'autres termes, p doit divise 21 − 1 = 1 ou 22 − 1 = 3 : seul
p = 3 convient.
De fait, 3 divise 23 + 1 et il existe une innité de n multiples de 3 tels que n divise
2n + 1. J

Théorème chinois
Peut-on trouver un nombre impair, qui soit congru à 2 modulo 7 et à 17 modulo 33 ?
Certes ! Ce résultat est connu de longue date des Chinois (d'où son nom), et peut s'énoncer
ainsi de manière très générale :

Théorème 7

Soient a1 , a2 , . . . , ak k entiers positifs deux à deux premiers entre eux, et b1 , b2 , . . . , bk k

entiers quelconques. Posons A = a1 a2 . . . ak . Il existe un et un seul entier B vériant :
0 6 B < A tel que le système d'équation :

x ≡ b1 (mod a1 )
x ≡ b2 (mod a2 )
..
.
x ≡ bk (mod ak )

est équivalent à x ≡ B (mod A).

• x congru à b1 modulo a1
• x congru à b2 modulo a2
...
• x congru à bk modulo ak
soit équivalent à x congru à B modulo A.

À titre d'exemple x ≡ 1 (mod 2), x ≡ 2 (mod 7) et x ≡ 17 (mod 33) équivaut à

x ≡ 149 (mod 462). Mais comment démontre-t-on ce théorème, et comment trouve-t-on
B?
Pour tout i, posons A = ai qi (qi est le produit de tous les aj autres que ai ). ai étant
premier avec chaque aj , par hypothèse, il est premier avec leur produit qi , donc, d'après
Bézout, il existe ui et vi tels que ui ai + vi qi = 1, ce qui entraîne vi qi ≡ 1 (mod ai ). Par
ailleurs, vi qi ≡ 0 (mod aj ) pour tout aj autre que ai . De sorte que l'entier

B 0 = b1 v1 q1 + b2 v2 q2 + . . . + bk vk qk

est bien solution du système d'équations. Et il en va de même de tout entier x ≡ B 0

(mod A), dont un et un seul, B , vérie 0 6 B < A.

10
 Réciproquement, si x et x0 sont deux solutions du système d'équations, pour tout i on
a x ≡ x0 (mod ai ). Il en découle que x − x0 est divisible par chacun des ai , donc par leur
Ppcm, en l'occurrence leur produit A (puisqu'ils sont deux à deux premiers entre eux).
Dans notre exemple, on a :

A = 2 × 7 × 33 = 462
a1 = 2 q1 = 231 116 × 2 − 1 × 231 = 1
a2 = 7 q2 = 66 19 × 7 − 2 × 66 = 1
a3 = 33 q3 = 14 3 × 33 − 7 × 14 = 1
donc :

B 0 = 1 × (−1 × 231) + 2 × (−2 × 66) + 17 × (−7 × 14) = −2161 = (−10 × 231) + 149

ce qui entraîne B = 149.

Exercice : Montrer que quel que soit l'entier n strictement positif, on peut trouver n entiers
strictement positifs consécutifs dont aucun n'est premier.

Solution :
I  quel que soit n  signie ici  aussi grand que soit n , et cet exercice prouve que la
distance de deux nombres premiers consécutifs peut être aussi grande que l'on veut. Cette
distance de deux nombres premiers consécutifs pk et pk+1 pose d'ailleurs bien des problèmes
fort diciles : il est vraisemblable qu'il existe une innité de nombres premiers pk tels que
pk+1 − pk = 2 (nombres premiers jumeaux), et dans l'autre sens, il est vraisemblable que
cette diérence pk+1 − pk est majorée, par exemple par une fonction du type pk+1 − pk <
√
c1 pk , ou même pk+1 − pk < c2 (ln pk )2 , c1 et c2 étant deux constantes que, suivant les
démonstrations, on peut calculer ou on ne peut pas calculer... Mais indépendamment des
constantes, ces résultats restent à démontrer.
Toujours est-il que pk+1 −pk n'est pas majoré par une constante, c'est l'objet du présent
exercice : grâce au théorème chinois, c'est simple à prouver. Comme il existe une innité
de nombres premiers, choisissons en n : p1 , p2 , . . . , pn distincts, donc deux à deux premiers
entre eux. Le système d'équations :
x ≡ −1 (mod p1 )
x ≡ −2 (mod p2 )
..
.
x ≡ −n (mod pn )

est équivalent à x ≡ B (mod A), avec A = p1 p2 . . . pn et 0 < B < A.

Pour tout i, A + B + i est divisible par pi , et il n'est pas égal à pi , car il est strictement
supérieur à A = p1 p2 . . . pn . Donc A + B + i n'est pas premier. A + B + 1, A + B + 2, . . . , A +
B + n sont bien n entiers strictement positifs consécutifs dont aucun n'est premier. J

5 Exercices
Exercice 1.
Trouver tous les triplets d'entiers strictement positifs x, y , z tels que :
1 2 3
+ − =1
x y z

11
 Exercice 2.
Montrer qu'il existe une innité de nombres premiers de la forme 6n + 5.

Exercice 3.
Quel est le plus grand diviseur commun de tous les a13 − a, a prenant toutes les valeurs
entières strictement positives ?

Exercice 4.
Montrer que le numérateur de la fraction :
1 1 1 1 1 1
1− + − + ... + − +
2 3 4 1333 1334 1335
est divisible par 2003.

Exercice 5.
Trouver tous les couples d'entiers strictement positifs a et b tels que Ppcm (a, a + 5) =
Ppcm (b, b + 1).

Exercice 6.
Pour quelles valeurs de l'entier n > 0, le nombre n4 + 4n est-il un nombre premier ?

Exercice 7 (Théorème de Wilson).

Montrer que (p − 1)! est congru à −1 modulo p si et seulement si p est premier.

Exercice 8.
a) Montrer (nombres de Fermat) que si 2n + 1 est premier, n est une puissance de 2.
La réciproque est fausse : montrer que 232 + 1 est divisible par 641 = 54 + 24 = 5 × 27 + 1.
b) Montrer (nombres de Mersenne) que si 2n − 1 est premier, n est un nombre premier.
La réciproque est fausse : le nombre 211 − 1 est divisible par 23.

Exercice 9.
Le symbole [x] désignant la partie entière de x, plus grand entier inférieur ou égal à x,
calculer : · ¸ · ¸ · ¸ · ¸
n+1 n+2 n+4 n + 2k
+ + + ... + + ...
2 4 8 2k+1

Exercice 10.
On construit une suite d'entiers en posant u0 = 20002003 et pour tout n > 0, un+1 =
un + 7 si un est impair, un+1 = u2n si un est pair.
Quel est le plus petit entier atteint par cette suite un ?

Exercice 11.
Trouver tous les couples d'entiers strictement positifs (x, y) tels que 7x − 3 × 2y = 1.

Exercice 12.
Montrer que pour tout entier n > 3, il existe deux entiers positifs impairs xn et yn tels
que :
7x2n + yn2 = 2n

Exercice 13.
Montrer que toute progression arithmétique innie qui contient un carré et un cube
contient une puissance sixième.

12
6 Solution des exercices
Exercice 1.
Une condition d'existence de solutions, c'est que x1 + y2 > 1. Il est clair que si x > 3
et y > 3, cette condition n'est pas vériée. Les solutions vérient donc x = 1 ou x = 2 ou
y = 1 ou y = 2.
Pour x = 1, l'équation se ramène à y2 = z3 , qui admet une innité de solutions : y = 2k ,
z = 3k . De même pour y = 2, l'équation se ramène à x1 = z3 , qui admet une innité de
solutions : z = 3x.
Pour y = 1, z3 = x1 + 1 donc z3 > 1, z < 3 : z = 1 ne fournit pas de solution, z = 2
fournit la solution x = 2.
Pour x = 2, on a y2 = z3 + 21 . Ce n'est possible que si y2 > 21 , donc y < 4 : hormis y = 1
et y = 2 déjà étudiés, cela fournit une solution : y = 3 et z = 18.
En dénitive, les triplets solutions sont (1, 2k, 3k), (x, 2, 3x), (2, 1, 2) et (2, 3, 18).

Exercice 2.
L'idée essentielle est qu'un nombre de la forme 6n + 5 admet nécessairement un facteur
premier de la forme 6n+5. En eet, hormis 2 et 3, tous les nombres premiers sont congrus à
1 ou 5 modulo 6. Or le produit de nombres congrus à 1 modulo 6 est congru à 1 modulo 6 :
un nombre congru à 5 modulo 6 est impair et non divisible par 3, et ses facteurs premiers
ne peuvent pas être tous congrus à 1 modulo 6.
Par l'absurde, supposons qu'il n'existe qu'un nombre ni de nombres premiers congrus
à 5 modulo 6 : p1 , p2 , . . . pk . Faisons le produit N = p1 p2 . . . pk de ces nombres. N est
congru à 1 ou 5 modulo 6, suivant que k est pair ou impair. Si N congru à 1 modulo 6,
posons N 0 = N + 4, et si N congru à 5 modulo 6, posons N 0 = N + 6. Dans les deux cas,
N 0 est congru à 5 modulo 6. Donc N 0 possède un facteur premier p congru à 5 modulo 6. Si
p était dans l'ensemble {p1 , . . . , pk }, N serait divisible par p et N 0 , congru à 4 ou 6 modulo
p. C'est impossible, car p ne divise pas 4 ni 6. Donc p n'est pas dans cet ensemble, et
l'hypothèse qu'il existe un nombre ni de nombres premiers congrus à 5 modulo 6 conduit
à une contradiction.

Exercice 3.
Le plus grand diviseur commun de tous les a13 − a divise entre autres 213 − 2 = 8190 =
2 × 32 × 5 × 7 ס 13. Reste
¢ à voir si tous ces facteurs premiers divisent tous les a13 − a.
13 12
a − a = a a − 1 . Soit p un nombre premier. Comme p divise a p−1 − 1 pour tout
12
a non multiple de p (théorème de Fermat), si p − 1 divise 12, p divise a − 1 pour tout
a non multiple de p, donc p divise a13 − a pour tout a, même multiple de p. Cela vaut
précisément pour p = 2, 3, 5, 7 et 13. Reste à voir si 32 divise tous les a13 − a, et il est clair
que ce n'est pas le cas : il sut de choisir a = 3, 9 divise 313 donc ne divise pas 313 − 3. Le
plus grand commun diviseur de tous les a13 − a est donc 2730 = 2 × 3 × 5 × 7 × 13.

Exercice 4.
Avant tout, il faut savoir que 2003 est un nombre premier. Il faut transformer cette
somme avant de la réduire au même dénominateur, et l'idée essentielle est de se débarrasser

13
des termes négatifs. On écrit :
1 1 1 1 1 1
S = 1 − + − + ... + − +
µ 2 3 4 1333 1334 1335 ¶ µ ¶
1 1 1 1 1 1 1 1 1
= 1 + + + + ... + + + −2 + + ... +
2 3 4 1333 1334 1335 2 4 1334
1 1 1 1
= + + ... + +
668 669 1334 1335
On remarque ensuite que :
1 1 2003
+ =
668 1335 668 × 1335
et plus généralement :
1 1 2003
+ =
668 + k 1335 − k (668 + k) × (1335 − k)
pour tout k compris entre 0 et 333, de sorte que :
2003 2003 2003
S= + + ... +
668 × 1335 669 × 1334 1001 × 1002
Ce qui peut s'écrire, en posant S = pq :
µ ¶
p 1 1 1 p0
= 2003 + + ... + = 2003 0
q 668 × 1335 669 × 1334 1001 × 1002 q
Il en résulte que 2003p0 q = pq 0 . Or 2003 est un nombre premier, il est donc premier avec
tous les entiers qui lui sont inférieurs, en particulier avec tous les facteurs du dénominateur
commun q 0 = 668 × 1335 × 669 × 1334 × . . . × 1001 × 1002. D'après le théorème de Gauss,
comme 2003 est premier avec q 0 et qu'il divise pq 0 , il divise p, numérateur de S , ce qui
achève la démonstration.

Exercice 5.
Les nombres b et b + 1 étant premiers entre eux, Ppcm (b, b + 1) = b (b + 1). Il n'en va
pas de même de a et a + 5 : Pgcd(a, a + 5) divise 5, et peut donc être égal soit à 1 soit à
5, ce qui conduit à deux cas distincts.
Premier cas : a n'est pas divisible par 5, donc Ppcm(a, a + 5) = a(a + 5). L'équation
se ramène à a(a + 5) = b(b + 1), soit a2 − b2 = b − 5a. Si b 6 a, le premier membre de
l'égalité serait positif et le second négatif. Donc b > a, 0 > a2 − b2 = b − 5a > −4a. Or
a2 − b2 = (a − b)(a + b), avec (a + b) > 2a. Il en résulte que (a − b) ne peut être égal qu'à
−1 : si (a − b) 6 −2, (a − b)(a + b) < −4a. Il sut donc de remplacer a par b − 1 pour
conclure. L'équation devient (b − 1)(b + 4) = b(b + 1) soit 2b − 4 = 0. De fait, a = 1 et
b = 2 fournit une solution, la seule pour laquelle a est non divisible par 5.
Deuxième cas : a est divisible par 5, donc Ppcm(a, a + 5) = a(a+5) 5 . Posons a = 5a0 ,
pour être sûr que la condition  a divisible par 5  sera vériée par les solutions que
l'on 0 0
¡ va0 trouver. ¢L'équation 2devient 5a (a + 1) = b(b + 1). Soit en multipliant par 4 :
5 (2a + 1) − 1 = (2b + 1) − 1. Si l'on pose y = 2a0 + 1 et x = 2b + 1, il reste à trouver
2

x et y impairs tels que 5y 2 − x2 = 4.

x = y = 1 convient évidemment, conduisant à a0 = b = 0, solution triviale et exclue
car a et b sont supposés strictement positifs. Mais il existe une innité d'autres solutions,
car il s'agit là d'une équation d'un type classique appelée  équation de Pell-Fermat .

14
 ¡ √ ¢¡ √ ¢
L'idée est d'écrire x2 −5y 2 = x + y 5 x − y 5 . Parmi les nombres réels de la forme
¡ √ ¢ ¡ √ ¢¡ √ ¢
a + b 5 , certains sont des  unités , c'est-à-dire vérient a + b 5 a − b 5 = 1 ou
¡ √ ¢¡ √ ¢ ¡ √ ¢¡ √ ¢
−1. Notamment 2 + 5 2 − 5 = −1. Si l'on multiplie 2 + 5 x + y 5 = x0 +
√ ¡ √ ¢¡ √ ¢ √ ¡ ¢
y 0 5, on a également 2 − 5 x − y 5 = x0 − y 0 5, donc x0 2 − 5y 0 2 = (−1) x2 − 5y 2 .
Ainsi, à partir d'un couple (x, y) vériant x2 − 5y 2 = −4, on peut en trouver un autre
vériant x0 2 − 5y 0 2 = 4, avec x0 = 2x + 5y , y 0 = x + 2y , puis un autre vériant x00 2 − 5y 00 2 =
−4, avec x00 = 2x0 + 5y 0 = 9x + 20y , y 00 = x0 + 2y 0 = 4x + 9y , et une innité d'autres par le
même algorithme. On remarque que si x et y sont impairs, x00 et y 0 ” sont eux aussi impairs.
Mais une autre remarque importante est que, par un tel algorithme, on peut, à partir
d'une solution quelconque, en trouver une autre plus petite, sous certaines conditions. Si
(x, y) vérient x2 − 5y 2 = −4, (9x − 20y, 4x − 9y) vérient la même relation, et on a
0 < 9x − 20y < x sauf si x > 25 y ou x 6 20 5 2 2
9 y . Si x > 2 y , x − 5y > 0 ne peut pas
20 2 2 5 2
être égal à −4. Par contre, si x < 9 y , x − 5y < − 81 y peut être égal à −4 pour peu
que y 2 < 4 × 81 5 , donc que y 6 8. On cherche à la main (ou à la machine) toutes les
solutions pour lesquelles y 6 8, en n'oubliant pas que x et y sont supposés impairs : on
trouve (1, 1) et (11, 5). Toutes les autres s'y ramènent par réitération de l'algorithme ci-
dessus. Comme cet algorithme peut être utilisé dans les deux sens, toutes les solutions de
l'équation cherchée se déduisent de ces deux solutions-ci, mais il y en a une innité. On
√ ¡ √ ¢¡ √ ¢k √ ¡ √ ¢¡ √ ¢k
peut écrire xk + yk 5 = 1 + 5 9 + 4 5 et x0 k + y 0 k 5 = 11 + 5 5 9 + 4 5 ,
(xk , yk ) et (x0 k , y 0 k ) sont toutes les solutions de x2 −5y 2 = −4. Tous ces entiers sont impairs
et on en déduit toutes les solutions ak = 25 (yk − 1), bk = ( 21 (xk − 1), a0 k = 25 (y 0 k − 1),
b0 k = 12 (x0 k − 1), de Ppcm(a, a + 5) = Ppcm(b, b + 1) pour lesquelles a est divisible par 5.
La première d'entre elles est a = 10, b = 5√ .
Les ensembles de réels du type a + b 5 sont des anneaux d'entiers algébriques, qui
possèdent un grand intérêt en arithmétique. Mais il faut prendre garde que la divisibilité
ne possède pas nécessairement les mêmes propriétés dans ces ensembles que dans Z, notam-
ment le théorème de Gauss et l'unicité de¡ décomposition √ ¢¡ √ en
¢ facteurs premiers est rarement
vériée. Par exemple, −4 = 2 × (−2) = 1 + 5 1 − 5 . L'étude de la divisibilité dans
de tels ensembles a fait beaucoup progresser les mathématiques depuis le XIXème siècle.

Exercice 6.
Il est clair que n doit être impair, sinon n4 + 4n est multiple de 4. Par ailleurs, n = 1
convient, et il est vraisemblable que c'est la seule solution : si un tel exercice admettait des
solutions non triviales, il serait quasiment impossible à résoudre à la main. Mais encore
faut-il le prouver.
On utilise¡ pour cela une ¢égalité
¡ connue sous
¢ le nom d'égalité de Sophie Germain :
x4 + 4y 4 = x2 − 2xy + 2y 2 x2 + 2xy + 2y 2 , qui se démontre très élémentairement :
¡ 2 ¢2 ¡ ¢2
x + 2y 2 = x4 + 4x2 y 2 + 4y 4 , donc x4 + 4y 4 = x2 + 2y 2 − (2xy)2 . L'entier n4 + 4n =
³ n−1 ´2
n4 + 4 2 2 sera donc non premier, sauf si l'un des facteurs est égal à 1 ou −1. Or
¡ 2 ¢
x − 2xy + 2y 2 = (x − y)2 + y 2 > 0 ne peut être égal à 1 que si l'un des carrés est nul
¡ ¢ n−1
et l'autre égal à 1, de même pour x2 + 2xy + 2y 2 = (x + y)2 + y 2 . Mais y = 2 2 n'est
jamais nul, et vaut 1 seulement pour n = 1. Pour tout autre n, n4 + 4n est donc non
premier.

Exercice 7.
Un peu moins important que le théorème de Fermat, ce théorème de Wilson s'utilise
surtout dans un sens : montrer que si p est premier, (p − 1)! congru à −1 modulo p.

15
 Si p est premier, p est premier avec tous les entiers non nuls qui lui sont inférieurs :
d'après Bézout, si 0 < a < p, il existe u tel que ua + vp = 1, u est manifestement non nul
et quitte à remplacer u par u + kp, v par v − ka, on peut imposer 0 < u < p. En d'autres
termes, à tout entier a vériant 0 < a < p on peut associer un autre entier u vériant lui
aussi 0 < u < p et tel que ua congru à 1 modulo p. Cet entier est unique, car ua congru à
1 congru à u0 a modulo p entraînerait (u − u0 )a divisible par p. p ne divisant pas a, p doit
diviser (u − u0 ), or 1 − (p − 1) 6 u − u0 6 (p − 1) − 1 : dans cet intervalle, seul 0 est multiple
de p. Il en résulte également que si à a on associe u, à u on associe a. Hormis 1 et p − 1,
tous les autres entiers compris entre 1 et p − 1 peuvent se grouper en paires {a, u} telles
que au congru à 1 modulo p. Mais peut-on avoir u = a ? ce qui revient à dire : peut-on
avoir a2 congru à 1 modulo p ? Cela signierait que a2 − 1 = (a − 1)(a + 1) est divisible
par p, donc que p divise soit a − 1 (donc a = 1), soit a + 1 (donc a = p − 1).
Il convient d'étudier séparément p = 2 et p = 3. 1! = 1 congru à −1 modulo 2 et 2! = 2
congru à −1 modulo 3. Pour tout autre p, les entiers strictement compris entre 0 et p se
classent en trois familles : 1, p − 1, et les autres, ces derniers se groupant en paires {a, u}
telles que au congru à 1 modulo p. Le produit de tous les entiers autres que 1 et p − 1 est
donc congru à 1 modulo p, et si je multiplie ce produit par 1 et par p − 1, j'ai (p − 1)!
congru à −1 modulo p. Par exemple :
10! = 1 × 10 × (2 × 6) × (3 × 4) × (5 × 9) × (7 × 8)
(2 × 6), (3 × 4), (5 × 9) et (7 × 8) étant tous quatre congrus à 1 modulo 11, le produit est
bien congru à 10 (donc à −1) modulo 11.
Si maintenant p n'est pas premier, p admet au moins un diviseur d strictement compris
entre 1 et p. Posons p = dq . Si q n'est pas égal à d, q et d apparaissent tous deux dans
(p − 1)! = 1 × 2 × . . . × (p − 1), donc (p − 1)! est divisible par p. Si q = d, soit d > 3 et dans
le produit (p − 1)! = 1 × 2 × . . . × (p − 1) on trouve d et 2d, ce qui prouve que le produit
est divisible par 2d2 , donc par p = d2 . Soit d = 2 et 3! congru à 2 modulo 4, ce qui achève
la démonstration.

Exercice 8.
a) Supposons que n possède un diviseur impair p > 1, et posons n = pq . Comme xp +y p
est divisible par x + y lorsque p est impair, 2n + 1 = (2q )p + 1p est divisible par 2q + 1,
donc n'est pas premier. Pour que 2n + 1 soit premier, il est nécessaire que n n'admette que
des diviseurs pairs, donc que n soit une puissance de 2. Mais c'est loin d'être susant ! Par
exemple, comme
¡ l'a
¢ démontré Euler, 232 + 1 est
¡ divisible
¢ par 641. En eet, 641 = 54 + 24
4
divise 228 54 + 24 et 641 = 5 × 27 + 1 divise 5 × 27 − 1, donc 641 divise la diérence,
à savoir 232 + 1. Il se peut même que les seuls nombres de Fermat premiers soient pour
n = 1, 2, 4, 8 et 16. On en a étudié une trentaine d'autres, et aucun d'eux n'était premier
(ces nombres de Fermat deviennent vite extrêmement grands).
b) Si n possède un diviseur p autre que 1 et n, posons n = pq . xp − y p est divisible par
x − y , que p soit pair ou impair. Donc 2n − 1 = (2q )p − 1p est non premier, car divisible par
2q − 1, qui n'est pas égal à 1 puisque q > 1. Pour que 2n − 1 soit premier, il est nécessaire
que n soit premier. Une fois encore, c'est loin d'être susant 211 −1 = 23×89. Sur plusieurs
centaines de milliers de nombres de Mersenne étudiés, moins de quarante sont premiers,
mais il demeure probable qu'il existe une innité de nombres de Mersenne premiers.

Exercice 9. h i
n+2k
Il est clair que cette somme ne possède qu'un nombre ni de termes non nuls, 2k+1
est
nul dès que 2k+1 > n + 2k , donc 2k > n. Cet énoncé d'Olympiade internationale se résout

16
 £ ¤
facilement si l'on connaît le lemme : pour tout £ réel¤ x, [2x] = [x] + x + 21 qui se vérie
1 1 1
immédiatement
£ ¤ : si n 6 x < n + 2 , [x] = n = x + 2 et [2x] = 2n, et si n + 2 6 x < n + 1,
1
[x] = n, x + 2 = n + 1, et [2x] = 2n + 1. Il en résulte que :
· ¸ · ¸ h i h
n + 2k n 1 n n i
= + = −
2k+1 2k+1 2 2k 2k+1

La somme s'écrit donc :

³ h n i´ ³h n i h n i´ ³h n i h n i´
[n] − + − + − + ...
2 2 4 4 8
et par  simplication téléscopique , elle vaut [n], soit n si n est un entier.

Exercice 10.
Quel peut être le plus petit entier atteint par cette suite un ? Si un > 7, soit un est
pair et un+1 = u2n est inférieur à un . Soit un est impair, un+1 = un + 7 est pair, donc
un+2 = un2+7 < un . Il en résulte que la plus petite valeur ne peut pas être strictement
supérieure à 7. Mais elle peut être égale à 7, car si un = 7, les termes suivants sont
14, 7, 14, 7, . . . et la suite ne descend plus. Si un = 2, 4 ou 6, alors un+1 = u2n est strictement
inférieur à un . Si un = 5, les termes suivants sont 12, 6, 3, 10, 5, 12, . . . et la suite descend
jusqu'à 3. De même si un = 3. Enn, si un = 1, un ne peut pas descendre plus bas, les
termes suivants de la suite étant 8, 4, 2, 1, 8, 4, . . .. Le plus petit entier atteint par cette suite
peut être soit 1, soit 3, soit 7, tout dépend quel est le nombre de départ.
Pour atteindre 7, il faut que tous les termes de la suite soient multiples de 7, car un+1
est divisible par 7 si et seulement si un est divisible par 7. Or il est clair que 20002003
n'est pas multiple de 7 car 2000 n'est pas multiple de 7. Plus précisément, 2000 congru à
5 modulo 7, car 1995 = 7 × 285. 52 congru à 4 modulo 7, 53 congru à 5 × 4 congru à 6
modulo 7, 54 congru à 5 × 6 congru à 2 modulo 7, 55 congru à 5 × 2 congru à 3 modulo
7 et (comme permettait de le prévoir le théorème de Fermat) 56 congru à 5 × 3 congru à
1 modulo 7. Pour tout k , 56k sera donc congru à 1 modulo 7, en particulier 51998 (puisque
1998 = 6 × 333). D'où 52003 congru à 55 congru à 3 modulo 7, puisque 2003 = 1998 + 5. Il
en résulte que 20002003 congru à 3 modulo 7.
Or l'algorithme transforme un nombre congru à 3 modulo 7 :
 s'il est impair, en un autre nombre congru à 3 modulo 7 (puisqu'on ajoute 7)
 s'il est pair, en un nombre congru à 5 modulo 7 (puisque 2 × 5 congru à 3 modulo 7)
Un nombre congru à 5 modulo 7 est transformé, s'il est impair, en un autre nombre
congru à 5 modulo 7, et s'il est pair, en un nombre congru à 6 modulo 7. Un nombre congru
à 6 modulo 7 est transformé, s'il est impair, en un autre nombre congru à 6 modulo 7, et
s'il est pair, en un nombre congru à 3 modulo 7.
La boucle est bouclée : à partir d'un nombre congru à 3 modulo 7, en réitérant autant
de fois que l'on veut l'algorithme, on ne peut obtenir que des nombres congrus à 5, 6 ou 3
modulo 7. On ne peut donc jamais atteindre le nombre 1 : le plus petit entier atteint par
cette suite est 3.

Exercice 11.
Cette équation est plus manipulable si on l'écrit 7x − 1 = 3 × 2y , car 7x − 1 peut se
factoriser alors que 7x − 3 × 2y , on ne peut pas en faire grand chose.
¡ ¢
7x − 1 = (7 − 1) 7x−1 + 7x−2 + . . . + 7 + 1

17
On peut donc simplier par 6, ce qui donne 7x−1 + 7x−2 + . . . + 7 + 1 = 2y−1 . Chacun des
x termes de la somme de gauche étant impair, une première condition, si y > 1, est que x
soit pair. Le cas y = 1 doit être étudié séparément, et il fournit une solution : x = y = 1.
Si y > 1 et x pair, on peut regrouper les termes deux par deux et mettre en facteur
(7 + 1) : ¡ ¢
(7 + 1) 7x−2 + 7x−4 + . . . + 72 + 1 = 2y−1
Si y = 2 ou y = 3, 2y−1 n'est pas divisible par 7 + 1, donc il ne peut pas y avoir de solution.
Si y = 4, on trouve une nouvelle solution : x = 2, y = 4. Pour y > 4, en simpliant par 8,
on est ramené à :
7x−2 + 7x−4 + . . . + 72 + 1 = 2y−4
Une fois encore, chacun des x2 termes de la somme de gauche étant impair, x
2 doit être pair.
On peut à nouveau regrouper les termes deux par deux, et écrire :
¡ 2 ¢¡ ¢
7 + 1 7x−4 + 7x−8 + . . . + 74 + 1 = 2y−4

Seulement là, le membre de gauche est divisible par 72 + 1 = 50, alors que le membre
de droite est une puissance de 2, il ne peut pas y avoir égalité. Les seules solutions de
l'équation sont donc : (1, 1) et (2, 4).

Exercice 12.
Si l'on n'avait pas la condition  xn et yn impairs , cet exercice serait très simple : il
surait de trouver (x3 , y3 ) et (x4 , y4 ), et de les multiplier par une puissance de 2 convenable.
Pour n = 3, 7 × 12 + 12 = 23 , et pour n = 4, 7 × 12 + 32 = 42 . Donc pour n = 2k + 3,
¡ ¢2 ¡ ¢2 ¡ ¢2 ¡ ¢2
7 × 2k + 2k = 22k+3 et pour n = 2k + 4, 7 × 2k + 3 × 2k = 22k+4 .
Mais il faut trouver des nombres impairs. Et montrer qu'ils existent, cela revient habi-
tuellement à expliciter un algorithme pour les construire. Le plus simple étant de construire
xn+1 et yn+1 à partir de xn et yn , de sorte que :
¡ ¢
7x2n+1 + yn+1
2
= 2 7x2n + yn2 (1)

Si, à partir de deux entiers xn et yn impairs vériant x2n + yn2 = 2n , on en trouve deux
autres, xn+1 et yn+1 eux aussi impairs vériant (1), donc vériant x2n+1 + yn+12 = 2n+1 , le
problème est résolu par récurrence, dans la mesure où l'hypothèse de récurrence est vériée
pour n = 3 (et même n = 4).
La relation (1) s'obtient avec xn+1 et yn+1 de la forme :

xn+1 = axn + byn

yn+1 = a0 xn + b0 yn

pour peu que les quatre constantes a, b, a0 , b0 vérient :

7a2 + a02 = 14
14ab + 2a0 b0 = 0
7b2 + b02 = 2

Nous n'avons pas à résoudre ce système d'équations dans sa généralité, il sut d'une
solution particulière quelle que soit la manière de la trouver. La première équation suggère

18
un a0 multiple de 7, et les deux autres si a0 = 7b, b0 = −a, sous réserve que a2 + 7b2 = 2,
donc par exemple que a = b = 21 , ou a = 21 , b = − 21 . En d'autres termes :
µ ¶ µ ¶
x n + yn 2 7xn − yn 2 ¡ ¢
7 + = 2 7x2n + yn2
2 2
tout comme : µ ¶2 µ ¶2
x n − yn 7xn + yn ¡ ¢
7 + = 2 7x2n + yn2
2 2

Il reste à voir si, dans l'hypothèse où xn et yn sont des entiers impairs, xn +y 2

n
et 7xn2−yn
xn −yn 7xn +yn xn +yn xn −yn
(respectivement 2 et 2 ) sont eux aussi des entiers impairs. 2 et 2 sont
manifestement entiers, mais pas de même parité, car leur somme, xn , est par hypothèse
impaire. L'un d'eux est donc impair. Or xn −y 2
n
et 7xn2+yn ont pour somme 4xn , qui est
pair, donc ils sont de même parité. Tout comme xn +y 2
n
et 7xn2−yn qui, eux aussi, ont pour
xn −yn
somme 4xn et sont donc de même parité. Si 2 est impair, on pose xn+1 = xn −y 2 ,
n

7xn +yn xn +yn 7xn −yn

yn+1 = 2 , sinon on pose xn+1 = 2 , yn+1 = 2 : dans les deux cas, xn+1
et yn+1 sont des entiers impairs, ce qui achève la démonstration. Notons que si l'un des
entiers ainsi obtenus était négatif, il surait d'en prendre la valeur absolue.

Remarque : Mais cet exercice donne l'occasion de présenter un domaine important des
mathématiques. On étudie souvent les sommes de deux carrés, en remarquant que le produit
de deux sommes de deux carrés est une somme de deux carrés :
¡ 2 ¢¡ ¢ ¡ ¢2 ¡ ¢2
a + b2 a02 + b02 = aa0 − bb0 + ab0 + ba0
On justie ceci en introduisant les entiers Gauss a + ib, nombres complexes, où a et b sont
entiers et i2 = −1. Il en résulte que (a + ib)(a − ib) = a2 + b2 , que l'on note |a + ib|2 , et
l'on a : ¯ ¯ ¯ ¯
¯(a + ib)(a0 + ib0 )¯ = |a + ib| ¯a0 + ib0 ¯
ce qui conduit à la relation ci-dessus. Le fait que dans cet ensemble des entiers de Gauss on
puisse dénir une division euclidienne comme dans Z permet d'y dénir une décomposition
en facteurs premiers comme dans Z et, par exemple, de démontrer que tout nombre premier
congru à 1 modulo 4 est somme de deux carrés.
Or cet anneau des entiers de Gauss n'est pas le seul qui mérite d'être étudié, du point
de vue de la √ divisibilité. Nous avons aaire ici à l'anneau des  entiers algébriques  de la
a+ib 7
forme 2 , a et b étant de même parité, qui lui aussi possède une division euclidienne
et donc une unicité de décomposition en facteurs premiers (ce qui est assez rare dans ce
type d'anneaux). Pourquoi le dénominateur 2 ? Cela n'empêche pas ces nombres d'être
des entiers algébriques, dans la mesure où un entier algébrique est un nombre (réel ou
complexe)√
racine d'une équation à coecients entiers, dont le premier coecient vaut 1.
a+ib 7 2 2
Or 2 est racine de x2 − ax + a +7b4 , et si a et b sont de même parité, a2 congru à
2 2
b2 modulo 4 et le dernier coecient : a +7b 4 est bien entier. La somme et le produit de
deux entiers algébriques étant un entier algébrique, cela justie que l'on travaille avec cet
ensemble, car sans ce dénominateur 2 il manquerait des entiers dans l'ensemble considéré
et l'on n'aurait plus les propriétés de division euclidienne et unicité de la décomposition en
facteurs premiers.
Si l'on pose : Ã √ !n
√ 1+i 7
un + ivn 7 = 2
2

19
il est clair que
à √ !n à √ !n
³ √ ´³ √ ´ 1+i 7 1−i 7
u2n + 7vn2 = un + ivn 7 un − ivn 7 = 4 = 2n+2
2 2
³ √ ´n √
Comme 1+i2 7 est entier algébrique, donc de la forme a+ib2 7 , en multipliant par 2 ou
trouve des un et vn entiers. Et l'unicité de décomposition en facteurs premiers prouve qu'ils
sont impairs, mais c'est beaucoup plus que ce que demande le présent exercice. Toujours
est-il qu'on a là une expression générale des xn et yn cherchés :
xn = |vn−2 | et yn = |un−2 |
√ ³ √ ´n
avec un + ivn 7 = 2 1+i2 7 .

Exercice 13.
Ce problème a été proposé aux Olympiades Internationales 1997, mais il est plus dicile
que les problèmes d'arithmétique habituellement posés aux Olympiades.
La première question, c'est le sens à donner à  progression arithmétique innie . Si
elle est innie dans les deux sens, c'est l'ensemble des entiers congrus à b modulo a, a
étant la raison de la progression arithmétique. Si elle n'est innie que dans un sens, c'est
l'ensemble des ak + b avec k entier positif. Mais cela ne change pas grand chose, car si x6
congru à b modulo a, tous les (x + qa)6 sont eux aussi congrus à b modulo a, et parmi eux,
en prenant q positif susamment grand, on en trouve nécessairement de la forme ak + b
avec k positif. On supposera donc désormais que la progression arithmétique innie est
l'ensemble des entiers congrus à b modulo a.
Supposons donc qu'il existe des entiers x et y tels que x2 congru à b modulo a et y 3
congru à b modulo a. Alors x6 congru à b3 modulo a et y 6 congru à b2 modulo a. Si y est
premier avec a (ce qui équivaut à : si b premier avec a, car tout nombre premier divisant
b et a divise y , et tout diviseur commun de y et a divise b), d'après Bézout il existe u tel
que uy congru à 1 modulo a, donc u6 y 6 x6 congru à b3 modulo a, soit : (ux)6 congru à b
modulo a, et le problème est résolu... dans ce premier cas.
Mais la diculté, c'est lorsque b et a ne sont pas premiers entre eux. Et une idée
astucieuse est de construire une récurrence sur a. L'hypothèse de récurrence s'énonce ainsi :
si une progression arithmétique innie de raison a 6 n contient un carré et un cube,
elle contient une puissance sixième. Pour n = 1, c'est évident, car la seule progression
arithmétique innie de raison 1, c'est Z tout entier, qui contient toutes les puissances
sixièmes. C'est presque aussi évident pour n = 2. Supposons que ce soit vrai pour n, et
montrons que si une progression arithmétique innie de raison a = n + 1 contient un carré
et un cube, elle contient une puissance sixième. En se limitant au cas où b et a ne sont pas
premiers entre eux : appelons d leur Pgcd et p un facteur premier de d, pi étant la plus
grande puissance de p divisant d. Deux cas à envisager : soit p ne divise pas ad , soit p ne
divise pas db , car si p divise ad et db , d n'est pas le Pgcd de a et b.
Si p ne divise pas ad , les congruences x2 congru à b modulo a et y 3 congru à b modulo
a entraînent, a fortiori x2 congru à b modulo pai et y 3 congru à b modulo pai . Mais pai 6 n,
donc, d'après l'hypothèse de récurrence, il existe z tel que z 6 congru à b modulo pai . Et
d'après le théorème chinois, il existe t tel que :
t ≡ z (mod pai )
t ≡ 0 (mod pi )

20
 a
puisque pi est premier avec pi
. Il en résulte :

t6 ≡ z 6 ≡ b (mod pai )
t6 ≡ 0 ≡ b (mod pi )
¡ ¢
puisque b est divisible par d, donc par pi . t6 − b est divisible par pai et par pi , donc par a
puisque pai est premier avec p : il existe bien une puissance sixième congrue à b modulo a.

Si p divise ad mais ne divise pas db , pi+1 divise a mais pas b, donc tous les termes ak + b
de la progression arithmétique sont divisibles par d donc par pi , mais aucun n'est divisible
par pi+1 . En particulier, la plus grande puissance de p divisant x2 est pi (ce qui prouve que
i est pair), et la plus grande puissance de p divisant y 3 est également pi (ce qui prouve que
i est divisible par 3). L'entier i est donc multiple de 6 : i = 6j . Et l'on a x divisible par p3j :
³ ´2 ³ ´
x2 − b étant divisible par a, px3j − pb6j est divisible par pa6j . De même, y est divisible
³ ´3
par p2j , et py2j congru à pb6j modulo pa6j . Comme pa6j 6 n, l'hypothèse de récurrence
s'applique : il existe z tel que z 6 congru à pb6j modulo pa6j . Si la diérence z 6 − pb6j est
¡ ¢6
divisible par pa6j , le nombre zpj − b est divisible par a, on a donc trouvé une puissance
¡ ¢6
sixième, zpj , congrue à b modulo a, ce qui achève la démonstration.

21