Lycée Jean Bart  MPSI  12 février 2023

Exercices 17  Arithmétique
Divisibilité - Congruences

Exercice .  1 Montrer que l'équation 25x − 60y = 13 n'admet pas de couple d'entiers solution.

Exercice .  2 Prouver que l'équation 12x + 15y 2 + 36xy = 3002 n'admet pas de couple d'entiers relatifs solution.

Exercice .  3 Dans cet exercice, on cherche à résoudre l'équation diophantienne :

(E) 3x2 + 2y 2 = 30
(c'est-à-dire que l'on cherche les couples (x, y) d'entiers relatifs solutions de l'équation
(E)).
1) Démontrer que si (x, y) est un couple d'entiers relatifs solution de (E), alors (x, −y)
est un autre couple solution.

Dans la suite de l'exercice, on admettra que si (x, y) est solution de (E), alors les
couples (−x, y) et (−x, −y) sont également solutions.

2) Soient x et y deux entiers naturels tels que 3x2 + 2y 2 = 30.

a) Démontrer que 0 6 x 6 3.
b) En examinant les diérents cas, déterminer tous les couples (x, y) d'entiers
naturels solutions de (E).

3) Conclure en donnant la liste des couples d'entiers relatifs solutions de (E).

Exercice 4 . Déterminer tous les entiers naturels n tels que (n − 1) divise (n + 8).

Exercice 5 . Déterminer tous les entiers naturels n tels que (n − 4) divise (3n + 24).

Exercice 6 . Montrer que le produit de deux entiers naturels consécutifs est pair.

Exercice 7 . Montrer que la somme de trois entiers naturels consécutifs est un multiple de 3.

Exercice 8 . Montrer que le produit de trois entiers naturels consécutifs est un multiple de 3.

Exercice 9 . Montrer que la somme de cinq entiers naturels consécutifs est un multiple de 5.

Exercice 10 . Montrer que :

(
11 2123 + 3 121
)

Exercice 11 . Montrer que le produit de 62 entiers naturels consécutifs est multiple de 59.

Exercice 12 . La propriété : pour tout entier naturel n, 56n+1 + 22n est divisible par 5 est-elle vraie ?

Exercice 13 . Montrer que pour tout entier naturel n, 56n+1 + 23n+1 est divisible par 7.

Exercice 14 . Montrer que 1 + 230 + 330 + 430 est multiple de 5.

Exercice 15 . Montrer que 11001 + 21001 + 31001 + 41001 + 51001 est divisible par 5.

Exercice 16 . Montrer que pour tout entier relatif n le nombre An = n(n + 3)(n + 6)(n + 13) est divisible par 4.

Exercice 17 . Montrer que l'équation (E) : 5x2 + 2y 4 = 135789 n'admet aucun couple d'entiers relatifs solution.

Exercice
que P s'écrit :
18 . On considère un polynôme
P (x) = an xn + · · · + a1 x + a0 avec
P de degré n > 1 à coecients entiers relatifs. Explicitement, on suppose
a0 , a1 , . . . , an des entiers relatifs, et an ̸= 0 et a0 =
̸ 0.

1) Montrer que toute racine entière de P divise a0 .

2) En déduire que le polynôme x3 + 2x2 + 6x − 4 n'a pas de racine entière.

Exercice .  19 Soient x et y deux entiers relatifs. Montrer que : 7 |x et 7 |y ⇐⇒ 7 x2 + y 2

2 MPSI  Arithmétique  12 février 2023

Exercice .  20 Critère de divisibilité par 3

Pour n un entier naturel, on peut noter : ap · · · a1 a0 son écriture décimale, les ai désignant des entiers compris entre 0 et
9. Cette écriture signie que : n = ap × 10p + · · · + a1 × 10 + a0 .
∑
p
Etablir que n est multiple de 3 si et seulement si ai est multiple de 3.

Exercice . 
i=0

21 Critère de divisibilité par 11

∑
p
Mêmes notations que précédemment. Etablir que n est multiple de 11 si et seulement si (−1)i ai est multiple de 11.

Exercice . 
i=0

22 Système chinois
1) Déterminer tous les entiers x congrus à 2 modulo 10. 2) Déterminer tous les entiers x congrus à 5 modulo 13.
{
x ≡ 2 [10]
3) Résoudre dans Z le système :
x ≡ 5 [13]

Division euclidienne

Exercice 23 . Déterminer tous les entiers naturels qui, divisés par 6, donnent un quotient égal au reste.

Exercice 24 . Déterminer le quotient et le reste dans la division euclidienne de a = 31000 + 28 par 9.

Exercice 25 . Déterminer le quotient et le reste dans la division euclidienne de A = 52019 + 51 par 25.

Exercice
130 et 10.
26 . On divise un entier naturel
Quel est cet entier naturel n?
n par 243 et 248. Les quotients sont égaux, et les restes respectifs sont

Exercice
et que
27 .
2019 = 3 × 673).
Déterminer le reste dans la division euclidienne de 12342019 par 7 (on pourra noter que 1234 ≡ 2 [7],

PGCD, PPCM, relation de Bezout

Exercice .  28 Déterminer le PGCD et les coecients de Bezout des entiers a et b suivants :

1) a = 33 et b = 24 2) a = 37 et b = 27 3) a = 270 et b = 105

Exercice 29 . Soit n ∈ N. Montrer que le PGCD de 2n + 4 et 3n + 3 ne peut être que 1, 2, 3 ou 6.

Exercice .
{
x∧y = 15
30 Déterminer tous les couples d'entiers relatifs tels que :
xy = 900

Exercice .
{
x∧y = 8
31 Déterminer tous les couples d'entiers naturels tels que :
x2 − y 2 = 5440

Exercice .
{
x ∨ y = 18
32 Déterminer tous les couples (x, y) d'entiers naturels tels que :
x + y = 15

Exercice .
{
x∧y = 5
33 Déterminer tous les couples d'entiers relatifs tels que :
x∨y = 60

Exercice .
{
x∧y = 10
34 Déterminer tous les couples d'entiers relatifs tels que :
x+y = 100

Exercice 35 . Quel est le plus petit entier naturel congru à 5 modulo 27 et modulo 42 ?

Exercice 36 . Déterminer l'ensemble des couples d'entiers relatifs (x, y) solutions de (E) : 7x − 6y = 1.

Exercice 37 . Déterminer l'ensemble des couples d'entiers relatifs (x, y) solutions de (E) : 16x − 3y = 4.

Exercice 38 . Déterminer l'ensemble des couples (x ; y) ∈ Z2 solutions de (E) : 3x + 7y = 10n (où n ∈ N).

Exercice 39 . Déterminer l'ensemble des couples d'entiers relatifs (x, y) solutions de (E) : 18x + 7y = 12.
 MPSI  Arithmétique  12 février 2023 3

Exercice . 
{
N ≡ 5 [13]
40 On se propose de déterminer tous les entiers relatifs N tels que :
N ≡ 1 [17]
1) Vérier que 239 est solution de ce système.

2) Soit N un entier relatif solution de ce système. Démontrer que N peut s'écrire sous la forme N = 1 + 17x = 5 + 13y
où x et y sont deux entiers relatifs vériant la relation 17x − 13y = 4.
3) Résoudre l'équation 17x − 13y = 4 où x et y sont des entiers relatifs.

4) En déduire qu'il existe un entier relatif k tel que N = 18 + 221k .

{
N ≡ 5 [13]
5) Démontrer l'équivalence entre N ≡ 18 [221] et .
N ≡ 1 [17]

Exercice .  41 On considère la suite (un )n∈ N dénie par : u0 = 0, u1 = 1 et ∀ n ∈ N, un+2 = un+1 + un .

0) Révision : quelle est l'expression du terme général un en fonction de n?
∗ n
1) Montrer que : ∀ n ∈ N , un+1 un−1 − u2n = (−1) .

∗
2) En déduire que : ∀ n ∈ N , un+1 ∧ un = 1.

Exercice .  42 Soient a et b deux entiers premiers entre eux. Montrer que a et a+b sont premiers entre eux.

Exercice .  43 Soit n ∈ N∗ . Montrer que n2 + n et 2n + 1 sont premiers entre eux.

Nombres premiers

Exercice .  44 Montrer que l'entier naturel N = 22022 − 49 n'est pas premier.

Exercice .  45 1) Pour vérier que

et ainsi de suite jusqu'à un certain nombre premier
977 est premier, on peut essayer de le diviser par les nombres premiers
p1 . Précisément, quelle est la valeur de p1 ?
2, 3, 5

2) Déterminer tous les couples d'entiers naturels (x, y) tels que : x2 − y 2 = 977.

Exercice 46 . Soit p un nombre premier, p > 5. Montrer que p2 − 1 est divisible par 24.

Exercice 47 . Construire une liste de 2019 entiers consécutifs non premiers.

Exercice 48 . Existe t-il deux entiers relatifs non-nuls a et b tels que : a ln (3) + b ln (7) = 0 ?

Exercice 49 . Justier que : ∀ n ∈ Z, 19 n19 − n .

Exercice
(indication :
50 . (Un nombre de Carmichael, 1879-1967). Justier que :
1729 = 7 × 13 × 19).
∀ n ∈ Z, n1729 ≡ n [1729]

Exercice
est premier. Montrer que
51 . (Sur les nombres de Mersenne, 1588-1648). On suppose que
n est premier.
n est un entier > 2 tel que 2n − 1

Exercice 52
nombres premiers de la forme
. (Progression arithmétique de Dirichlet, 1805-1859) Montrer qu'il existe une innité de
4n + 3.

Exercice 53 . (Théorème de Wilson, 1741-1793) *

Soit p un entier > 2. Etablir que : p est premier SSI (p − 1)! ≡ −1 [p].

Exercice .  54 Indicatrice d'Euler (1707-1783).

Notations : pour tout entier n > 2, on note ϕ(n) le nombre d'entiers naturels inférieurs à n qui sont premiers avec n.
On dénit ainsi une application ϕ : N\ {0, 1} −→ N∗ , appelée fonction indicatrice d'Euler.
Par exemple : ϕ(2) = 1, ϕ(3) = 2, ϕ(4) = 2. On notera P l'ensemble des nombres premiers.

1) En justiant brièvement vos réponses, donner les valeurs de ϕ (5), ϕ (9) et ϕ (12). „

*. Selon la loi d'éponymie de Stigler : une découverte scientique ne porte jamais le nom de son auteur (cette loi, énoncée par le
statisticien Stephen Stigler en 1980, ne serait pas de Stigler lui-même !...). Cette loi s'applique en particulier au théorème de Wilson. Celui-ci
fut énoncé initialement par un mathématicien Arabe nommé Alhazen (965-1039). Il fut connu à partir du XVIIe siècle en Europe, mentionné
dans les travaux de Leibniz (1646-1716). Un peu plus tard, Wilson redécouvre ce qu'il croit être une conjecture et en partage la découverte
avec son professeur Edward Waring, qui publie cette conjecture en 1770. Lagrange (1736-1813) en présente deux premières démonstrations
en 1771, puis Euler une troisième en 1773. Utilisant les notations de l'arithmétique modulaire, Gauss (1777-1855) reformule la démonstration
d'Euler et en donne une quatrième.
„. On pourra vérier (après calculs et justications) que ϕ(12) = ϕ(3) × ϕ(4), et que ϕ(9) ̸= ϕ(3) × ϕ(3).
4 MPSI  Arithmétique  12 février 2023

2) Soit n un entier supérieur ou égal à 2, et soit a ∈ Z. Redémontrer que :

[a est inversible modulo n] ⇐⇒ [a ∧ n = 1]

3) Soit p ∈ P.
a) Etablir que ϕ(p) = p − 1.
∗
b) Soit α∈ N . Soit n un entier naturel. Montrer que : [n ∧ p = 1] ⇐⇒ [n ∧ pα = 1].
c) En déduire que pour tout α ∈ N∗ , ϕ (pα ) = pα − pα−1 .
A la lumière de la question 3-a, la conclusion de cette question peut être réécrite : ∀ n ∈ Z\pZ, nϕ(p) ≡ 1 [p]. Cette
assertion peut être généralisée à un entier N non nécessairement premier ; il s'agit de l'énoncé ci-dessous.
[ ]
Théorème d'Euler : ∀ N ∈ N\ {0, 1} , ∀ n ∈ Z, [n ∧ N = 1] =⇒ nϕ(N ) ≡ 1 [N ]

Exercice .  55 Les bases du codage RSA, extrait du DS9 de 2018

1) Congruences et exponentiation rapide

a) Déterminer le PGCD et les coecients de Bezout des entiers 27 et 112.

b) On pose a = 12. Calculer a2 , puis a4 , puis a8 et enn a16 modulo 145.

27
c) Déduire de ce qui précède la valeur de 12 modulo 145.
2) Questions de cours

a) Rappeler la dénition d'entiers premiers entre eux. Rappeler la dénition de nombre premier.

b) Soient a et b deux entiers. A quelle condition sur a et b l'entier a est-il inversible modulo b ? Donner, en justiant
brièvement votre réponse, un inverse de 27 modulo 112, ainsi qu'un inverse de 112 modulo 27.
c) Etablir que si p et q sont deux nombres premiers distincts, alors ils sont premiers entre eux.

d) Soit p un nombre premier. Le petit théorème de Fermat arme que : ∀ a ∈ Z, ap ≡ a [p].

Redémontrer alors que : ∀ a ∈ Z\pZ, ap−1 ≡ 1 [p].
3) Une nouvelle conséquence du théorème de Fermat. Soient p et q deux nombres premiers distincts, et soit
N = pq .
a) Montrer que a est premier avec N si et seulement si a est premier avec p et avec q.
b) On suppose que a est premier avec N. Montrer que a (p−1)(q−1)
≡ 1 [p] et a(p−1)(q−1)
≡ 1 [q].
c) Déduire de la question précédente que a(p−1)(q−1) ≡ 1 [N ].

4) On pose φ (N ) = (p − 1) (q − 1). Soit e un entier naturel premier avec φ (N ). Justier qu'il existe un entier d tel que
ed ≡ 1 [φ (N )].
5) Soit m un entier naturel.

a) Montrer que si m est premier avec N, alors med ≡ m [N ]. Ÿ

b) Montrer que pour tout entier m, on a med ≡ m [N ].
c) Vérication . Dans cette question, on prend p = 5, q = 29, m = 12 ete = 27. Donner sans justication la valeur
d
de d. Déterminer la valeur de me modulo N, puis détailler le calcul de (me ) modulo N .

. Pour l'anecdote, voici le même énoncé dans sa version originale :

Ce théorème est extrait d'un article publié (par Euler, vous aviez suivi !) en 1763 dans une revue scientique russe appelée Novi Commentarii
academiae scientiarum Petropolitanae (traduit en français : Nouveaux Mémoires de l'Académie Impériale des Sciences de St-Petersbourg).
Qu'un mathématicien suisse ait publié en latin dans un journal russe ne doit pas vous surprendre ; en premier lieu, le latin fut la langue
prédominante (pour ne pas dire exclusive) des travaux scientiques entre le XVème et le XVIIIème siècles. En second lieu, la deuxième moitié
du XVIIIème siècle correspond au règne de la tsarine Catherine II, qui a énormément contribué au développement des arts, lettres et sciences
en Russie. Elle a notamment incité Euler à s'installer à Saint-Petersbourg (où il repose désormais), et a entretenu des relations privilégiées
avec Diderot et Voltaire pour ne citer qu'eux.
Ÿ. Où e et d sont ceux dénis dans la question 4, et N = pq avec p et q premiers distincts.