CPGE: Lycée Mohamed V Casablanca Année scolaire: 2024-2025

Filière: MPSI Professeur: Y.Hdach

TD 11: Arithmétique
Exercice 1

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

Exercice 2

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

Exercice 3

Montrer que: 11 | 2123 + 3121

Exercice 4

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

Exercice 5

Soient x et y deux entiers relatifs. Montrer que :

7 | x et 7|y ⇐⇒ 7|x2 + y 2

Exercice 6
(
x ∧ y = 15
(1) Déterminer tous les couples d’entiers relatifs tels que :
xy = 100

x ∨ y = 18
(2) Déterminer tous les couples (x, y) d’entiers naturels tels que :
x + y = 15

Exercice 7

N ≡ 5 [13]
On se propose de déterminer tous les entiers relatifs N tels que :
N ≡ 1 [17]

1. Vérifier 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érifiant 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 8

On considère la suite (un ) définie pour tout entier naturel n non nul par :

un = 2n + 3n + 6n − 1.

1. Calculer les six premiers termes de la suite.

2. Montrer que, pour tout entier naturel n non nul, un est pair.

1
 3. Montrer que, pour tout entier naturel n pair non nul, un est divisible par 4.
On note (E) l’ensemble des nombres premiers qui divisent au moins un terme de la suite ( un ).

4. Les entiers 2, 3, 5 et 7 appartiennent-ils à l’ensemble (E) ?

5. Soit p un nombre premier strictement supérieur à 3 .

(a) Montrer que : 6 × 2p−2 ≡ 3 ( modulo p) et 6 × 3p−2 ≡ 2 ( modulo p).
(b) En déduire que 6up−2 ≡ 0 (modulo p).
(c) Le nombre p appartient-il à l’ensemble (E) ?

Exercice 9

1. On considère l’équation (E) : 11x − 7y = 5, où x et y sont des entiers relatifs.

(a) Justifier, en énonçant un théorème, qu’il existe un couple d’entiers relatifs (u;v) tels que 11u −
7v = 1. Trouver un tel couple.
(b) En déduire une solution particulière de l’équation (E).
(c) Résoudre l’équation (E).
(d) Dans le plan rapporté à un repère orthonormé (O; →
−, , ~), on considère la droite D d’équation
cartésienne 11x − 7y − 5 = 0.
On note C l’ensemble des points M(x; y) du plan tels que 0 6 x 6 50 et 0 6 y 6 50.
Déterminer le nombre de points de la droite D appartenant à l’ensemble C et dont les coordonnées
sont des nombres entiers.

2. On considère l’équation (F) : 11x2 − 7y 2 = 5, où x et y sont des entiers relatifs.

(a) Démontrer que si le couple (x; y) est solution de (F), alors x2 ≡ 2y 2 (mod5).
(b) Soient x et y des entiers relatifs. Recopier et compléter les deux tableaux suivants :
Modulo 5, x est congru à 0 1 2 3 4 Modulo 5, y est congru à 0 1 2 3 4
Modulo 5, x2 est congru à Modulo 5, 2y 2 est congru à
Quelles sont les valeurs possibles du reste de la division euclidienne de x2 et de 2y 2 par 5 ?
(c) En déduire que si le couple (x; y) est solution de (F), alors x et y sont des multiples de 5 .

3. Démontrer que si x et y sont des multiples de 5 , alors le couple (x; y) n’est pas solution de (F ).
Que peut-on en déduire pour l’équation (F) ?

Exercice 10

On considère la suite (un ) d’entiers naturels définie par :

u0 = 1et, pour tout entier naturel n, un+1 = 10un + 21

1. Calculer u1 , u2 et u3 .

2. (a) Démontrer par récurrence que, pour tout entier naturel n,

3un = 10n+1 − 7

(b) En déduire, pour tout entier naturel n, 1 ’écriture décimale de un .

3. Montrer que u2 est un nombre premier.

On se propose maintenant d’étudier la divisibilité des termes de la suite (un ) par certains nombres
premiers.

4. Démontrer que, pour tout entier naturel n, un n’est divisible ni par 2 , ni par 3, ni par 5 .

5. (a) Démontrer que, pour tout entier naturel n, 3un ≡ 4 − (−1)n (modulol 11).
(b) En déduire que, pour tout entier naturel n, un n’est pas divisible par 11 .

2
 6. (a) Démontrer l’égalité : 1016 ≡ 1 (modulo17).
(b) En déduire que, pour tout entier naturel k, u16k+8 est divisible par 17 .

Exercice 11

Dans cet exercice, on s’intéresse aux triplets d’entiers naturels non nuls (x, y, z) tels que

x2 + y 2 = z 2
Ces triplets seront nommés triplets pythagoriciens en référence aux triangles rectangles dont ils
mesurent les côtés, et notés en abrégé TP. Ainsi (3, 4, 5) est un TP car 32 + 42 = 9 + 16 = 25 = 52 .
Partie A

1. Démontrer que, si (x, y, z) est un TP, et p un entier naturel non nul, alors le triplet ( px, py, pz )
est lui aussi un TP.
2. Démontrer que, si (x, y, z) est un TP, alors les entiers naturels x, y et z ne peuvent pas être tous les
trois impairs.
3. Pour cette question, on admet que tout entier naturel non nul n peut s’écrire d’une façon unique
sous la forme du produit d’une puissance de 2 par un entier impair : n = 2α × k où α est un entier
naturel (éventuellement nul) et k un entier naturel impair.
L’écriture n = 2α × k est nommée décomposition de n.
Voici par exemple les décompositions des entiers 9 et 120 : 9 = 20 × 9, 120 = 23 × 15.
(a) Donner la décomposition de l’entier 192.
(b) Soient x et z deux entiers naturels non nuls, dont les décompositions sont x = 2α × k et
z = 2β × m.
Écrire la décomposition des entiers naturels 2x2 et z 2 .
(c) En examinant l’exposant de 2 dans la décomposition de 2x2 et dans celle de z 2 , montrer qu’il
n’existe pas de couple d’entiers naturels non nuls (x, z) tels que 2x2 = z 2 .
On admet que la question A-3. permet d’établir que les trois entiers naturels x, y et z sont deux
à deux distincts. Comme de plus les entiers naturels x, y jouent un rôle symétrique, dans la suite,
pour tout TP (x, y, z), les trois entiers naturels x, y et z seront rangés dans l’ordre suivant :

x<y<z

Partie B : z = 2015
1. Décomposer en produit de facteurs premiers l’entier 2015 puis, en utilisant le TP donné dans le
préambule, déterminer un TP de la forme (x, y, 2015).

2
2
2. On admet que, pour tout entier naturel n, (2n + 1)2 + 2n2 + 2n = 2n2 + 2n + 1 .
Déterminer un TP de la forme (2015, y, z ).
3. (a) En remarquant que 4032 = 169 × 961, déterminer un couple d’entiers naturels non nuls (x, z)
tels que : z 2 − x2 = 4032 , avec x < 403.
(b) En déduire un TP de la forme (x, 2015, z).

Exercice 12

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.

3
 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 diffé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 13
Notations : pour tout entier n > 2, on note φ(n) le nombre d’entiers naturels inférieurs à n qui sont
premiers avec n. On définit 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 justifiant brièvement vos réponses, donner les valeurs de φ(5), φ(9) et φ(12).†
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) Établir 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 .
Exercice 14

1. Congruences et exponentiation rapide

(a) Déterminer le PGCD et les coefficients de Bezout des entiers 27 et 112 .
(b) On pose a = 12. Calculer a2 , puis a4 , puis a8 et enfin a16 modulo 145.
(c) Déduire de ce qui précède la valeur de 1227 modulo 145 .

2. Questions de cours
(a) Rappeler la définition d’entiers premiers entre eux. Rappeler la définition 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 justifiant 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 affirme 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 ). Justifier 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érification”. Dans cette question, on prend p = 5, q = 29, m = 12 et e = 27. Donner sans
justification la valeur de d.
Déterminer la valeur de me modulo N ,
puis détailler le calcul de (me )d modulo N .