PR ÉPARATION OLYMPIQUE FRANÇAISE DE

MATH ÉMATIQUES

OL
N
IO

YM
R AT

PIQ
PA
POFM

PR É

UE
MATH ÉMATIQUES
E NVOI 3 : A RITHM ÉTIQUE
À RENVOYER AU PLUS TARD LE 11 F ÉVRIER 2024

Les consignes suivantes sont à lire attentivement :

- Le groupe junior est constitué des élèves nés en 2009 ou après. Les autres élèves sont dans le
groupe senior.
- Les exercices classés “Juniors” ne sont à chercher que par les élèves du groupe junior.
- Les exercices classés “Seniors” ne sont à chercher que par les élèves du groupe senior.
- Les exercices doivent être cherchés de manière individuelle.
- Utiliser des feuilles différentes pour des exercices différents.
- Respecter la numérotation des exercices.
- Bien préciser votre nom en lettres capitales, et votre prénom en minuscules sur chaque copie.

1
Exercices Juniors
Exercice 1. Soient a, b deux entiers relatifs. Montrer que, si ni a, ni b n’est multiple de 3, alors a4 − b2
est multiple de 3.
Solution de l’exercice 1 Rappelons que si k n’est pas un multiple de 3, alors k vaut 1 ou 2 modulo 3.
Ainsi k2 vaut 12 = 1 ou 22 ≡ 4 ≡ 1 (mod 3) : tout carré d’un nombre non divisible par 4 vaut 1 modulo
3.
Ainsi a4 − b2 ≡ (a2 )2 − b2 ≡ 12 − 1 ≡ 0 (mod 3), donc a4 − b2 est un multiple de 3.

Commentaire des correcteurs : L’exercice a été très bien réussi dans l’ensemble, cependant pas mal
d’élèves pourraient aller plus vite en utilisant des modulos plutôt que les écritures explicites des divisions
euclidiennes, les calculs seraient de fait allégés.

2
Exercice 2. Soit n un entier vérifiant n ⩾ 2. On note d le plus grand diviseur de n différent de n. On
suppose que d > 1. Démontrer que n + d n’est pas une puissance de 2.
Solution de l’exercice 2 Supposons par l’absurde que n + d est une puissance de 2. Notons que d divise
n, donc d divise n + d, donc d divise une puissance de 2. Ainsi d est une puissance de 2 : on pose
d = 2k pour un certain k ∈ N. On a k ⩾ 1 car d ̸= 1. Posons n = da = 2k a avec a ∈ N∗ . Comme d
est différent de n, on a a ⩾ 2. Ainsi 2k−1 a est un diviseur de n, supérieur ou égal à 2k = d, et différent
de n. Par hypothèse d = 2k−1 a, donc a = 2. Ainsi n = 2k+1 .
On trouve alors n+d = 2k (2+1) = 3×2k qui n’est pas une puissance de 2, ce qui est une contradiction.
Ainsi n + d n’est pas une puissance de 2.

Commentaire des correcteurs : L’exercice a été très bien réussi, mais plusieurs copies ont oublié que 1
est un diviseur impair d’une puissance de 2.

3
Exercice 3. Déterminer tous les entiers n ⩾ 0 tels que 2023 + n! est un carré parfait.
Solution de l’exercice 3 Soit n ⩾ 0 tel que 2023 + n! est un carré parfait. Si n ⩾ 4, alors 4 divise n!,
donc 2023 + n! ≡ 2023 ≡ 3 (mod 4). Or 3 n’est pas un carré modulo 4 (les carrés modulo 4 sont 0 et
1), donc on a une contradiction. Ainsi n ⩽ 3.
Notons que 442 = 1936 < 2023+0! = 2023+1! = 2024 < 2023+2! = 2025 = 452 < 2023+3!+2029 <
2116 = 462 . Ainsi pour n = 0, 1, 3, 2023 + n! n’est pas un carré, mais pour n = 2 c’est un carré.
Ainsi 2023 + n! est un carré si et seulement si n = 2.

Commentaire des correcteurs : L’exercice a été très bien réussi. Quelques copies ont oublié le cas n =
0.

4
Exercice 4. Déterminer tous les triplets (p, q, r) de nombres premiers tels que p + q2 = r4 .
Solution de l’exercice 4 Notons que l’équation se réécrit p = (r2 )2 − q2 = (r2 − q)(r2 + q). Come
r2 + q est strictement positif, et p aussi, r2 − q aussi. En particulier, d’après l’équation précédente, on a
que r2 − q = 1 et r2 + q = p. Si r et q sont impairs, alors r2 − q est pair, ce qui est contradictoire. Ainsi
parmi r et q, un est pair, donc vaut 2 car q et r sont premiers.
Si r = 2, alors r2 − q = 1, donc q = 4 − 1 = 3. De plus p = q + r2 = 7, donc (p, q, r) = (7, 3, 2) est
une éventuelle solution.
Si q = 2, alors r2 = q + 1 = 3 ce qui est impossible.
Réciproquement, pour (p, q, r) = (7, 3, 2), p + q2 = 7 + 9 = 16 = 24 .

Commentaire des correcteurs : L’exercice est très bien résolu. Beaucoup d’approches différentes de
celle proposée dans le corrigé étaient envisageables, et les élèves les ont toujours bien mises en oeuvre.

5
Exercice 5. Déterminer tous les quadruplets (a, b, c, d) d’entiers positifs avec a, b, c strictement posi-
tifs tels que

PPCM(b, c) = a + d
PPCM(c, a) = b + d
PPCM(a, b) = c + d

Solution de l’exercice 5 Le système étant symétrique, on suppose que c est le maximum de a, b et c.

Comme c divise PPCM(b, c), c divise a + d. Comme c divise PPCM(c, a), c divise b + d, donc c
divise a + d − (b + d) = a − b. Or −c < a − b < c donc a = b. La dernière ligne donne alors
a = PPCM(a, b) = c + d ⩾ c. Pour avoir égalité, on a donc d = 0 et a = c.
Réciproquement, si a = b = c et d = 0, chaque équation équivaut à a = a + 0, qui est vrai. Les
quadruplets solution sont donc les (a, a, a, 0) pour a ∈ N∗ .

Commentaire des correcteurs : L’exercice a été bien réussi dans l’ensemble. Cependant beaucoup d’élèves
oublient que A divise B n’implique pas A ⩽ B : cela ne marche que si A est positif et B strictement po-
sitif. Si B est uniquement positif, il peut être nul. Et beaucoup d’élèves raisonnent par implication, mais
oublient de vérifier les solutions à la fin : en compétition cela coûte systématiquement un point.

6
Exercice 6. Un entier n ⩾ 2 est écrit au tableau. Chaque jour, quelqu’un choisit p un diviseur premier
de l’entier écrit n au tableau, efface celui-ci et écrit n + n
p
à la place. Montrer que p = 3 est choisi une
infinité de fois.
Solution de l’exercice 6 Fixons N ∈ N. Notons 2ak 3bk ck l’entier écrit au tableau le jour k, avec ck
produit de nombres premiers distincts de 2 et 3. Supposons par l’absurde qu’on peut ne jamais choisir
p = 3 à partir du jour N.
Si le k-ième jour on choisit p ̸= 2, 3, alors le nombre écrit au tableau devient 2ak 3bk cpk (p + 1). Posons
p + 1 = 2b 3c d avec b, c, d des entiers positifs et d premier avec 2 et 3. Comme p est premier et différent
de 2, il est pair, donc a ⩾ 1, donc d ⩽ p+1 2
. Ainsi comme le nombre écrit au tableau est 2ak +a 3bk +b cpk d,
donc ak+1 = ak + a, bk+1 = bk + b et ck+1 = cpk d ⩽ ck p+1 2p
< ck .
Si le k-ième jour on choisit p = 2, le nombre écrit au tableau devient 23 2ak 3bk ck = 2ak −1 3bk +1 ck .
En particulier, la suite (ck )k⩾N décroı̂t et est strictement positive. Elle ne peut donc décroı̂tre strictement
infiniment souvent, sinon elle deviendrait négative. Donc à partir d’un certain jour k > N, on ne choisit
plus p ̸= 2, 3, donc p = 2 est choisit chaque jour à partir du k-ième jour.
Or si à partir du jour k > N on ne choisit que p = 2, alors aj+1 = aj − 1 pour tout j ⩾ k. Donc la suite
d’entiers (aj )j⩾k décroı̂t strictement, elle doit donc devenir strictement négative ce qui est absurde.
Ainsi, on est obligé de choisir au moins une fois p = 3 après le N-ième jour.
Supposons que p = 3 n’est pas choisi une infinité de fois. A partir d’un certain jour, noté N, p = 3 n’est
plus jamais choisi. Cela contredit ce qu’on vient de prouver : p = 3 est donc choisi une infinité de fois.

Commentaire des correcteurs : L’idée du raisonnement derrière l’exercice a généralement été com-
prise, mais les solutions ont été assez mal rédigées dans leur ensemble, préférant des descriptions infor-
melles à des énoncés précis et soigneusement démontrés. Rédiger de telles démonstrations au collège
n’est certainement pas chose facile, mais est tout de même nécessaire pour éviter quelques écueils. Si
ceux-ci étaient mineurs et relativement faciles à contourner dans ce problème (pour peu qu’on les vı̂t,
ce qui était rare), ce n’est pas toujours le cas et des conclusions ”intuitivement vraies” peuvent s’avérer
complètement fausses parce que des étapes cruciales de raisonnement n’auraient pas été envisagées.
Quelques élèves n’ont pas compris la question : il ne s’agissait pas ici de montrer que l’on pouvait choisir
p = 3 une infinité de fois avec un choix judicieux d’opérations. Il fallait montrer que quelle que soit la
suite d’opérations choisie à partir de n’importe quel entier (et même si on essayait d’éviter de le faire),
on doit choisir p = 3 une infinité de fois. Les autres élèves ont, pour la plupart, compris que les facteurs
premiers de n devenaient de plus en plus petits, puisqu’un facteur p > 2 était remplacé par le nombre
pair p + 1, dont tous les facteurs premiers étaient strictement inférieurs à p. Cette intuition est correcte,
mais ne doit pas figurer telle quelle dans une copie, parce que cet énoncé n’est pas clair : en quel sens
les facteurs premiers devenaient-ils de plus en plus petits ? Leur maximum ? Leur nombre ? Une espèce
de combinaison des deux, dirait-on intuitivement, mais encore faut-il la décrire ! Tout le problème d’em-
ployer cette intuition informelle comme une étape de raisonnement est qu’il semble naturel d’en déduire
qu’au bout d’un certain moment, l’entier écrit au tableau n’a plus que des 2 et des 3 comme facteurs
premiers. Ceci n’est pas vrai, puisqu’on peut par exemple multiplier une suite valide par 5. Cela peut
paraı̂tre un contre-exemple trivial, mais cela montre qu’il existe des contre-exemples, et donc qu’il peut
exister des contre-exemples plus subtils que celui-ci. Le corrigé permet de trouver une des façons de for-
maliser cette intuition, en explicitant une quantité entière qui ne peut que décroı̂tre (un ”mono-variant”)
et qui doit donc être constante à partir d’un certain moment. Quelques élèves ont pris une autre approche,
consistant essentiellement à raisonner par récurrence (forte) en se reposant sur l’observation suivante : si
n = ab, alors on peut aussi considérer qu’on a chaque jour deux nombres a et b écrits sur deux tableaux
différents, et qu’on effectue chaque jour l’opération sur l’un des deux tableaux. Partant, l’un ou l’autre
des entiers est modifié selon l’opération une infinité de fois et on a donc par hypothèse de récurrence

7
utilisé p = 3 une infinité de fois.

8
Exercice 7. Soit k un entier premier avec n vérifiant 1 ⩽ k < n. Augustin colorie les entiers de
{1, 2, . . . , n − 1} avec autant de couleur qu’il le souhaite. Cependant, si j est un entier vérifiant 1 ⩽ j ⩽
n − 1, les entiers j et n − j sont de la même couleur. De plus, si i est un entier vérifiant 1 ⩽ i ⩽ n et
i ̸= k, les entiers i et |i − k| sont de la même couleur.
Démontrer que Augustin a colorié tous les entiers de la même couleur.
Solution de l’exercice 7 Pour k = 1, on voit que n a la même couleur que n − 1, puis que n − 2 à la
même couleur que n − 1, etc et tous les entiers ont la même couleur.
Pour k = 2, n est impair et on voit que n, n − 2, . . . , 1 ont la même couleur, puis que n − 1 a la même
couleur que 1, et que n − 1, n − 3, . . . , 2 ont la même couleur.
En faisant la même chose pour des petites valeurs de k, on se rend compte qu’on arrive à chaque fois
à montrer successivement que n − k, . . . , n − (n − 1)k pris modulo n sont tous de la même couleur.
Essayons de formaliser cela.
Notons c la couleur de n. On montre par récurrence la propriété suivante pour tout j ∈ {1, . . . , n − 1} :
P(j) : ”Le reste de la division euclidienne de n − jk n’est pas congru à 0 modulo n, et est colorié avec la
couleur c.
Initialisation : pour j = 1, comme 1 ⩽ n − k ⩽ n − 1, le reste de la division euclidienne de n − k vaut
n − k, n’est pas congru à 0 modulo n, et est colorié avec la couleur c.
Hérédité : Soit j ∈ {0, . . . , n − 2}, supposons que P(j) est vraie et montrons P(j + 1). Notons r le reste
de la division euclidienne de n − jk par n.
Premier cas : si r > k, alors n > r ⩾ r − k > 0. Or r − k ≡ n − jk − k ≡ n − (j + 1)k (mod n). Donc
le reste de la division euclidienne de n − jk par n vaut r − k, est non nul et est de la même couleur que
r, donc de la couleur c ce qui conclut.
Second cas, si r = k, alors n − jk ≡ k (mod n), i.e. (j + 1)k ≡ 0 (mod n). Comme n est premier avec
k, et divise (j + 1)k, n divise j + 1, mais comme j + 1 ∈ {1 . . . , , n − 1}, ce cas est impossible.
Troisième cas : si k > r, alors k − r est de la couleur de de r, donc de la couleur c. De plus on a
1 ⩽ k − r ⩽ k ⩽ n − 1, donc n − (k − r) vérifie 1 ⩽ n − (k − r) ⩽ n − 1 et est de la couleur c. Or
n − (k − r) ≡ r − k ≡ n − (j + 1)k (mod n), donc n − (k − r) est le reste de la division euclidienne
de n − (j + 1)k par n, est non nul et de couleur c, ce qui conclut.
Ceci conclut l’hérédité.
Maintenant donnons nous j ∈ {1, . . . , n − 1}. Il existe ℓ ∈ {0 . . . , n − 1} tel que j ≡ n − ℓk (mod n) : en
effet, ceci est équivalent à ℓk ≡ n − j (mod n), soit à ℓ ≡ (n − j)k−1 (mod n) (où k−1 est l’inverse de
k modulo n, qui existe car k est premier avec n), et admet une solution dans {0 . . . , n − 1}. En particulier,
j est le reste de la divison euclidienne de n − ℓj par n, donc de couleur c. Ainsi tous les entiers de 1 à
n − 1 ont la même couleur que n, donc tous les entiers sont coloriés de la même couleur.

Commentaire des correcteurs : L’exercice est relativement mal résolu : beaucoup de preuves fournies
s’avèrent incomplètes, car elles oublient certaines contraintes (i ̸= k pour dire que |i − k| et i ont la même
couleur, oubli que i et i + k n’ont pas la même couleur si i > n − k, etc).

9
Exercice 8. Déterminer tous les couples (a, p) d’entiers strictement positifs, avec p premier, tels que
n
pour tout couple (m, n) d’entiers strictement positifs, le reste de la division euclidienne de a2 par pn
m
est non nul, et est le même que celui de a2 par pm .
Solution de l’exercice 8 En prenant n = 1 dans l’énoncé, on obtient que pour tout entier m strictement
m
positif, le reste de a2 modulo pm vaut celui de a2 modulo p, donc est constant. Notons r ce reste : on a
donc r ̸= 0 ainsi r ∈ {1, . . . , p − 1}. On a a2 ≡ r (mod p) et a4 ≡ r (mod p2 ), donc a4 ≡ r (mod p),
donc r2 ≡ r (mod p). Ainsi comme r est premier avec p, r est inversible mod p, donc r ≡ 1 (mod p).
m
On a donc a2 ≡ 1 (mod pm ) pour tout m. En particulier a2 ≡ 1 (mod p)
Or
m m−1 m−1 m−1
a2 − 1 = (a2 − 1)(a2 + 1) = · · · = (a2 − 1)(a2 + 1)(a4 + 1) . . . (a2 + 1)
k k−1 m
Si p ⩾ 3, pour tout k ⩾ 1, a2 + 1 ≡ 12 + 1 ≡ 2 ̸≡ 0 (mod p), donc si a ̸= 1 Vp (a2 − 1) =
m m
Vp (a2 − 1). Or pour tout m, pm divise a2 − 1, donc m ⩽ Vp (a2 − 1) = Vp (a2 − 1) ce qui est absurde
car Vp (a2 − 1) est fini. Ainsi a = 1. Réciproquement pour tout p premier, a = 1 est solution car le reste
m
de 12 modulo pm vaut toujours 1 et est non nul.
Si p = 2 et a ̸= 1, a2 ≡ 1 (mod 2), donc a est impair. Réciproquement si a est impair, rappelons que
m m−1 m−1 m−1
a2 − 1 = (a2 − 1)(a2 + 1) = · · · = (a2 − 1)(a2 + 1)(a4 + 1) . . . (a2 + 1)
Le produit de droite contient m termes tous pairs, donc est divisible par 2m . Ainsi pour tout n, le reste
n
de a2 modulo 2n vaut 1 et est non nul, donc tous les couples de la forme (a, 2) avec a impair sont
solutions.
Ainsi les couples solutions sont ceux de la forme (1, p) pour p ⩾ 3 et (a, 2) pour a impair.
m
Solution alternative A partir du fait que a2 ≡ 1 (mod pm ) pour tout m, on a comme p divise a2 − 1,
m
par LTE si p ⩾ 3 que si a > 1, Vp (a2 − 1) = Vp (a2 − 1) + Vp (2m−1 ) = Vp (a2 − 1). En particulier,
m
comme Vp (a2 − 1) ⩾ m pour tout m ⩾ 1, Vp (a2 − 1) ⩾ m pour tout m ce qui est absurde donc a = 1.
Réciproquement, a = 1 et p ⩾ 3 convient comme dans la solution précédente.
Pour le cas p = 2, de même que précédemment on a p impair, donc 4 divise p2 −1 = (p−1)(p+1), donc
m
par LTE, comme 4 divise a4 − 1, si a > 1 V2 (a2 − 1) = V2 (a2 − 1) + V2 (2m−1 ) ⩾ 2 + m − 1 = m + 1,
m
ainsi a2 − 1 est divisible par 2m pour tout m, et on conclut de la même façon que précédemment.

Commentaire des correcteurs : L’exercice est résolu de manière inégale par ceux qui s’y sont essayés.
En effet, certains loupent certaines solutions (soit le cas p = 2 soit le cas a = 1 : les petites valeurs
devraient pourtant permettre de repérer ces solutions. Attention aussi aux utilisations du LTE : le théorème
LTE a des hypothèses, il faut les vérifier sous peine d’écrire des choses fausses.

10
Exercice 9. Déterminer tous les quadruplets (x, y, z, t) d’entiers strictement positifs tels que 2x 3y +
5z = 7t .
Solution de l’exercice 9 Supposons x ⩾ 2, en regardant modulo 4, 1 ≡ 2x 3y + 5z ≡ 7t ≡ (−1)t
(mod 4), donc t est pair.
L’équation prise modulo 3 devient 0 + (−1)z ≡ 1 (mod 3) donc z est pair. En particulier, posons z =
2b, t = 2c, on a alors 2x 3y = (7b − 5c )(7b + 5c ). Le pgcd de 7b + 5c et 7b − 5c divise leur somme
et leur produit, donc il divise 2x 3y et 2 × 7b , ainsi il divise 2. Or 7b + 5c et 7b − 5c sont égaux mod
2 donc ils ont la même parité, et leur produit est pair, donc chacune est pair, leur pgcd vaut 2. Comme
7b − 5c < 7b + 5c , on a (7b − 5c , 7b + 5c ) = (2, 2x−1 3y ), (2x−1 , 2 × 3y ), (2 × 3y , 2x−1 ).
— Dans le premier cas, si c ⩾ 2, modulo 25, 7b ≡ 2 (mod 25). Or les puissances de 7 valent
1, 7, −1, −7 modulo 25, mais jamais 2. Comme c ̸= 0 car z ̸= 0, on a donc c = 1, donc 7b =
5+2 = 7, donc b = 1. On a donc 12 = 2x−1 3y donc (x, y, z, t) = (3, 1, 2, 2), qui réciproquement
est solution car 23 × 3 + 52 = 24 + 25 = 49 = 72 .
— Dans le second cas (7b − 5c , 7b + 5c ) = (2x−1 , 2 × 3y ). Par parité, on a x ⩾ 2, et comme le cas
où x = 2 est déjà couvert par le cas précédent, on peut supposer x ⩾ 3. On pose x ′ = x − 1, on
′
a alors 7b = 5c + 2x avec x ′ ⩾ 2. En regardant modulo 4, (−1)b ≡ 1 (mod 4), donc b est pair.
′
En regardant modulo 5, 2b ≡ 2x (mod 5). Or les puissances de 2 alternent entre 1, 2, 4, 3 mod 5,
donc deux puissances de 2 ont même valeur modulo 5 si et seulement si leur exposant sont égaux
′
modulo 4, donc b et x ′ ont même parité. En regardant modulo 3, 1 ≡ (−1)c + (−1)x (mod 3)
donc c et x ′ sont impairs. Ceci contredit le fait que b et x ′ ont même parité.
Avant de traiter le dernier cas, résolvons l’équation dans le cas x = 1 : on a 2 × 3y + 5z = 7t . Modulo
3, on obtient comme avant que z est pair, donc 5z ≡ 25z/2 ≡ 1 (mod 8). En particulier modulo 8,
(−1)t ≡ 1 + 2 × 3y . Le terme de droite vaut 3 si y est pair, −1 sinon, donc t est impair et y est impair
(car 32 ≡ 1 (mod 8)). On a alors en regardant modulo 5, comme les puissances de 7 valent 1, 2, 4, 3, 1
et les puissances de 3 valent 1, 3, 4, 2, 1, on a 7t ≡ 2 ou 3 car t est impair, et 7 d’ordre 4 (qui est pair)
modulo 5. Comme y est impair, on a 2 × 3y ≡ 1 ou 4 modulo 5 car l’ordre de 3 modulo 5 est pair. Or
l’équation modulo 5 donne 2 × 3y ≡ 7t ce qui est impossible. Il n’y a donc pas de solution avec x = 1.
Pour le troisième cas (7b − 5c , 7b + 5c ) = (2 × 3y , 2x−1 ), on a 7b − 5c = 2 × 3y . Comme c > 0, on est
ramené au cas précédent il n’y a pas de solution.
Ainsi la seule solution est (x, y, z, t) = (3, 1, 2, 2).

Commentaire des correcteurs : L’exercice était très difficile et a été très peu abordé. Il est tout de même
regrettable que les quelques copies qui réussissent à trouver la factorisation ne pensent que rarement à
considérer le pgcd de 7z + 5t et 7z − 5t (ou même simplement la parité de ces deux nombres !) et se
lancent tête baissée dans de grandes disjonctions de cas ou dans des utilisations abusives du théorème
de Zsigmondy, que beaucoup auraient pu s’épargner (un seul élève a su utiliser ce théorème vraiment
efficacement).

11
Exercices Seniors
Exercice 10.
4 2
Soient a, b deux entiers relatifs. Montrer que, si ni a, ni b n’est multiple de 3, alors
a − b est multiple de 3.
Solution de l’exercice 10 Rappelons que si k n’est pas un multiple de 3, alors k vaut 1 ou 2 modulo 3.
Ainsi k2 vaut 12 = 1 ou 22 ≡ 4 ≡ 1 (mod 3) : tout carré d’un nombre non divisible par 4 vaut 1 modulo
3.
Ainsi a4 − b2 ≡ (a2 )2 − b2 ≡ 12 − 1 ≡ 0 (mod 3), donc a4 − b2 est un multiple de 3.

Commentaire des correcteurs : Exercice très bien réussi.

12
Exercice 11. Soit n un entier vérifiant n ⩾ 2. On note d le plus grand diviseur de n différent de n. On
suppose que d > 1. Démontrer que n + d n’est pas une puissance de 2.
Solution de l’exercice 11 Supposons par l’absurde que n+d est une puissance de 2. Notons que d divise
n, donc d divise n + d, donc d divise une puissance de 2. Ainsi d est une puissance de 2 : on pose d = 2k
pour un certain k ∈ N. On a k ⩾ 1 car d ̸= 1. Posons n = da = 2k a avec a ∈ N∗ . Comme d est différent
de n, on a a ⩾ 2. Ainsi 2k−1 a est un diviseur de n, supérieur ou égal à 2k = d, et différent de n. Par
hypothèse d = 2k−1 a, donc a = 2. Ainsi n = 2k+1 .
On trouve alors n+d = 2k (2+1) = 3×2k qui n’est pas une puissance de 2, ce qui est une contradiction.
Ainsi n + d n’est pas une puissance de 2.

Commentaire des correcteurs : Exercice bien réussi, cependant quelques élèves vont un peu trop vite
et oublient des étapes, essentielles pour aboutir à des contradictions, alors injustifiées.

13
Exercice 12. Déterminer tous les quadruplets (a, b, c, d) d’entiers positifs avec a, b, c strictement
positifs tels que

PPCM(b, c) = a + d
PPCM(c, a) = b + d
PPCM(a, b) = c + d

Solution de l’exercice 12 Le système étant symétrique, on suppose que c est le maximum de a, b et c.

Comme c divise PPCM(b, c), c divise a + d. Comme c divise PPCM(c, a), c divise b + d, donc c
divise a + d − (b + d) = a − b. Or −c < a − b < c donc a = b. La dernière ligne donne alors
a = PPCM(a, b) = c + d ⩾ c. Pour avoir égalité, on a donc d = 0 et a = c.
Réciproquement, si a = b = c et d = 0, chaque équation équivaut à a = a + 0, qui est vrai. Les
quadruplets solution sont donc les (a, a, a, 0) pour a ∈ N∗ .

Commentaire des correcteurs : L´exercice est très bien réussi, cependant quelques élèves ont oublié de
vérifier que les solutions trouvées étaient solutions du système ce qui les a pénalisés.

14
Exercice 13. Un entier n ⩾ 2 est écrit au tableau. Chaque jour, quelqu’un choisit p un diviseur premier
de l’entier écrit n au tableau, efface celui-ci et écrit n + n
p
à la place. Montrer que p = 3 est choisi une
infinité de fois.
Solution de l’exercice 13 Fixons N ∈ N. Notons 2ak 3bk ck l’entier écrit au tableau le jour k, avec ck
produit de nombres premiers distincts de 2 et 3. Supposons par l’absurde qu’on peut ne jamais choisir
p = 3 à partir du jour N.
Si le k-ième jour on choisit p ̸= 2, 3, alors le nombre écrit au tableau devient 2ak 3bk cpk (p + 1). Posons
p + 1 = 2b 3c d avec b, c, d des entiers positifs et d premier avec 2 et 3. Comme p est premier et différent
de 2, il est pair, donc a ⩾ 1, donc d ⩽ p+1 2
. Ainsi comme le nombre écrit au tableau est 2ak +a 3bk +b cpk d,
donc ak+1 = ak + a, bk+1 = bk + b et ck+1 = cpk d ⩽ ck p+1 2p
< ck .
Si le k-ième jour on choisit p = 2, le nombre écrit au tableau devient 23 2ak 3bk ck = 2ak −1 3bk +1 ck .
En particulier, la suite (ck )k⩾N décroı̂t et est strictement positive. Elle ne peut donc décroı̂tre strictement
infiniment souvent, sinon elle deviendrait négative. Donc à partir d’un certain jour k > N, on ne choisit
plus p ̸= 2, 3, donc p = 2 est choisit chaque jour à partir du k-ième jour.
Or si à partir du jour k > N on ne choisit que p = 2, alors aj+1 = aj − 1 pour tout j ⩾ k. Donc la suite
d’entiers (aj )j⩾k décroı̂t strictement, elle doit donc devenir strictement négative ce qui est absurde.
Ainsi, on est obligé de choisir au moins une fois p = 3 après le N-ième jour.
Supposons que p = 3 n’est pas choisi une infinité de fois. A partir d’un certain jour, noté N, p = 3 n’est
plus jamais choisi. Cela contredit ce qu’on vient de prouver : p = 3 est donc choisi une infinité de fois.

Commentaire des correcteurs : Certains élèves ont mal compris l’énoncé : il s’agissait de prouver que
l’on était obligé de choisir p = 3 une infinité de fois quels que soient les choix effectués, pas que l’on
pouvait s’arranger pour que ce soit le cas. L’exercice est généralement bien abordé par ceux qui l’ont
correctement interprété, mais de trop nombreux élèves manquent de rigueur. L’enjeu était de trouver un
argument rigoureux (donc a priori un monovariant, que ce soit celui proposé par le corrigé, l’ordre lexi-
cographique inversé des exposants ou beaucoup d’autres possibilités) pour clarifier la phrase lue dans de
trop nombreuses copies : ”les facteurs premiers décroissent”. Cette phrase dénuée de sens mathématique
ne constitue en aucun cas un argument recevable, il faut clarifier l’intuition qui se cache derrière. C’est un
écueil que l’on croise souvent en combinatoire : il est parfois délicat de passer de l’intuition à l’argument
rigoureux, et souvent une partie de la difficulté de l’exercice réside justement dans cette étape.

15
Exercice 14. Soit k un entier premier avec n vérifiant 1 ⩽ k < n. Augustin colorie les entiers de
{1, 2, . . . , n − 1} avec autant de couleur qu’il le souhaite. Cependant, si j est un entier vérifiant 1 ⩽ j ⩽
n − 1, les entiers j et n − j sont de la même couleur. De plus, si i est un entier vérifiant 1 ⩽ i ⩽ n et
i ̸= k, les entiers i et |i − k| sont de la même couleur.
Démontrer que Augustin a colorié tous les entiers de la même couleur.
Solution de l’exercice 14 Pour k = 1, on voit que n a la même couleur que n − 1, puis que n − 2 à la
même couleur que n − 1, etc et tous les entiers ont la même couleur.
Pour k = 2, n est impair et on voit que n, n − 2, . . . , 1 ont la même couleur, puis que n − 1 a la même
couleur que 1, et que n − 1, n − 3, . . . , 2 ont la même couleur.
En faisant la même chose pour des petites valeurs de k, on se rend compte qu’on arrive à chaque fois
à montrer successivement que n − k, . . . , n − (n − 1)k pris modulo n sont tous de la même couleur.
Essayons de formaliser cela.
Notons c la couleur de n. On montre par récurrence la propriété suivante pour tout j ∈ {1, . . . , n − 1} :
P(j) : ”Le reste de la division euclidienne de n − jk n’est pas congru à 0 modulo n, et est colorié avec la
couleur c.
Initialisation : pour j = 1, comme 1 ⩽ n − k ⩽ n − 1, le reste de la division euclidienne de n − k vaut
n − k, n’est pas congru à 0 modulo n, et est colorié avec la couleur c.
Hérédité : Soit j ∈ {0, . . . , n − 2}, supposons que P(j) est vraie et montrons P(j + 1). Notons r le reste
de la division euclidienne de n − jk par n.
Premier cas : si r > k, alors n > r ⩾ r − k > 0. Or r − k ≡ n − jk − k ≡ n − (j + 1)k (mod n). Donc
le reste de la division euclidienne de n − jk par n vaut r − k, est non nul et est de la même couleur que
r, donc de la couleur c ce qui conclut.
Second cas, si r = k, alors n − jk ≡ k (mod n), i.e. (j + 1)k ≡ 0 (mod n). Comme n est premier avec
k, et divise (j + 1)k, n divise j + 1, mais comme j + 1 ∈ {1 . . . , , n − 1}, ce cas est impossible.
Troisième cas : si k > r, alors k − r est de la couleur de de r, donc de la couleur c. De plus on a
1 ⩽ k − r ⩽ k ⩽ n − 1, donc n − (k − r) vérifie 1 ⩽ n − (k − r) ⩽ n − 1 et est de la couleur c. Or
n − (k − r) ≡ r − k ≡ n − (j + 1)k (mod n), donc n − (k − r) est le reste de la division euclidienne
de n − (j + 1)k par n, est non nul et de couleur c, ce qui conclut.
Ceci conclut l’hérédité.
Maintenant donnons nous j ∈ {1, . . . , n − 1}. Il existe ℓ ∈ {0 . . . , n − 1} tel que j ≡ n − ℓk (mod n) : en
effet, ceci est équivalent à ℓk ≡ n − j (mod n), soit à ℓ ≡ (n − j)k−1 (mod n) (où k−1 est l’inverse de
k modulo n, qui existe car k est premier avec n), et admet une solution dans {0 . . . , n − 1}. En particulier,
j est le reste de la divison euclidienne de n − ℓj par n, donc de couleur c. Ainsi tous les entiers de 1 à
n − 1 ont la même couleur que n, donc tous les entiers sont coloriés de la même couleur.

Commentaire des correcteurs : L’exercice est relativement mal résolu : beaucoup de preuves fournies
s’avèrent incomplètes, car elles oublient certaines contraintes (i ̸= k pour dire que |i − k| et i ont la même
couleur, oubli que i et i + k n’ont pas la même couleur si i > n − k, etc). Il est crucial que les élèves
se relisent à froid : certaines copies n’ont vraiment pas de sens en les relisant à froid, et plusieurs élèves
auraient évité une déconvenue en relisant leur production à tête reposée.

16
Exercice 15. Soit (Pn )n∈N une suite de polynômes à coefficients entiers. On suppose qu’il existe un
polynôme Q unitaire à coefficient entier tel que Pn+1 − Pn = Q pour tout n ⩾ 0. On suppose de plus
que pour tout n ⩾ 0, Pn a une racine entière. Montrer qu’on est dans un des deux cas suivants :
— P0 et Q ont une racine entière en commun
— Il existe un polynôme à coefficients entiers R tel que P0 = RQ et le degré de R est 1.
Solution de l’exercice 15 Supposons que P0 et Q n’ont pas de racines entière en commun. Notons que
par récurrence immédiate Pn = P0 + nQ pour tout n ⩾ 0. Notons xn une racine entière de Pn pour tout
n ⩾ 0, on a que nQ(xn ) = −P0 (xn ), donc Q(xn ) divise P0 (xn ).
Notons que si xk = xj avec k ̸= j, alors P0 (xk ) + kQ(xk ) = 0 = P0 (xj ) + jQ(xj ), donc (k − j)Q(xk ) =
0, donc Q(xk ) = 0. Ainsi P0 (xk ) = 0, donc P0 et Q ont une racine entière en commun, ce qui est
contradictoire. Ainsi la suite (xk )k⩾0 est injective donc prend des valeurs arbitrairement grandes.
Faisons la division euclidienne de P0 par Q. Comme Q est unitaire à coefficient entier (et P0 à coefficients
entiers), il existe des polynômes R et S à coefficients entiers tels que P0 = QR+S avec S de degré inférieur
ou égal à Q.
En évaluant en xn , P0 (xn ) = Q(xn )R(xn ) + S(xn ), donc comme Q(xn ) divise P0 (xn ), Q(xn ) divise
S(xn ) = P0 (xn ) − Q(xn )R(xn ). Or pour tout entier k avec |k| assez grand, comme le degré de S est
strictement inférieur à celui de Q, |S(k)| < |Q(k)|. Comme la suite (xn ) prend des valeurs arbitrairement
grande, il existe une infinité de n tels que |S(xn )| < |Q(xn )|. Comme Q(xn ) divise S(xn ), on en déduit
qu’il existe une infinité de n tels que S(xn ) = 0. Comme la suite est injective, S a une infinité de racine,
donc S = 0. Ainsi P0 = QR.
De plus, en évaluant en xn , on a −nQ(xn ) = P0 (xn ) = Q(xn )R(xn ). Si Q(xn ) = 0, alors P0 (xn ) = 0
et P0 et Q ont une racine en commun, contradiction. Ainsi Q(xn ) ̸= 0, donc R(xn ) = −n. Ainsi pour
tout entier N ⩾ 0, il existe au moins N entiers y tels que R(y) ∈ [−N, N].
Or si le degré de R noté d vaut au moins 2, pour un M assez grand et pour un C > 0, on a pour tout
x vérifiant |x| ⩾ M, |R(x)| ⩾ C|x|d . Ainsi pour N assez grand, le nombre d’entier tel que |R(x)| ⩽ N
est plus petit que 2M + 1 (le nombre d’entiers dans [−M, M]), auquel on ajoute le nombre d’entiers
|x| ⩾ M tel que |P(x)| ⩽ N. Pour ces x, on a C|x|d ⩽ N donc |x| ⩽ (N/C)1/d . Ainsi on a au plus
2M + 1 + 2(N/c)1/d + 1 entiers tels que P(y) ∈ [−n, n], ce qui est strictement inférieurs à N pour N
assez grand, ce qui est contradictoire.
Ainsi le degré de R est au plus 1. Comme on a R(xn ) = −n pour tout n, le degré de R vaut 1.
Alternativement, pour prouver que le degré de R valait n, on pouvait remarquer que pour tout n, xn+1 −xn
divise R(xn+1 ) − R(xn ) = −1. En particulier xn+1 − xn = ±1 pour tout n. Comme la suite (xn )
est injective, on ne peut avoir xn+1 − xn = 1 et xn+2 − xn+1 = −1, ou avoir xn+1 − xn = −1
et xn+2 − xn+1 = 1 sinon xn = xn+2 . Ainsi on a facilement par récurrence que soit pour tout n,
xn+1 − xn = 1, et donc xn = x0 + n(x1 − x0 ), soit xn+1 − xn = −1, et donc xn = x0 − n(x1 − x0 ).
Dans le premier cas, en posant S(X) = R(x0 + X(x1 − x0 )) − X, on voit que Q(n) = 0 pour tout n.
Comme S est un polynôme, c’est le polynôme nul, donc pour tout x réel, R(x0 + x(x1 − x0 )) = x. Ainsi
en posant x = xy−x 0
1 −x0
(qui est bien défini car x1 ̸= x0 ), on a que R(y) = xy−x 0
1 −x0
pour tout y, donc par
X−x0
identification R(X) = x1 −x0 : R est de degré 1.
Dans le second cas, en posant S(X) = R(x0 − X(x1 − x0 )) − X, on voit que Q(n) = 0 pour tout n.
Comme S est un polynôme, c’est le polynôme nul, donc pour tout x réel, R(x0 − x(x1 − x0 )) = x. Ainsi
en posant x = xx10−x−y
0
(qui est bien défini car x1 ̸= x0 ), on a que R(y) = xx10−x
−y
0
pour tout y, donc par
X−x0
identification R(X) = x1 −x0 : R est de degré 1.

Commentaire des correcteurs : L’exercice a été très bien traité par les élèves qui l’ont abordé. Presque
tous ont bien vu qu’un R de degré au moins 2 ” croirait et décroirait trop vite” pour attendre tous les
entiers négatifs, mais certains n’ont pas rendu cette idée, certes vraie, rigoureuse. De plus, il faut garder

17
en tête qu’on peut considérer la divison euclidienne de P0 par Q dans Z[X] seulement parce que Q est
unitaire. Enfin, ne jamais oublier les cas triviaux : il est dommage de voir des élèves perdre un point pour
ne pas avoir préciser que R ne pouvait être constant.

18
Exercice 16. Soit p un nombre premier et n un entier vérifiant n ⩾ 2.
— A quelle condition existe-t-il n + 1 entiers (pas forcément distincts) tels que, pour tout choix de
n entiers parmi les n + 1, leur somme est une puissance de p ?
— A quelle condition existe-t-il n + 1 entiers strictement positifs (pas forcément distincts) tels que,
pour tout choix de n entiers parmi les n + 1, leur somme est une puissance de p ?
Solution de l’exercice 16 Essayons d’analyser l’énoncé. Posons x1 , . . . , xn+1 les entiers tels que pour
tout choix de n entiers parmi les n + 1 entiers, alors leur somme est une puissance de p. Il existe donc
α1 , . . . , αn+1 des entiers positifs tels que x2 + · · · + xn+1 = pα1 , x1 + x3 + · · · + xn+1 = pα2 , . . . , x1 +
· · · + xn = pαn+1 .
En particulier, notons déjà que pαi = x1 + · · · + xn+1 − xi pour tout i ∈ {1, . . . , n + 1} et que pα1 +
α1 αn+1
· · · + pαn+1 = n(x1 + · · · + xn+1 ), donc pour tout i ∈ {1, . . . , n + 1}, xi = p +···+p n
− pαi .
α αn+1
Réciproquement, si on se donne α1 , . . . , αn+1 des entiers positifs tels que xi = p +···+p
1
n
− pαi pour
tout i ∈ {1, . . . , n + 1}, alors on voit que x1 + · · · + xi−1 + xi+1 + · · · + xn+1 = pα1 + · · · + pαn+1 −
pα1 − · · · − pαi−1 − pαi+1 − · · · − pαn+1 = pαi .
La question revient donc à la suivant : existe-t-il des entiers positifs α1 , . . . , αn+1 tels que n divise
α1 αn+1
pα1 +· · ·+pαn+1 pour la première question, et pour la seconde question tels que p +···+p n
−pαi > 0,
i.e. pα1 + · · · + pαn+1 > npαi pour tout i.
Essayons de répondre d’abord à la première partie de la question : à quelle condition sur n existe-t-il
α1 , . . . , αn+1 tels que n divise pα1 + · · · + pαn+1 ? Déjà, modulo p − 1, on a pα1 + · · · + pαn+1 ≡ n + 1
(mod p − 1). Notons d le pgcd de p − 1 et n, alors si n divise pα1 + · · · + pαn+1 , comme d divise p − 1,
d divise aussi n + 1. Comme d divise n, on obtient que d divise n + 1 − n = 1, donc d = 1. Ainsi il
faut que n et p − 1 sont premiers entre eux.
Réciproquement si n et p−1 sont premiers entre eux, soit x ∈ {1, . . . , n+1} on prend α1 = · · · = αx = 0
et αx+1 = · · · = αn+1 = 1. On cherche donc un certain x tel que x tel que n divise x + (n + 1 − x)p,
i.e. x tel que x + p − xp ≡ 0 (mod n), soit x ≡ p(p − 1)−1 (mod n) (qui existe car p − 1 et n sont
premiers entre eux). On peut prendre un tel x dans {1, . . . , n} tel que la précédente congruence est vraie.
Ainsi la condition pour la première question est exactement n et p − 1 sont premiers entre eux.
Pour la seconde question, on cherche de plus à avoir pα1 + · · · + pαn+1 > npαi pour tout i. Quitte à
réordonner les αi , on peut supposer α1 ⩽ α2 ⩽ · · · ⩽ αn+1 , la condition est équivalente à pα1 + · · · +
pαn+1 > npαn+1 . Si α2 < αn+1 , on a :

pα1 + · · · + pαn+1 ⩽ 2pα2 + (n − 1)pαn+1 ⩽ pα2 +1 + (n − 1)pαn+1 ⩽ npαn+1 .

Ainsi on a α2 ⩾ αn+1 , donc α2 = · · · = αn+1 . Dans ce cas, il est clair que pα1 + · · · + pαn+1 > npαn+1
est vérifié. Il reste donc à chercher à quelle condition sur n existe-t-il α1 ⩽ α2 deux entiers positifs tels
que n divise pα1 + npα2 donc à quelle condition n divise pα1 . Il est alors clair que les solutions sont les
puissances de p. Ainsi la condition pour la seconde question est que n soit une puissance de p.

Commentaire des correcteurs : Chacune des parties de cet exercice a été globalement réussie par les
élèves qui l’ont abordée. Néanmoins, plusieurs élèves, après avoir réussi l’une des deux parties, ont cru
que l’autre n’en était qu’un simple corollaire, ce qui n’était pas vrai ; ils l’ont donc mal traitée, aboutissant
à des résultats incorrects. C’est dommage !

19
Exercice 17. Soient a, b deux entiers tels que pgcd(a, b) a au moins deux facteurs premiers distincts.
Soit S = {x ∈ N|x ≡ a[b]}. Un élément de S est dit irréductible s’il ne peut pas s’écrire comme un
produit d’au moins deux éléments de S (pas forcément distincts).
Montrer qu’il existe N > 0 tel que tout élément de S s’écrit comme produit d’au plus N éléments
irréductibles de S (pas forcément distincts).
Solution de l’exercice 17 Soit d = pgcd(a, b), et écrivons a = da ′ , b = db ′ . Commençons par traiter
le cas où pgcd(d, b ′ ) > 1. Si c’est le cas, alors on a pgcd(a2 , b) = dpgcd(da ′2 , b ′ ) > d. Donc, pour
tout k ⩾ 2, on a ak ̸≡ a[b]. En particulier, tout élément de S est irréductible, et donc N = 1 convient.
Supposons à présent que d et b ′ sont premiers entre eux. On a alors a et b ′ premiers entre eux ; soit ω
l’ordre de a modulo b ′ . On a alors que aω+1 ≡ a[b]. Donc tout produit de ω + 1 éléments de S est
encore un élément de S. Ceci signifie en particulier que tout élément non irréductible de S peut s’écrire
comme un produit de k éléments de S pour un certain k ∈ J2, ωK.
Soient p et q deux diviseurs premiers de d, et soit x ∈ S. Si x est irréductible, c’est bon ; sinon, écrivons
x = u1 u2 . . . uk avec u1 , . . . , uk ∈ S, pour un k ∈ J2, ωK. Montrons d’abord qu’on peut supposer
vp (uj ) < φ(b ′ ) + vp (d) pour tout j < k. Pour cela, on remarque que, si vp (uj ) ⩾ φ(b ′ ) + vp (d), alors
u ′ ′ ′
on peut remplacer uj par pφ(bj ′ ) et uk par pφ(b ) uk . On a pφ(b ) ≡ 1[b ′ ], donc pφ(b ) uk ≡ uk ≡ a[b ′ ].
′
D’autre part, d | uk donc pφ(b ) uk ≡ 0 ≡ a[d]. Donc, d’après le théorème des restes chinois, on
′ u
a pφ(b ) uk ≡ a[b]. D’autre part, on a aussi pφ(bj ′ ) ≡ a[b ′ ], et on a également (puisque vp (uj ) ⩾
u u
φ(b ′ ) + vp (d)) que d | pφ(bj ′ ) . Donc pφ(bj ′ ) ≡ a[b].
On a à présent vp (uj ) < φ(b ′ ) + vp (d) pour j < k. De même, on peut supposer que vq (uk ) <
φ(b ′ )+vq (d). Toute écriture de uj (j < k) sous forme de produit d’irréductibles fait apparaı̂tre seulement
des multiples de d, donc de p, et comprend donc au plus vp (uj ) facteurs. De même pour q avec uk .
Finalement, on a réussi à écrire x sous la forme d’un produit d’au plus (ω − 1)(φ(b ′ ) + vp (d) − 1) +
φ(b ′ ) + vq (d) − 1 facteurs irréductibles, comme souhaité.

Commentaire des correcteurs : L’exercice est réussi par une poignée d’élèves. Il semble que la notion
d’irréductibilité a posé des problèmes de compréhension, montrer que tout nombre de S peut s’écrire
comme un nombre fini d’éléments irréductibles ne répondait pas à l’énoncé. Enfin, il est regrettable que
pour certains, les copies rendues pour ce problème d’envoi soient pratiquement illisibles.

20
Exercice 18. Pour tout entier k ⩾ 1, on note p(k) le plus petit nombre premier ne divisant pas k. Soit
(an )n∈N une suite telle que a0 ∈ N∗ et pour tout n ⩾ 0, an+1 est le plus petit entier strictement positif
an+1
différent de a0 , . . . , an tel que an − 1 est divisible par p(an ). Démontrer que tout entier strictement
positif apparaı̂t une unique fois dans la suite (an )n∈N .
Solution de l’exercice 18 Déjà notons que la suite est bien définie : si a1 , . . . , an sont construits, comme
an est premier avec p(an ), il existe une infinité d’entiers k tels que akn ≡ 1 (mod p(an )) qui sont
tous les multiples de l’ordre de an modulo p(an ). En particulier, il existe au moins un de ces entiers
n’apparaissant pas parmi a1 , . . . , an , donc an+1 existe bien.
Notons que chaque entier apparaı̂t au plus une fois dans la suite par construction. Il faut donc montrer
que tous apparaissent au moins une fois. Supposons qu’il existe un entier N qui n’apparaı̂t pas dans la
suite (xn ), on prend alors N minimal. On note N0 un entier tel que si n ⩾ N0 , an > N.
Montrons que pour tout premier q, il existe un nombre fini de n tels que p(an ) = q. Supposons que ce
n’est pas le cas, et fixons q un nombre premier tel que p(an ) = q pour une infinité de n. On se donne
alors ϕ : N → N strictement croissante telle que p(aϕ(n) ) = q. Notons alors que tout multiple de q − 1
apparaı̂t : en effet si on fixe M un multiple de q − 1, alors comme les p(aϕ(n)+1 ) sont deux à deux
distincts, il existe n tel que aϕ(n)+1 > M. Or comme q − 1 divise M, aM ϕ(n) ≡ 1 (mod q − 1) par petit
Fermat, ce qui contredit la définition de aϕ(n)+1 .
Ainsi tous les multiples de q − 1 apparaissent. on note p1 < · · · < pk les nombres premiers strictement
inférieurs à q. On sait que pour tout j ⩾ 1, (p1 . . . pk )j(q−1) est congru à 1 modulo q, divisible par q − 1
pour j assez grand (car tous les
j(q−1)

facteurs de q − 1 sont parmi p1 , . . . , pk ) donc apparaı̂t dans la suite,
et vérifie p (p1 . . . pk ) = q. Comme il y a une infinité de tels termes, il existe N1 > N0 tel
j(q−1)
que aN1 = (p1 . . . pk ) pour j assez grand. Ainsi aN N1 ≡ 1 (mod q), ce qui contredit le fait que
aN1 +1 > N.
Ainsi on a bien prouvé que pour tout premier q, il existe un nombre fini de n tels que p(an ) = q. En
particulier, pour tout M ∈ N, comme la suite (p(an )) prend un nombre fini de fois chaque valeurs entre
1 et M, à partir d’un certain rang p(an ) > M, donc (p(an )) tend vers +∞. En particulier, pour tout k,
à partir d’un certain rang, p1 . . . , pk divise an .
Soit k et m tels que p1 . . . pk divise am , pk+1 ne divise pas am , et p1 . . . pk+1 divise an pour tout n ⩾
p ...p p p ...p p
m + 1. On a alors p(am ) = pk+1 , et an1 k k+1 ≡ 1 (mod pk+1 ). Or par Petit Fermat, an1 k k+1 ≡
ap1 ...pk (mod pk+1 ), donc pour tout i vérifiant 1 ⩽ i ⩽ pk − 1, aip1 ...pk ≡ 1 (mod pk+1 ). Ainsi
pour tout i vérifiant 1 ⩽ i ⩽ pk − 1, ip1 . . . pk apparaı̂t dans la suite (an ). En prenant i un inverse
de p1 . . . pk modulo pk+1 − 1 dans {1, . . . , pk+1 − 1}, on a alors que (ip1 . . . pk )N ≡ N (mod pk+1 ),
donc si an = ip1 . . . pk , alors an+1 < N, donc n ⩽ N0 . Ainsi si de tels k, m existent, alors pk divise
a1 . . . an+1 , donc k est borné.
Or pour tout K ∈ N, on peut trouver k ⩾ K et m tels que p1 . . . pk divise am , pk+1 ne divise pas am , et
p1 . . . pk+1 divise an pour tout n ⩾ m + 1. En effet, notons pour tout k ⩾ 1 rk le premier rang à partir
duquel p1 . . . pk divise an . La suite (rj ) est croissante, et ne peut être stationnaire sinon un an serait
divisible par tous les nombres premiers. Donc elle tend vers +∞, pour tout K, il existe k ⩾ K tel que
rk+1 > rk . Ainsi ark+1 −1 est divisible par p1 . . . pk car rk+1 − 1 ⩾ rk , et pas par pk+1 . Mais tous les
termes après rk+1 sont divisibles par p1 . . . pk+1 , donc m = rk+1 − 1 convient. On a donc bien obtenu
que pour tout K ∈ N, on peut trouver k ⩾ K et m tels que p1 . . . pk divise am , pk+1 ne divise pas am , et
p1 . . . pk+1 divise an pour tout n ⩾ m + 1, donc on a abouti à une contradiction.
Ainsi chaque entier apparaı̂t une unique fois dans la suite.

Commentaire des correcteurs : L’exercice est réussi par une poignée d’élèves. Certains ont utilisé des
résultats moins élémentaires que le corrigé par exemple le postulat de Bertrand.

21