TD 15

Divisibilité, diviseurs, congruences

Exercice 1
Soit a et b tels que 7 divise a2 + b2 . Montrer que 7 divise a et 7 divise b. Comment généraliser ?

Exercice 2
P10 k
Quel est le reste de la division euclidienne de k=1 1010 par 7?

Exercice 3
Démontrer que pour tout n ∈ N :
n n
1. 42 + 22 + 1 ≡ 0[7]
2. 22n + 15n − 1 ≡ 0[9].
3. Soient a ∈ Z impair et n ≥ 3. Montrer que a2
n−2
≡ 1 (mod2n ).

Exercice 4
Pour n ∈ N∗ on note σ(n) la somme des diviseurs positifs de n. Par exemple :

σ(12) = 1 + 2 + 3 + 4 + 6 + 12 = 28.
Montrer que si n + 1 est un multiple de 24 , alors σ(n) est un multiple de 24 .

Exercice 5
Soit A la somme des chiffres de 44444444 et B la somme des chiffres de A Trouver la somme des
chiffres de B ; la numération est la numération décimale.

Exercice 6
1. Montrer qu’un nombre est divisible par 3 si et seulement si la somme de ses chiffres est
divisible par 3 .
2. Montrer qu’un nombre est divisible par 9 si et seulement si la somme de ses chiffres est
divisible par 9.
3. (a) Montrer qu’un nombre est divisible P par 11 si et seulement si ses chiffres cn , . . . , c0 ( c0
étant le chiffre des unités) vérifient ni=0 (−1)i ci ≡ 0 [11].
(b) 978381778401775 est-il divisible par 11 ?
4. (a) Trouver de même un critère de divisibilité par 7.
(b) Le nombre 231442433142493650563 est-il divisible par 7 ?
5. Justifier que pour tout nombre N > 1 premier avec 10 , on peut trouver une suite (an )n∈N , k
périodique (k ∈ N∗ ), telle qu’un nombre dont les chiffres sont cn , cn−1 , . . . , c0 est divisible par
N si et seulement si
n
X
ak ck ≡ 0[N ]
k=0

1
Exercice 7
Soit n > 1 un entier. Montrer que n est impair si, et seulement si, n | 1n + 2n + · · · + (n − 1)n .

Exercice 8
Soit k ≥ 1 un entier impair. Montrer que pour tout n ∈ N∗ : (n + 2) ∤ 1k + 2k + · · · + nk .

Exercice 9
Trouver tous les n ∈ N tels que :
n
7 | 22 + 2n + 1.

Exercice 10
Soient m et n des entiers strictement positifs avec m > 2. Montrer que 2m − 1 ∤ 2n + 1.

Exercice 11
On note d : N∗ −→ N∗ l’application qui, à chaque n ∈ N∗ , associe le nombre de diviseurs ≥ 1 de n.
Montrer que, pour tout a ∈ N\{0, 1}, et pour tout n ∈ N∗ , on a : d (an − 1) ≥ d(n).

Exercice 12
Déterminer tous les entiers n ∈ N∗ qui ont exactement 16 diviseurs strictement positifs d1 , d2 , · · · , d16
tels que :

1 = d1 < d2 < · · · < d16 = n, d6 = 18 et d9 − d8 = 17

Exercice 13 (Formule d’inversion de Möbius)

On définit la fonction de Möbius par

(
0 si n est divisible par un carré non égal à 1
∀n ∈ N∗ , µ(n) = k
(−1) si n = p1 . . . pk où les pi sont premiers 2 à 2 distincts.

1. Montrer que pour tout (m, n) ∈ (N∗ )2 , si m ∧ n = 1, alors µ(mn) = µ(m)µ(n). 2. Montrer que
pour tout n ∈ N∗ , d|n µ(d) = δ1,n , où δi,j est le symbole de Kronecker, égal à 1 si i = j et 0 sinon.
P
3. Montrer que réciproquement, si ν est une fonction vérifiant l’identité de la question précédente,
alors ν = µ. 4. Soit f et g deux fonctions telles que pour tout n ∈ N∗ ,
X
g(n) = f (d).
d|n

Montrer (formule d’inversion de Möbius) :

n n
∀n ∈ N∗ ,
X X
f (n) = g(d)µ = µ(d)g .
d d
d|n d|n

5. Soit φ l’indicatrice d’Euler, montrer que pour tout n ∈ N∗

φ(n) X µ(d)
=
n d
d|n
X
(Ind : Montrer que n = φ(d))
d|n

2
PGCD, PPCM, entiers premiers entre eux, Bézout
Exercice 14

Étudier l’inversibilité modulo n de k, et le cas échéant, trouver les inverses modulo n des entiers k.
1. k = 1685, n = 1759
2. k = 1770, n = 1827
3. k = 1882, n = 1971

Exercice 15
Trouver les solutions entières de l’équation en (x, y) : 1955x + 1981y = 2.

Exercice 16
Soit (a, b, c) ∈ (N∗ )3 , tel que a > 1.


1. Montrer que ab − 1 ∧ (ac − 1) = ab∧c − 1.



2. En déduire que si b ∧ c = 1, alors ab − 1 (ac − 1) divise (a − 1) abc − 1 .

Exercice 17
Résoudre a ∧ b = 42 et a ∨ b = 1680.

Exercice 18
Déterminer les triplets (a, b, c) ∈ (N∗ )3 tels que

(i) ppcm(a, b) = 42 (ii) pgcd(a, c) = 3 (iii) a + b + c = 29.

Exercice 19
Résoudre x2 + y 2 = z 2 , avec (x, y, z) ∈ (N∗ )3 .

Exercice 20
Déterminer les entiers n ∈ N∗ tels que 7 divise nn − 3.

Exercice 21 (Nombres parfaits)

1. a) Pour tout entier naturel non nul n, on note σ(n) la somme des diviseurs de n.
Exprimer σ(n) en fonction des termes intervenant dans la décomposition de n en facteurs
premiers. Montrer que

n∧m=1 =⇒ σ(nm) = σ(n)σ(m)

b) On dit qu’un entier naturel non nul n est parfait s’il est égal à la somme de ses diviseurs
autres que lui même (i.e. si σ(n) = 2n ). Si 2p − 1 est un nombre premier, montrer que
n = 2p−1 (2p − 1) est un nombre parfait.
c) Réciproquement, démontrer qu’un nombre parfait pair n est de la forme 2p−1 (2p − 1), où
2p − 1 est nécessairement un nombre premier.
2. Nombres parfaits impairs.
a) (Théorème d’Euler). Montrer que s’il existe un nombre parfait impair n, alors il est
nécessairement de la forme n = p1+4α Q2 avec p premier, p ≡ 1 (mod4), α ∈ N, et
Q ∈QN∗ avec p ∧ Q = 1. (Indication : à partir de la décomposition en facteurs premiers
n = pαi i , étudier la valeur de σ (pαi i ) modulo 4.)
b) Montrer qu’un nombre parfait impair a au moins 3 facteurs premiers distincts.

3
Nombres premiers, théorème de Fermat, valuation p-adique
Exercice 22
Q2n
Déterminer la valuation 2-adique de k=n+1 k.

Exercice 23
(2m)!(2n)!
Montrer que pour tout (m, n) ∈ N2 , est un entier.
m!n!(m + n)!

Exercice 24

1. (a) Soit a et d deux entiers, d étant premier impair. À l’aide du petit théorème de Fermat,
montrer que si d divise a2 + 1, alors d ≡ 1[4].
(b) En déduire qu’il existe une infinité de nombres premiers p tels que p ≡ 1[4].
2. Montrer qu’il y a une infinité de nombres premiers de la forme 6k − 1, k ∈ N∗ .

Exercice 25
Montrer que pour tout n ∈ N, n7 ≡ n[42].

Exercice 26
1. Soit n un nombre impair. Montrer que n2 ≡ 1[8] et n4 ≡ 1[16].
2. Généraliser.
3. Soit p un nombre premier strictement supérieur à 17 . Montrer que p16 − 1 ≡ 0 [16320].

Exercice 27
Soit Pn l’ensemble des nombres premiers inférieurs ou égaux à n et an le cardinal de Pn .
1. Soit p ∈ P2n \Pn . Montrer que p divise 2n


n
.
2. Montrer que na2n −an ⩽ 22n .
3. Montrer qu’il existe C > 0 tel que
n
∀n ⩾ 2 an ⩽ C
ln n