Exercice 1 4396

Soit $n \in ℕ$ . Établir les divisibilités suivantes:

(a)

$6 ∣ 5 n^{3} + n$
(b)

$5 ∣ 2^{2 n + 1} + 3^{2 n + 1}$
(c)

$9 ∣ 4^{n} - 1 + 6 n$ .

Exercice 2 2358 CENTRALE (MP)Correction

Pour $n \in ℕ^{*}$ , on désigne par $N$ le nombre de diviseurs positifs de $n$ et par $P$ leur produit. Quelle relation existe-t-il entre $n$ , $N$ et $P$ ?

Solution

En associant dans $P^{2} = P \times P$ chaque diviseur $d$ avec celui qui lui est conjugué $n / d$ , on obtient un produit de $N$ termes égaux à $n$ . Ainsi,

P^{2} = n^{N} .

Exercice 3 4404

Déterminer les $x \in ℤ$ tels que

(a)

$(x - 2) ∣ (x + 2)$
(b)

$(x - 1) ∣ (x^{2} + x + 1)$ .

Exercice 4 1187 Correction

Résoudre dans $ℤ$ les équations suivantes:

(a)

$x - 1 ∣ x + 3$
(b)

$x + 2 ∣ x^{2} + 2$ .

Solution

(a)

$x = 1$ n’est pas solution. Pour $x \neq 1$ ,

$x - 1 ∣ x + 3$ $\Leftrightarrow \frac{x + 3}{x - 1} = 1 + \frac{4}{x - 1} \in ℤ$

$\Leftrightarrow x - 1 \in 𝒟 (4) = {1,2,4, - 1, - 2, - 4}$

Ainsi,

$𝒮 = {2,3,5,0, - 1, - 3} .$
(b)

$x = - 2$ n’est pas solution. Pour $x \neq - 2$ ,

$x + 2 ∣ x^{2} + 2$ $\Leftrightarrow \frac{x^{2} + 2}{x + 2} = x - 2 + \frac{6}{x + 2} \in ℤ$

$\Leftrightarrow x + 2 \in 𝒟 (6) = {1,2,3,6, - 1, - 2, - 3, - 6} .$

Ainsi,

$𝒮 = {- 1,0,1,4, - 3, - 4, - 5, - 8} .$

Exercice 5 4397

(Équations diophantiennes)

Déterminer les couples $(x, y) \in ℤ^{2}$ vérifiant

(a)

$x y = 3 x + y + 2$
(b)

$x^{2} - 6 x - y^{2} - 2 y = 4$ .

Exercice 6 1188 Correction

Résoudre dans $ℤ^{2}$ les équations suivantes:

(a)

$x y = 3 x + 2 y$
(b)

$\frac{1}{x} + \frac{1}{y} = \frac{1}{5}$
(c)

$x^{2} - y^{2} - 4 x - 2 y = 5$

Solution

(a)

On a

$x y = 3 x + 2 y \Leftrightarrow (x - 2) (y - 3) = 6 .$

En détaillant les diviseurs de 6 possibles, on obtient

$𝒮 = {(3,9), (4,6), (5,5), (8,4), (1, - 3), (0,0), (- 1,1), (- 4,2)} .$
(b)

Pour $x, y \in ℤ^{*}$ ,

$\frac{1}{x} + \frac{1}{y} = \frac{1}{5} \Leftrightarrow 5 x + 5 y = x y \Leftrightarrow (x - 5) (y - 5) = 25 .$

En détaillant les diviseurs de 25 possibles, on obtient

$𝒮 = {(6,30), (10,10), (30,6), (4, - 20), (- 20,4)} .$
(c)

On a

$x^{2} - y^{2} - 4 x - 2 y = 5 \Leftrightarrow {(x - 2)}^{2} - {(y + 1)}^{2} = 8$

et donc

$x^{2} - y^{2} - 4 x - 2 y = 5 \Leftrightarrow (x - y - 3) (x + y - 1) = 8 .$

En détaillant les diviseurs de 8 possibles et sachant

${\begin{matrix} x - y - 3 & = a \\ x + y - 1 & = b \end{matrix} \Leftrightarrow {\begin{matrix} x & = \frac{a + b}{2} + 2 \\ y & = \frac{b - a}{2} - 1 \end{matrix}$

on obtient

$𝒮 = {(5,0), (5, - 2), (- 1,0), (- 1, - 2)} .$

Exercice 7 155

Soit $A$ un ensemble de $n + 1 \geq 2$ entiers distincts tous inférieurs ou égaux à $2 n$ .
Montrer qu’il existe deux éléments de $A$ tels que l’un divise l’autre.

[<] Divisibilité[>] Calculs en congruence

Exercice 8 1189 Correction

Soient $a \in ℤ$ et $b \in ℕ^{*}$ , on note $q$ le quotient de la division euclidienne de $a - 1$ par $b$ .
Déterminer pour tout $n \in ℕ$ , le quotient de la division euclidienne de $(a b^{n} - 1)$ par $b^{n + 1}$ .

Solution

$a - 1 = b q + r$ avec $0 \leq r < b$ .
$a b^{n} - 1 = (b q + r + 1) b^{n} - 1 = q b^{n + 1} + b^{n} (r + 1) - 1$ .
Or $0 \leq b^{n} (r + 1) - 1 < b^{n + 1}$ donc la relation ci-dessus est la division euclidienne de $a b^{n} - 1$ par $b^{n + 1}$ .
Le quotient de celle-ci est donc $q$ .

Exercice 9 4430

(Développement factoriel d’un entier)

(a)

Montrer que pour tout $n \in ℕ^{*}$ , il existe $p \in ℕ^{*}$ et $(a_{1}, a_{2}, \dots, a_{p}) \in ℕ^{p}$ tels que

$n = \sum_{k = 1}^{p} a_{k} \cdot k! avec 0 \leq a_{k} \leq k et a_{p} \neq 0 .$
(b)

Vérifier l’unicité de cette écriture.

[<] Division euclidienne[>] PGCD et PPCM

Exercice 10 1190 Correction

Montrer que $11 ∣ 2^{123} + 3^{121}$ .

Solution

$2^{5} = - 1 [11]$ donc $2^{10} = 1 [11]$ puis $2^{123} = 2^{120} \times 2^{3} = {(2^{10})}^{12} \times 8 = 1 \times 8 = 8 [11]$ .
$3^{5} = 1 [11]$ donc $3^{121} = 3^{120} \times 3 = {(3^{5})}^{24} \times 3 = 1 \times 3 = 3 [11]$ .
Ainsi $2^{123} + 3^{121} = 8 + 3 = 0 [11]$ et donc $11 ∣ 2^{123} + 3^{121}$ .

Exercice 11 1191 Correction

Quel est le reste de la division euclidienne de $1234^{4321} + 4321^{1234}$ par 7?

Solution

$1234 = 2 [7]$ et $2^{3} = 1 [7]$ donc $1234^{4321} = 2^{4321} = 2^{4320} \times 2 = 1 \times 2 = 2 [7]$ .
$4321 = 2 [7]$ donc $4321^{1234} = 2^{1234} = 2^{1233} \times 2 = 1 \times 2 = 2 [7]$ .
Par suite, $1234^{4321} + 4321^{1234} = 2 + 2 = 4 [7]$ . Le reste cherché est 4.

Exercice 12 1193 Correction

Trouver les entiers $n \in ℤ$ tel que $10 ∣ n^{2} + {(n + 1)}^{2} + {(n + 3)}^{2}$ .

Solution

On a

\begin{matrix} n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ n^{2} + {(n + 1)}^{2} + {(n + 3)}^{2} & 0 & 1 & 8 & 1 & 0 & 5 & 6 & 3 & 6 & 5 \end{matrix}

donc $10 ∣ n^{2} + {(n + 1)}^{2} + {(n + 3)}^{2} \Leftrightarrow n = 0$ ou $4 [10]$ .

Exercice 13 1192 Correction

Montrer que pour tout $n \in ℕ$ :

(a)

$6 ∣ 5 n^{3} + n$
(b)

$7 ∣ 3^{2 n + 1} + 2^{n + 2}$
(c)

$5 ∣ 2^{2 n + 1} + 3^{2 n + 1}$
(d)

$11 ∣ 3^{8 n} \times 5^{4} + 5^{6 n} \times 7^{3}$
(e)

$9 ∣ 4^{n} - 1 - 3 n$
(f)

$15^{2} ∣ 16^{n} - 1 - 15 n$

Solution

(a)

Pour $n = 0,1,2,3,4,5$ on a $n^{3} = n [6]$ donc $5 n^{3} + n = 6 n = 0 [6]$ .
(b)

$3^{2 n + 1} + 2^{n + 2} = 3 . {(3^{2})}^{n} + {4.2}^{n} = {3.2}^{n} + {4.2}^{n} = {7.2}^{n} = 0 [7]$ .
(c)

$2^{2 n + 1} + 3^{2 n + 1} = 2 . {(2^{2})}^{n} + 3 . {(3^{2})}^{n} = {2.4}^{n} + {3.4}^{n} = {5.4}^{n} = 0 [5]$ .
(d)

$3^{8 n} \times 5^{4} + 5^{6 n} \times 7^{3} = 5^{n} \times 9 + 5^{n} \times 2 = 11 \times 5^{n} = 0 [11]$ .
(e)

$4^{n} - 1 - 3 n = (4 - 1) (1 + 4 + \dots + 4^{n - 1}) - 3 n = 3 (1 + 4 + \dots + 4^{n - 1} - n)$
or $1 + 4 + \dots + 4^{n - 1} - n = 1 + \dots + 1 - n = n - n = 0 [3]$ donc $9 ∣ 4^{n} - 1 - 3 n$ .
(f)

$16^{n} - 1 - 15 n = (16 - 1) (1 + 16 + \dots + 16^{n - 1}) - 15 n = 15 (1 + 16 + \dots + 16^{n - 1} - n)$
or $1 + 16 + \dots + 16^{n - 1} - n = 1 + \dots + 1 - n = n - n = 0 [15]$ donc $15^{2} ∣ 16^{n} - 1 - 15 n$ .

Exercice 14 3679 Correction

Montrer que si $n$ est entier impair alors

n^{2} \equiv 1 [8] .

Solution

On peut écrire $n = 2 p + 1$ et alors

n^{2} = {(2 p + 1)}^{2} = 4 p (p + 1) + 1 .

Puisque l’un des facteurs de $p (p + 1)$ est pair, le produit $4 p (p + 1)$ est multiple de 8 et donc

4 p (p + 1) + 1 \equiv 1 [8] .

Exercice 15 1194

Soient $x$ et $y$ deux entiers. Montrer

7 ∣ x et 7 ∣ y \Leftrightarrow 7 ∣ x^{2} + y^{2} .

Exercice 16 3680 Correction

Soient $λ, a, b \in ℤ$ et $m \in ℕ^{*}$ . On suppose $λ$ et $m$ premiers entre eux. Montrer

a \equiv b [m] \Leftrightarrow λ a \equiv λ b [m] .

Solution

$(⟹)$ Si $a \equiv b [m]$ alors $m$ divise $b - a$ et divise a fortiori $λ b - λ a = λ (b - a)$ .
$(⟸)$ Si $λ a \equiv λ b [m]$ alors $m$ divise $λ (b - a)$ . Or $m$ et $λ$ sont supposés premiers entre eux donc, en vertu du théorème de Gauss, $m$ divise $b - a$ .

Exercice 17 2359 CENTRALE (MP)Correction

Soient $A$ la somme des chiffres de $4444^{4444}$ , $B$ celle de $A$ et enfin $C$ celle de $B$ .

Que vaut $C$ ?

Solution

Posons $x = 4444^{4444}$ , $4444 \equiv 7 [9]$ , $7^{3} \equiv 1 [9]$ donc $4444^{4444} \equiv 7 [9]$ .

Sachant $x < 10^{5 \times 4444}$ , on a $A \leq 9 \times 5 \times 4444 = 199980$ , $B \leq 9 \times 5 + 1 = 46$ puis $C \leq 4 + 9 = 13$ . Or $C \equiv B \equiv A \equiv x [9]$ donc $C = 7$ .

[<] Calculs en congruence[>] Nombres premiers entre eux

Exercice 18 4398

Calculer le pgcd $d$ des entiers $a = 33$ et $b = 24$ ainsi qu’un couple $(u, v)$ de coefficients entiers exprimant une relation de Bézout $d = a u + b v$ .

Exercice 19 1195 Correction

Déterminer le pgcd et les coefficients de l’égalité de Bézout (1730-1783) des entiers $a$ et $b$ suivants:

(a)

$a = 33 et b = 24$
(b)

$a = 37 et b = 27$
(c)

$a = 270 et b = 105$ .

Solution

(a)

$pgcd (a, b) = 3$ et $3 a - 4 b = 3$ .
(b)

$pgcd (a, b) = 1$ et $11 b - 8 a = 1$
(c)

$pgcd (a, b) = 15$ et $2 a - 5 b = 15$

Exercice 20 1196 Correction

Soient $a, b, d \in ℤ$ . Montrer l’équivalence:

(\exists u, v \in ℤ, a u + b v = d) \Leftrightarrow pgcd (a, b) ∣ d .

Solution

$(⟹)$ Supposons $d = a u + b v$ avec $u, v \in ℤ$ . $pgcd (a, b) ∣ a$ et $pgcd (a, b) ∣ b$ donc $pgcd (a, b) ∣ a u + b v = d$ .

$(⟸)$ Supposons $pgcd (a, b) ∣ d$ . On peut écrire $d = k pgcd (a, b)$ avec $k \in ℤ$ .
Par l’égalité de Bézout, il existe $u_{0}, v_{0} \in ℤ$ tels que

a u_{0} + b v_{0} = pgcd (a, b)

et on a alors

d = a u + b v

avec $u = k u_{0}$ et $v = k v_{0} \in ℤ$

Exercice 21 4405

(Coefficients de l’égalité de Bézout)

Soient $a$ et $b$ deux entiers non nuls de pgcd $d$ . Notre but est de déterminer tous les couples $(u, v) \in ℤ^{2}$ tels que $a u + b v = d$ .

(a)

Justifier l’existence d’un couple solution $(u_{0}, v_{0})$ .
(b)

Exprimer à partir de $(u_{0}, v_{0})$ tous les couples solutions.

Exercice 22 1197 Correction

Montrer que le pgcd de $2 n + 4$ et $3 n + 3$ ne peut être que $1,2,3$ ou 6.

Solution

$3 \times (2 n + 4) - 2 \times (3 n + 3) = 6$ donc $pgcd (2 n + 4,3 n + 3) ∣ 6$ .

Exercice 23 4399

Soient $a, b$ et $k$ des entiers. Établir

a \land b = (a + k b) \land b .

Exercice 24 1201 Correction

Résoudre dans $ℕ^{2}$ les systèmes:

(a)

${\begin{matrix} pgcd (x, y) & = 5 \\ ppcm (x, y) & = 60 \end{matrix}$
(b)

${\begin{matrix} x + y & = 100 \\ pgcd (x, y) & = 10 \end{matrix}$

Solution

(a)

Soit $(x, y)$ solution. $pgcd (x, y) = 5$ donc $x = 5 x^{'}$ et $y = 5 y^{'}$ avec $x^{'}, y^{'} \in ℕ$ premiers entre eux.
$ppcm (x, y) = 5 x^{'} y^{'} = 60$ donc $x^{'} y^{'} = 12$ d’où

$(x^{'}, y^{'}) \in {(1,12), (2,6), (3,4), (4,3), (6,2), (12,1)} .$

Les couples $(2,6)$ et $(6,2)$ sont à éliminer car 2 et 6 ne sont pas premiers entre eux.
Finalement,

$(x, y) \in {(5,60), (15,20), (20,15), (60,5)} .$

Inversement: ok.

Finalement,

$𝒮 = {(5,60), (15,20), (20,15), (60,5)} .$
(b)

Soit $(x, y)$ solution. $pgcd (x, y) = 10$ donc $x = 10 x^{'}$ et $y = 10 y^{'}$ avec $x^{'}, y^{'} \in ℕ$ premiers entre eux.
$x + y = 10 (x^{'} + y^{'}) = 100$ donc $x^{'} + y^{'} = 10$ .
Sachant $x^{'} \land y^{'} = 1$ , il reste $(x^{'}, y^{'}) \in {(1,9), (3,7), (7,3), (9,1)}$ puis $(x, y) \in {(10,90), (30,70), (70,30), (90,10)}$ .
Inversement: ok.

Finalement,

$𝒮 = {(10,90), (30,70), (70,30), (90,10)} .$

Exercice 25 1199 Correction

Soient $d, m \in ℕ$ . Donner une condition nécessaire et suffisante pour que le système

{\begin{matrix} pgcd (x, y) & = d \\ ppcm (x, y) & = m \end{matrix}

possède un couple $(x, y) \in ℕ^{2}$ solution.

Solution

Si le système possède une solution alors $d ∣ m$ est une condition nécessaire.
Inversement, si $d ∣ m$ alors $x = d$ et $y = m$ donne un couple $(x, y) \in ℕ^{2}$ solution.

Exercice 26 1200 Correction

Résoudre dans $ℕ^{2}$ l’équation:

pgcd (x, y) + ppcm (x, y) = x + y .

Solution

Soit $(x, y) \in ℕ^{2}$ un couple solution. Posons $δ = pgcd (x, y)$ .
On peut écrire

x = δ x^{'} et y = δ y^{'} avec x^{'} \land y^{'} = 1 .

L’équation devient:

1 + x^{'} y^{'} = x^{'} + y^{'} \Leftrightarrow (x^{'} - 1) (y^{'} - 1) = 0 \Leftrightarrow x^{'} = 1 ou y^{'} = 1 .

Ainsi $(x, y)$ est de la forme $(δ, δ k)$ ou $(δ k, δ)$ avec $k \in ℕ$ .
Inversement, ces couples sont solutions.

Exercice 27 1198

Soient $a$ et $b$ deux entiers naturels avec $b$ non nul.

(a)

Montrer que, si $r$ est le reste de la division euclidienne de $a$ par $b$ , alors $2^{r} - 1$ est le reste de la division euclidienne de $2^{a} - 1$ par $2^{b} - 1$ .
(b)

En déduire

$(2^{a} - 1) \land (2^{b} - 1) = 2^{a \land b} - 1 .$

Exercice 28 4409

(Suite de Fibonacci)

On considère la suite $(φ_{n})$ déterminée par

φ_{0} = 0, φ_{1} = 1 et \forall n \in ℕ, φ_{n + 2} = φ_{n + 1} + φ_{n} .

(a)

Vérifier que, pour tout $n \in ℕ$ , $φ_{n}$ et $φ_{n + 1}$ sont des entiers premiers entre eux.
(b)

Soit $k \in ℕ^{*}$ . Montrer

$φ_{k + n} = φ_{k} φ_{n + 1} + φ_{k - 1} φ_{n} pour tout n \in ℕ .$

Soient $a \in ℕ$ et $b \in ℕ^{*}$ .

(c)

Établir

$φ_{a + b} \land φ_{b} = φ_{a} \land φ_{b} puis φ_{a} \land φ_{b} = φ_{b} \land φ_{r}$

où $r$ est le reste de la division euclidienne de $a$ par $b$ .
(d)

Conclure

$φ_{a} \land φ_{b} = φ_{a \land b} .$

[<] PGCD et PPCM[>] Nombres premiers

Exercice 29 4400

Montrer que, pour tout $n \in ℤ$ , les entiers $n$ , $n + 1$ et $2 n + 1$ sont premiers entre eux deux à deux. Que dire des entiers $n^{2} + n$ et $2 n + 1$ ?

Exercice 30 1204 Correction

Montrer que pour tout $n \in ℕ^{*}$

(a)

$(n^{2} + n) \land (2 n + 1) = 1$
(b)

$(3 n^{2} + 2 n) \land (n + 1) = 1$

Solution

(a)

$n^{2} + n = n (n + 1)$ .
$1 \times (2 n + 1) - 2 \times n = 1$ donc $(2 n + 1) \land n = 1$ .
$2 \times (n + 1) - 1 \times (2 n + 1) = 1$ donc $(2 n + 1) \land (n + 1) = 1$
Par produit $(2 n + 1) \land (n^{2} + n) = 1$ .
(b)

$3 n^{2} + 2 n = n (3 n + 2)$ .
$1 \times (n + 1) - 1 \times n = 1$ donc $n \land (n + 1) = 1$ .
$3 \times (n + 1) - 1 \times (3 n + 2) = 1$ donc $(3 n + 2) \land (n + 1) = 1$ .
Par produit $(3 n^{2} + 2 n) \land (n + 1) = 1$ .

Exercice 31 1202 Correction

Soient $a$ et $b$ deux entiers. Montrer que $a + b$ et $a b$ sont premiers entre si, et seulement si, $a$ et $b$ le sont.

Solution

Raisonnons par double implication.

$(⟹)$ Supposons $a + b$ et $a b$ premiers entre eux et calculons le pgcd $d$ de $a$ et $b$ . L’entier $d$ divise $a$ et $b$ et donc divise aussi $a + b$ et $a b$ . On en déduit que $d$ vaut $1$ : les entiers $a$ et $b$ sont premiers entre eux.

$(⟸)$ Supposons $a$ et $b$ premiers entre eux.

Méthode: On vérifie que $a + b$ est premier avec $a$ et avec $b$ afin d’affirmer qu’il est alors premier avec $a b$ .

Introduisons $d$ le pgcd de $a$ et $a + b$ . L’entier $d$ divise $a$ et divise aussi $b$ car $b = (a + b) - a$ . On en déduit que $d$ vaut $1$ et donc $a$ et $a + b$ sont premiers entre eux. Il en est de même pour $b$ et $a + b$ et donc pour $a b$ et $a + b$ .

Exercice 32 1203 Correction

Soient $a, b \in ℤ$ .

(a)

On suppose $a \land b = 1$ . Montrer que $(a + b) \land a b = 1$ .
(b)

On revient au cas général. Calculer $pgcd (a + b, ppcm (a, b))$ .

Solution

(a)

$pgcd (a, a + b) = pgcd (a, b)$ et $pgcd (b, a + b) = pgcd (a, b) = 1$ .
Ainsi $(a + b) \land a = 1$ et $(a + b) \land b = 1$ donc $(a + b) \land a b = 1$ .
(b)

Posons $δ = pgcd (a, b)$ . On peut écrire $a = δ a^{'}$ et $b = δ b^{'}$ avec $a^{'} \land b^{'} = 1$ .
$pgcd (a + b, ppcm (a, b)) = δ pgcd (a^{'} + b^{'}, ppcm (a^{'}, b^{'})) = δ$

Exercice 33 1205 Correction

Montrer que pour tout entier $n \in ℕ^{*}$ , $n + 1$ et $2 n + 1$ sont premiers entre eux.
En déduire

n + 1 ∣ (\binom{2 n}{n}) .

Solution

$2 \times (n + 1) - 1 \times (2 n + 1) = 1$ donc $(n + 1) \land (2 n + 1) = 1$ .
On a

(\binom{2 n + 1}{n + 1}) = \frac{2 n + 1}{n + 1} (\binom{2 n}{n})

donc

(n + 1) (\binom{2 n + 1}{n + 1}) = (2 n + 1) (\binom{2 n}{n}) .

Puisque $(\binom{2 n + 1}{n + 1}) \in ℤ$ , on a

(n + 1) ∣ (2 n + 1) (\binom{2 n}{n})

or $(n + 1) \land (2 n + 1) = 1$ donc

(n + 1) ∣ (\binom{2 n}{n}) .

Exercice 34 4401

Soient $a$ , $b$ et $c$ trois entiers avec $a$ et $c$ premiers entre eux.

(a)

Montrer $a \land (b c) = a \land b$ .
(b)

Que dire de $a \lor (b c)$ ?

Exercice 35 1208 Correction

(a)

Pour $n \in ℕ$ , montrer qu’il existe un couple unique $(a_{n}, b_{n}) \in ℕ^{2}$ tel que

${(1 + \sqrt{2})}^{n} = a_{n} + b_{n} \sqrt{2} .$
(b)

Calculer $a_{n}^{2} - 2 b_{n}^{2}$ .
(c)

En déduire que $a_{n}$ et $b_{n}$ sont premiers entre eux.

Solution

(a)

Unicité: Si $(a_{n}, b_{n})$ et $(α_{n}, β_{n})$ sont solutions alors

$a_{n} + b_{n} \sqrt{2} = α_{n} + β_{n} \sqrt{2}$

donc

$(b_{n} - β_{n}) \sqrt{2} = (α_{n} - a_{n}) .$

Si $b_{n} \neq β_{n}$ alors

$\sqrt{2} = \frac{α_{n} - a}{b_{n} - β_{n}} \in ℚ$

ce qui est absurde.
On en déduit $b_{n} = β_{n}$ puis $a_{n} = α_{n}$ .

Existence: Par la formule du binôme de Newton,

${(1 + \sqrt{2})}^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) {\sqrt{2}}^{k} .$

En séparant les termes d’indices pairs de ceux d’indices impairs, on a

${(1 + \sqrt{2})}^{n} = a_{n} + b_{n} \sqrt{2}$

avec

$a_{n} = \sum_{p = 0}^{⌊ n / 2 ⌋} (\binom{n}{2 p}) 2^{p} et b_{n} = \sum_{p = 0}^{⌊ (n - 1) / 2 ⌋} (\binom{n}{2 p + 1}) 2^{p} .$
(b)

On a

$a_{n}^{2} - 2 b_{n}^{2} = (a_{n} + b_{n} \sqrt{2}) (a_{n} - b_{n} \sqrt{2}) .$

Or en reprenant les calculs qui précèdent

${(1 - \sqrt{2})}^{n} = a_{n} - b_{n} \sqrt{2}$

donc

$a_{n}^{2} - 2 b_{n}^{2} = {(1 + \sqrt{2})}^{n} {(1 - \sqrt{2})}^{n} = {(- 1)}^{n} .$
(c)

La relation qui précède permet d’écrire

$a_{n} u + b_{n} v = 1 avec u, v \in ℤ .$

On en déduit que $a_{n}$ et $b_{n}$ sont premiers entre eux.

Exercice 36 1209 Correction

Soient $a$ et $b$ deux entiers relatifs premiers entre eux et $d \in ℕ$ un diviseur de $a b$ .
Montrer

\exists! (d_{1}, d_{2}) \in ℕ^{2}, d = d_{1} d_{2}, d_{1} ∣ a et d_{2} ∣ b .

Solution

Unicité: Si $(d_{1}, d_{2})$ est solution alors $pgcd (d, a) = pgcd (d_{1} d_{2}, a)$
Or $d_{2} \land a = 1$ car $d_{2} ∣ b$ et $a \land b = 1$ , donc $pgcd (d_{1} d_{2}, a) = pgcd (d_{1}, a) = d_{1}$ car $d_{1} ∣ a$ .
De même, $d_{2} = pgcd (d, b)$ d’où l’unicité.
Existence: Posons $d_{1} = pgcd (d, a)$ et $d_{2} = pgcd (d, b)$ . On a $d_{1} ∣ a$ et $d_{2} ∣ b$ .
$d_{1} ∣ a$ et $d_{2} ∣ b$ donc $d_{1} \land d_{2} = 1$ car $a \land b = 1$ .
$d_{1} ∣ d$ , $d_{2} ∣ d$ et $d_{1} \land d_{2} = 1$ donc $d_{1} d_{2} ∣ d$ .
Inversement: Par l’égalité de Bézout on peut écrire $d_{1} = u_{1} d + v_{1} a$ et $d_{2} = u_{2} d + v_{2} b$ donc $d ∣ d_{1} d_{2} = U d + v_{1} v_{2} a b$ car $d ∣ a b$ .

Exercice 37 1210

On note $Div (n)$ l’ensemble des diviseurs positifs d’un entier $n \in ℤ$ .
Soient $a, b$ deux entiers premiers entre eux. Établir la bijectivité de l’application

φ : {\begin{matrix} Div (a) \times Div (b) & \to & Div (a b) \\ (k, ℓ) & \mapsto & k ℓ . \end{matrix}

Exercice 38 3624 Correction

Soit $n \in ℕ$ . Montrer que les entiers

a_{i} = i \cdot n! + 1

pour $i \in {1, \dots, n + 1}$ sont deux à deux premiers entre eux.

Solution

Par l’absurde, supposons que $a_{i}$ et $a_{j}$ (avec $i, j \in {1, \dots, n + 1}$ ) ne soient pas premiers entre eux.
Considérons $d$ un diviseur premier commun à $a_{i}$ et $a_{j}$ . L’entier $d$ est diviseur de $a_{i} - a_{j}$ donc de $(i - j) \cdot n!$ .
Puisque $d$ est premier et diviseur de $i - j$ ou de $n!$ , il est nécessairement inférieur à $n$ et donc assurément diviseur de $n!$ . Or $d$ divise aussi $a_{i} = i \cdot n! + 1$ et donc $d$ divise $1$ .
C’est absurde.

[<] Nombres premiers entre eux[>] Études arithmétiques

Exercice 39 2653 ENTPE

Soit $p$ un nombre premier supérieur à $5$ . Montrer que $p^{2} - 1$ est divisible par $24$ .

Exercice 40 3209 ENTPECorrection

Soient $n \geq 2$ et $N$ la somme de $n$ entiers impairs consécutifs. Montrer que $N$ n’est pas un nombre premier.

Solution

Notons $2 p + 1$ le premier nombre impair sommé. On a

N = \sum_{k = 0}^{n - 1} (2 k + 2 p + 1) = n (n + 2 p)

avec $n \geq 2$ et $n + 2 p \geq 2$ . Ainsi, $N$ est composé.

Exercice 41 1219 Correction

Montrer que les nombres suivants sont composés:

(a)

$4 n^{3} + 6 n^{2} + 4 n + 1$ avec $n \in ℕ^{*}$
(b)

$n^{4} - n^{2} + 16$ avec $n \in ℤ$ .

Solution

(a)

$4 n^{3} + 6 n^{2} + 4 n + 1 = {(n + 1)}^{4} - n^{4} = ({(n + 1)}^{2} - n^{2}) ({(n + 1)}^{2} + n^{2}) = (2 n + 1) (2 n^{2} + 2 n + 1)$ .
Cet entier est composé pour $n \in ℕ^{*}$ car $2 n + 1 \geq 2$ et $2 n^{2} + 2 n + 1 \geq 2$ .
(b)

$n^{4} - n^{2} + 16 = {(n^{2} + 4)}^{2} - 9 n^{2} = (n^{2} - 3 n + 4) (n^{2} + 3 n + 4)$ .
De plus, les équations $n^{2} - 3 n + 4 = 0,1 ou - 1 et n^{2} + 3 n + 4 = 0,1 ou - 1$ n’ont pas de solutions car toutes de discriminant négatif. Par conséquent, $n^{4} - n^{2} + 16$ est composée.

Exercice 42 4402

Soient $p$ un nombre premier et $a$ un entier. Montrer

p ∣ a ou p et a sont premiers entre eux.

Exercice 43 3623 Correction

Soit $n$ un naturel non nul. Montrer qu’il existe toujours un nombre premier strictement compris entre $n$ et $n! + 2$ .

Solution

Considérons l’entier $n! + 1$ . Celui-ci est divisible par un nombre premier $p$ inférieur à $n! + 1$ .
Si ce nombre premier $p$ est aussi inférieur à $n$ alors il divise $n!$ (car apparaît comme l’un des facteurs de ce produit) et donc il divise aussi $1 = (n! + 1) - n!$ . Ceci est absurde et donc le nombre premier en question est au moins égal à $n + 1$ . Finalement, il est strictement compris entre $n$ et $n! + 2$ .

Exercice 44 1224 Correction

Justifier l’existence de $1 000$ entiers consécutifs sans nombres premiers.

Solution

Considérons les $x_{k} = 1 001! + k$ avec $2 \leq k \leq 1001$ . Ce sont $1 000$ entiers consécutifs.
Pour tout $2 \leq k \leq 1001$ , on a $k ∣ (1001)!$ donc $k ∣ x_{k}$ avec $2 \leq k < x_{k}$ donc $x_{k} \notin 𝒫$ .

Exercice 45 2369 CENTRALE (MP)Correction

On suppose que $n$ est un entier $\geq 2$ tel que $2^{n} - 1$ est premier.
Montrer que $n$ est nombre premier.

Solution

Si $n = a b$ avec $a, b \in ℕ^{*}$ alors

2^{n} - 1 = (2^{a} - 1) (1 + 2^{a} + \dots + 2^{a (b - 1)})

donc $2^{a} - 1 ∣ 2^{n} - 1$ d’où $2^{a} - 1 = 1$ ou $2^{a} - 1 = 2^{n} - 1$ ce qui implique $a = 1$ ou $a = n$ .
Ainsi $n$ ne possède que des diviseurs triviaux, il est premier.

Exercice 46 1220

Soient $a$ et $p$ deux entiers supérieurs à $2$ . Montrer que, si $a^{p} - 1$ est un nombre premier, alors $a = 2$ et $p$ est premier.

Exercice 47 2656 MINES (MP)Correction

Soient des entiers $a > 1$ et $n > 0$ .
Montrer que si $a^{n} + 1$ est premier alors $n$ est une puissance de 2.

Solution

On peut écrire

n = 2^{k} (2 p + 1) .

On a alors

a^{n} + 1 = b^{2 p + 1} - {(- 1)}^{2 p + 1} = (b - (- 1)) \sum_{k = 0}^{2 p} b^{k} {(- 1)}^{2 p - k} = (b + 1) c

avec $b = a^{2^{k}}$ .
On en déduit que $b + 1 ∣ a^{n} + 1$ , or $a^{n} + 1$ est supposé premier et $b + 1 > 1$ donc $b + 1 = a^{n} + 1$ puis $n = 2^{k}$ .

Exercice 48 3351 X (PC)Correction

Soient $a, b \in ℕ ∖ {0,1}$ et $n \in ℕ^{*}$ .
On suppose que $a^{n} + b^{n}$ est un nombre premier. Montrer que $n$ est une puissance de 2.

Solution

On peut écrire $n = 2^{k} (2 p + 1)$ avec $k, p \in ℕ$ et l’enjeu est d’établir $p = 0$ .
Posons $α = a^{2^{k}}$ et $β = b^{2^{k}}$ . On a

a^{n} + b^{n} = α^{2 p + 1} + β^{2 p + 1} = α^{2 p + 1} - (- β^{2 p + 1}) .

On peut alors factoriser par $α - (- β) = α + β$ et puisque $a^{n} + b^{n}$ est un nombre premier, on en déduit que $α + β = 1$ ou $α + β = a^{n} + b^{n}$ . Puisque $α, β \geq 1$ , le cas $α + β = 1$ est à exclure et puisque $α \leq a^{n}$ et $β \leq b^{n}$ , le cas $α + β = a^{n} + b^{n}$ entraîne

α = a^{n} et β = b^{n} .

Puisque $a \geq 2$ , l’égalité $α = a^{n} = α^{2 p + 1}$ entraîne $p = 0$ et finalement $n$ est une puissance de 2.

Exercice 49 4403

(Morphisme de Frobenius)

Soit $p$ un nombre premier.

(a)

Pour tout $1 \leq k < p$ , montrer que le coefficient binomial $(\binom{p}{k})$ est un multiple de $p$ .
(b)

En déduire que, pour tous entiers $a$ et $b$ , ${(a + b)}^{p} \equiv a^{p} + b^{p} [p]$ .

Exercice 50 3682 Correction

Soit $n \in ℕ$ avec $n \geq 2$ .

(a)

On suppose que $n$ est premier. Montrer

$\forall k \in {2, \dots, n - 1}, n divise (\binom{n}{k}) .$
(b)

Inversement, on suppose que $n$ est composé. Montrer

$\exists k \in {2, \dots, n - 1}, n ne divise pas (\binom{n}{k}) .$

Solution

(a)

On suppose $n$ premier. On sait

$(\binom{n}{k}) = \frac{n}{k} (\binom{n - 1}{k - 1})$

donc

$k (\binom{n}{k}) = n (\binom{n - 1}{k - 1})$

ce qui permet d’affirmer que $n$ divise l’entier $k (\binom{n}{k})$ . Or $n$ est premier et donc premier avec $k$ puisque $k < n$ . Par le théorème de Gauss, on peut alors affirmer que $n$ divise $(\binom{n}{k})$ .
(b)

Supposons maintenant $n$ composé. On peut introduire $p$ un facteur premier de $n$ avec $p < n$ . Nous allons alors montrer que $n$ ne divise par $(\binom{n}{p})$ ce qui permet de conclure.
Par l’absurde, supposons que $m = \frac{1}{n} (\binom{n}{p})$ soit un entier. On peut écrire

$(n - 1)! = m \cdot p! (n - p)!$

Puisque $p$ divise $n$ , on peut aussi écrire $n = p q$ avec $q$ entier et donc

$(p q - 1)! = m \cdot p! (p (q - 1))!$

Dans les produits définissant $(p q - 1)!$ et $(p (q - 1))!$ , on retrouve les mêmes multiples de $p$ , à savoir $p,2 p, \dots (q - 1) p$ . On peut donc écrire

$(p q - 1)! = k a et (p (q - 1))! = k b$

avec $k$ regroupant le produit des multiples de $p$ précédents et $a$ et $b$ non divisibles par $p$ .

La relation initiale se simplifie alors pour donner

$a = m p! b$

ce qui entraîne que $a$ est divisible par $p$ . C’est absurde!

Exercice 51 2654 MINES (MP)

Montrer qu’il existe une infinité de nombres premiers de la forme $4 n - 1$ avec $n$ entier.

Exercice 52 2657 MINES (MP)

(Nombres de Fermat)

Pour $n \in ℕ$ , on introduit $F_{n} = 2^{2^{n}} + 1$ .

(a)

On suppose $n$ et $m$ sont deux entiers naturels distincts. Montrer $F_{n} \land F_{m} = 1$ .
(b)

Exploiter cette propriété afin de retrouver le théorème d’Euclide affirmant l’existence d’une infinité de nombres premiers.

[<] Nombres premiers[>] Valuation p-adique

Exercice 53 1211

Soient $a$ et $b$ deux entiers relatifs. Montrer

a ∣ b \Leftrightarrow a^{2} ∣ b^{2} .

Exercice 54 1225 Correction

Soit $n \in ℕ$ . Montrer

\sqrt{n} \in ℚ \Leftrightarrow \exists m \in ℕ, n = m^{2} .

En déduire que $\sqrt{2} \notin ℚ$ et $\sqrt{3} \notin ℚ$

Solution

$(⟸)$ C’est immédiat.

$(⟹)$ Si $\sqrt{n} \in ℚ$ alors on peut écrire $\sqrt{n} = \frac{p}{q} avec p \land q = 1$ .
On a alors $q^{2} n = p^{2}$ donc $n ∣ p^{2}$
De plus, $q^{2} n = p^{2}$ et $p^{2} \land q^{2} = 1$ donne $p^{2} ∣ n$ .
Par double divisibilité $n = p^{2}$ .
ni 2, ni 3 ne sont des carrés d’un entier, donc $\sqrt{2} \notin ℚ$ et $\sqrt{3} \notin ℚ$ .

Exercice 55 4406

Soient $m$ et $n$ deux entiers naturels non nuls premiers entre eux.

(a)

Soit $x$ un nombre rationnel. On suppose que $x^{n}$ est entier, montrer que $x$ est entier.
(b)

Soient $a$ et $b$ deux entiers non nuls tels que $a^{m} = b^{n}$ . Montrer qu’il existe $c \in ℕ^{*}$ tel que $a = c^{n}$ et $b = c^{m}$ .

Exercice 56 1214 Correction

On divise un cercle en $n$ arcs égaux et l’on joint les points de division de $p$ en $p$ jusqu’à ce que l’on revienne au point de départ. Quel est le nombre de côtés du polygone construit?

Solution

Le nombre de côté du polygone construit est le plus petit entier $k \in ℕ^{*}$ tel que $n ∣ k p$ .
Posons $δ = pgcd (n, p)$ . On peut écrire $n = δ n^{'}$ et $p = δ p^{'}$ avec $n^{'} \land p^{'} = 1$ .
$n ∣ k p \Leftrightarrow n^{'} ∣ k p^{'}$ c’est-à-dire $n^{'} ∣ k$ . Ainsi $k = n^{'} = n / δ$ .

Exercice 57 3669 Correction

On étudie l’équation algébrique

(E) : x^{n} + a_{n - 1} x^{n - 1} + \dots + a_{1} x + a_{0} = 0

d’inconnue $x$ et où les coefficients $a_{0}, a_{1}, \dots, a_{n - 1}$ sont supposés entiers.
Montrer que les solutions réelles de $(E)$ sont entières ou irrationnelles.

Solution

Supposons $x = p / q$ une racine rationnelle de l’équation $(E)$ avec $p$ et $q$ premiers entre eux.
En réduisant au même dénominateur, on obtient

p^{n} + a_{n - 1} q p^{n - 1} + \dots + a_{1} p q^{n - 1} + a_{0} q^{n} = 0 .

Puisque $q$ divise $a_{n - 1} q p^{n - 1} + \dots + a_{1} p q^{n - 1} + a_{0} q^{n}$ , on obtient que $q$ divise $p^{n}$ .
Or $p$ et $q$ sont premiers entre eux donc nécessairement $q = 1$ et donc $x = p \in ℤ$ .
Ainsi, les racines rationnelles de $(E)$ sont entières.

Exercice 58 1228 Correction

Soient $p \in 𝒫$ et $α \in ℕ^{*}$ . Déterminer les diviseurs positifs de $p^{α}$ .

Solution

Soit $d \in D i v (p^{α}) \cap ℕ$ . Notons $β$ la plus grande puissance de $p$ telle que $p^{β} ∣ d$ .
On peut écrire $d = p^{β} k$ avec $p ∣ k$ .
Puisque $p ∣ k$ et $p \in 𝒫$ on a $p \land k = 1$ . Or $k ∣ p^{α} \times 1$ donc, par Gauss: $k ∣ 1$ .
Par suite, $d = p^{β}$ avec $β \in ℕ$ . De plus, $d ∣ p^{α}$ donc $p^{β} \leq p^{α}$ puis $β \leq α$ .
Inversement: ok.

Exercice 59 1229 Correction

Soit $n \in ℕ ∖ {0,1}$ et $n = \prod_{k = 1}^{N} p_{k}^{α_{k}}$ sa décomposition primaire.
Quel est le nombre de diviseurs positifs de $n$ ?

Solution

Les diviseurs positifs sont les $d = \prod_{k = 1}^{N} p_{k}^{β_{k}}$ avec

\forall 1 \leq k \leq N, 0 \leq β_{k} \leq α_{k} .

Le choix des $β_{k}$ conduisant à des diviseurs distincts, il y a exactement $\prod_{k = 1}^{N} (α_{k} + 1)$ diviseurs positifs de $n$ .

Exercice 60 1227

Soit $n \in ℕ$ au moins égal à $2$ . Montrer que $n$ est le produit de ses diviseurs non triviaux¹¹ 1 Dans ce sujet, on se limite aux diviseurs positifs. Les diviseurs triviaux de $n$ sont $1$ et $n$ . si, et seulement si, $n = p^{3}$ avec $p$ nombre premier ou $n = p q$ avec $p$ et $q$ des nombres premiers distincts.

Exercice 61 1230 Correction

Soit $n \in ℕ ∖ {0,1}$ dont la décomposition primaire est

n = \prod_{i = 1}^{N} p_{i}^{α_{i}} .

On note $d (n)$ le nombre de diviseurs supérieurs ou égaux à 1 de $n$ et $σ (n)$ la somme de ceux-ci.
Montrer

d (n) = \prod_{i = 1}^{N} (α_{i} + 1) et σ (n) = \prod_{i = 1}^{N} \frac{p_{i}^{α_{i} + 1} - 1}{p_{i} - 1} .

Solution

Soit $d \in ℕ$ diviseur de $n$ .
Tout diviseur premier de $d$ est aussi diviseur de $n$ et c’est donc l’un des $p_{1}, \dots, p_{N}$ .
Par suite, on peut écrire $d = \prod_{i = 1}^{N} p_{i}^{β_{i}}$ avec $β_{i} \in ℕ$ .
$p_{i}^{β_{i}} ∣ d$ donc $p_{i}^{β_{i}} ∣ n$ d’où $β_{i} \leq α_{i}$ .
Ainsi $d$ est de la forme $d = \prod_{i = 1}^{N} p_{i}^{β_{i}}$ avec pour tout $i \in {1, \dots, N}$ , $0 \leq β_{i} \leq α_{i}$ .
Inversement, de tels nombres sont bien diviseurs de $n$ .
Il y a autant de nombres de cette forme distincts que de choix pour les $β_{1}, \dots, β_{N}$ .Pour $β_{i}$ , il y a $α_{i} + 1$ choix possibles, au total $d (n) = \prod_{i = 1}^{N} (α_{i} + 1)$ .
De plus,

	$σ (n)$	$= \sum_{β_{1} = 0}^{α_{1}} \sum_{β_{2} = 0}^{α_{2}} \dots \sum_{β_{N} = 0}^{α_{N}} p_{1}^{β_{1}} p_{2}^{β_{2}} \dots p_{N}^{β_{N}}$
		$= (\sum_{β_{1} = 0}^{α_{1}} p_{1}^{β_{1}}) (\sum_{β_{2} = 0}^{α_{2}} p_{2}^{β_{2}}) \dots (\sum_{β_{N} = 0}^{α_{N}} p_{N}^{β_{N}}) .$

Par sommation géométrique

σ (n) = \prod_{i = 1}^{N} \frac{p_{i}^{α_{i} + 1} - 1}{p_{i} - 1} .

Exercice 62 4410

Soit $n \in ℕ ∖ {0,1}$ dont la décomposition en facteurs premiers s’écrit

n = \prod_{k = 1}^{r} p_{k}^{α_{k}} avec p_{1}, \dots, p_{r} nombres premiers deux à deux distincts.

Montrer que la somme $σ (n)$ des diviseurs positifs de $n$ vaut

σ (n) = \prod_{k = 1}^{r} \frac{p_{k}^{α_{k} + 1} - 1}{p_{k} - 1} .

Exercice 63 4408

(Théorème RSA)

Soient $p$ et $q$ deux nombres premiers distincts, $n = p q$ et $e$ un entier naturel premier avec le produit $(p - 1) (q - 1)$ .

(a)

Justifier qu’il existe un entier $d \geq 0$ tel que $e d \equiv 1 [(p - 1) (q - 1)]$ .
(b)

Montrer que $x^{e d} \equiv x [n]$ pour tout entier $x$ .

Exercice 64 4407

(Triplets pythagoriciens)

On étudie l’équation $(E) : a^{2} + b^{2} = c^{2}$ d’inconnue $(a, b, c) \in ℤ^{3}$ .

Soit $(a, b, c)$ une solution non nulle. Si $d$ désigne le pgcd des trois entiers $a$ , $b$ et $c$ , on peut simplifier l’équation par $d^{2}$ et se ramener à la situation où $d = 1$ : nous supposons par la suite être dans cette situation.

(a)

Montrer que $a$ , $b$ et $c$ sont deux à deux premiers entre eux.
(b)

Quelles sont les congruences possibles d’un carré modulo $4$ ? En déduire que l’une des deux valeurs $a$ ou $b$ est paire et l’autre impaire.

On suppose que $b$ est pair.

(c)

Montrer qu’il existe $x$ et $y$ entiers tels que $c + a = 2 x^{2}$ et $c - a = 2 y^{2}$ .
(d)

Quels sont les triplets $(a, b, c) \in ℤ^{3}$ solutions de l’équation $a^{2} + b^{2} = c^{2}$ ?

Exercice 65 4411

(Formule d’inversion de Möbius)

Pour $n \in ℕ^{*}$ on pose

μ (n) = {\begin{matrix} 0 & si n est divisible par le carré d’un nombre premier \\ {(- 1)}^{r} & si n est le produit de r nombres premiers deux à deux distincts. \end{matrix}

En particulier, $μ (1) = 1$ . Enfin, pour $n \in ℕ^{*}$ , on pose¹¹ 1 La somme introduite porte sur les entiers $d$ diviseurs positifs de $n$ .

s (n) = \sum_{d ∣ n} μ (d) .

(a)

Soient $p$ un nombre premier et $α \in ℕ^{*}$ . Calculer $s (p^{α})$ .
(b)

Soient $m$ et $n \in ℕ^{*}$ premiers entre eux, vérifier $s (m n) = s (m) s (n)$ .
(c)

En déduire la valeur de $s (n)$ pour tout $n \in ℕ^{*}$ .

On considère une fonction $u : ℕ^{*} \to ℂ$ et la fonction $v : ℕ^{*} \to ℂ$ définie par

v (n) = \sum_{d ∣ n} u (d) .

(d)

Soit $n \in ℕ^{*}$ . Vérifier la formule d’inversion

$u (n) = \sum_{d ∣ n} μ (\frac{n}{d}) v (d) .$

Exercice 66 3681

On note $d (n)$ le nombre de diviseurs de $n \in ℕ^{*}$ . Montrer

\frac{1}{n} \sum_{k = 1}^{n} d (k) = \sum_{k = 1}^{n} \frac{1}{k} + b_{n}

avec $(b_{n})$ une suite bornée.

Exercice 67 3725

(Théorème d’Aubry)

Soit $N$ un entier strictement positif et $𝒞$ le cercle d’équation $x^{2} + y^{2} = N$ .

On suppose que le cercle $𝒞$ possède un point $(x_{0}, y_{0})$ à coordonnées rationnelles. On introduit $(x_{0}^{'}, y_{0}^{'})$ un point à coordonnées entières obtenues par arrondis des coordonnées de $(x_{0}, y_{0})$ . En étudiant, lorsque cela a un sens, l’intersection du cercle $𝒞$ avec la droite joignant $(x_{0}, y_{0})$ et $(x_{0}^{'}, y_{0}^{'})$ , montrer que ce cercle contient un point à coordonnées entières.

[<] Études arithmétiques[>] Petit théorème de Fermat

Exercice 68 1226 Correction

Pour $p \in 𝒫$ et $n \in ℤ$ , on note $v_{p} (n)$ l’exposant de la plus grande puissance de $p$ divisant $n$ .

(a)

Montrer que $v_{2} (1 000!) = 994$ .
(b)

Plus généralement, calculer $v_{p} (n!)$ . On rappelle que

$\forall x \in ℝ, ⌊ \frac{⌊ p x ⌋}{p} ⌋ = ⌊ x ⌋ .$

Solution

(a)

$v_{2} (1 000!) = 500 + v_{2} (500!)$ car $1000! = 2^{500} \times 500! \times k$ avec $k$ produit de nombres impairs.
$v_{2} (1 000!) = 500 + 250 + 125 + 62 + 31 + 15 + 7 + 3 + 1 = 994$ .
(b)

En isolant les multiples de $p$ dans le produit décrivant $p!$ , on obtient

$v_{p} (n!) = ⌊ \frac{n}{p} ⌋ + v_{p} (⌊ \frac{n}{p} ⌋!)$

puis

$v_{p} (n!) = ⌊ \frac{n}{p} ⌋ + ⌊ \frac{⌊ n / p ⌋}{p} ⌋ + v_{p} (⌊ \frac{⌊ n / p ⌋}{p} ⌋!)$

or

$⌊ \frac{⌊ p x ⌋}{p} ⌋ = ⌊ x ⌋$

avec $x = n / p^{2}$ donne

$⌊ \frac{⌊ n / p ⌋}{p} ⌋ = ⌊ \frac{n}{p^{2}} ⌋$

puis finalement

$v_{p} (n!) = ⌊ \frac{n}{p} ⌋ + ⌊ \frac{n}{p^{2}} ⌋ + \dots + ⌊ \frac{n}{p^{k}} ⌋$

avec

$k = ⌊ \frac{\ln (n)}{\ln (p)} ⌋ .$

Exercice 69 4412

(Formule de Legendre)

(a)

Soient $p$ un nombre premier et $n \in ℕ$ . Établir

$v_{p} (n!) = \sum_{i = 1}^{r} ⌊ \frac{n}{p^{i}} ⌋ avec r = ⌊ \frac{\ln (n)}{\ln (p)} ⌋ .$
(b)

Application: Soient $a, b \in ℕ$ , montrer

$\frac{(2 a)! (2 b)!}{a! b! (a + b)!} \in ℕ .$

Exercice 70 2370 CENTRALE (MP)Correction

On note $𝒫$ l’ensemble des nombres premiers. Pour tout entier $n > 0$ , on note $v_{p} (n)$ l’exposant de $p$ dans la décomposition de $n$ en facteurs premiers. On note $⌊ x ⌋$ la partie entière de $x$ . On note $π (x)$ le nombre de nombres premiers au plus égaux à $x$ .

(a)

Montrer

$v_{p} (n!) = \sum_{k = 1}^{+ \infty} ⌊ \frac{n}{p^{k}} ⌋ .$
(b)

Montrer que $(\binom{2 n}{n})$ divise $\prod_{p \in 𝒫; p \leq 2 n} p^{⌊ \frac{\ln (2 n)}{\ln (p)} ⌋}$ .
(c)

Montrer que $(\binom{2 n}{n}) \leq {(2 n)}^{π (2 n)}$ .
(d)

Montrer que $\frac{x}{\ln (x)} = O (π (x))$ quand $x \to + \infty$

Solution

(a)

Pour $k$ suffisamment grand $⌊ n / p^{k} ⌋ = 0$ , la somme évoquée existe donc car elle ne comporte qu’un nombre fini de termes non nuls. $n! = 1 \times 2 \times \dots \times n$ , parmi les entiers allant de 1 à $n$ , il y en a exactement $⌊ n / p ⌋$ divisibles par $p$ , $⌊ n / p^{2} ⌋$ divisibles par $p^{2}$ , etc…donc

$v_{p} (n!) = \sum_{k = 1}^{+ \infty} ⌊ \frac{n}{p^{k}} ⌋ .$
(b)

On a

$(\binom{2 n}{n}) = \frac{(2 n)!}{{(n!)}^{2}} .$

Pour tout $p \in 𝒫$ ,

$v_{p} (\frac{(2 n)!}{{(n!)}^{2}}) = \sum_{k = 1}^{\infty} (⌊ \frac{2 n}{p^{k}} ⌋ - 2 ⌊ \frac{n}{p^{k}} ⌋)$

or $⌊ 2 x ⌋ - 2 ⌊ x ⌋ = 0$ ou 1 donc

$\sum_{k = 1}^{\infty} (⌊ \frac{2 n}{p^{k}} ⌋ - 2 ⌊ \frac{n}{p^{k}} ⌋) \leq Card {k \in ℕ^{*} | ⌊ 2 n / p^{k} ⌋ > 0} \leq ⌊ \frac{\ln (2 n)}{\ln (p)} ⌋ .$

De plus, les nombres premiers diviseurs de $(\binom{2 n}{n}) = \frac{(2 n)!}{{(n!)}^{2}}$ sont diviseurs d’un entier inférieur à $2 n$ (lemme d’Euclide) et sont donc eux-mêmes inférieur à $2 n$ . Il en découle

$(\binom{2 n}{n}) ∣ \prod_{p \in 𝒫; p \leq 2 n} p^{⌊ \frac{\ln (2 n)}{\ln (p)} ⌋}$

car toutes les puissances de nombres premiers intervenant dans la décomposition de $(\binom{2 n}{n})$ divisent $\prod_{p \in 𝒫; p \leq 2 n} p^{⌊ \frac{\ln (2 n)}{\ln (p)} ⌋}$ .
Notons qu’en fait ce produit désigne

$ppcm (1,2, \dots,2 n) .$
(c)

On a

$(\binom{2 n}{n}) \leq \prod_{p \in 𝒫; p \leq 2 n} p^{⌊ \frac{\ln (2 n)}{\ln (p)} ⌋} \leq \prod_{p \in 𝒫; p \leq 2 n} p^{\frac{\ln (2 n)}{\ln (p)}} \leq \prod_{p \in 𝒫; p \leq 2 n} (2 n) = {(2 n)}^{π (2 n)} .$
(d)

En passant au logarithme:

$\sum_{k = 1}^{2 n} \ln (k) - 2 \sum_{k = 1}^{n} \ln (k) \leq π (2 n) \ln (2 n) .$

À l’aide d’une comparaison intégrale on obtient

$\int_{1}^{n} \ln (t) d t \leq \sum_{k = 1}^{n} \ln (k) \leq \int_{1}^{(n + 1)} \ln (t) d t$

donc

$n \ln (n) - n + 1 \leq \sum_{k = 1}^{n} \ln (k) \leq (n + 1) \ln (n + 1) - n$

donc

$\sum_{k = 1}^{n} \ln (k) \underset{n \to + \infty}{=} n \ln (n) - n + O (\ln (n)) .$

Par suite,

$\sum_{k = 1}^{2 n} \ln (k) - 2 \sum_{k = 1}^{n} \ln (k) \underset{n \to + \infty}{=} 2 n \ln (2 n) - 2 n - 2 (n \ln (n) - n) + O (\ln (n))$

puis

$\sum_{k = 1}^{2 n} \ln (k) - 2 \sum_{k = 1}^{n} \ln (k) \underset{n \to + \infty}{\sim} \ln (2) (2 n) .$

On en déduit

$\frac{2 n}{\ln (2 n)} \underset{n \to + \infty}{=} O (π (2 n)) .$

Ajoutons

$\frac{x}{\ln (x)} \underset{n \to + \infty}{\sim} \frac{2 ⌊ x / 2 ⌋}{\ln (2 ⌊ x / 2 ⌋)}$

par calculs et $π (x) \sim π (2 ⌊ x / 2 ⌋)$ car $π (x)$ et $π (2 ⌊ x / 2 ⌋)$ ne différent qu’au plus d’une unité et $π (x) \to + \infty$ .
Finalement, une certaine satisfaction.

[<] Valuation p-adique

Exercice 71 1222 Correction

Soit $p$ un nombre premier.

(a)

Montrer

$\forall k \in {1,2, \dots, p - 1}, p ∣ (\binom{p}{k}) .$
(b)

En déduire que

$\forall n \in ℤ, n^{p} \equiv n [p] .$

Solution

(a)

On a

$(\binom{p}{k}) = \frac{p}{k} (\binom{p - 1}{k - 1})$

donc

$k (\binom{p}{k}) = p (\binom{p - 1}{k - 1}) .$

Par suite, $p ∣ k (\binom{p}{k})$ .
Or $p$ est premier et $k < p$ donc $k \land p = 1$ puis $p ∣ (\binom{p}{k})$ en vertu du théorème de Gauss.
(b)

Par récurrence finie sur $n \in {0,1, \dots, p - 1}$
Pour $n = 0$ : ok
Supposons la propriété établie au rang $n \in {0,1, \dots, p - 2}$
Par la formule du binôme

${(n + 1)}^{p} = n^{p} + \sum_{k = 1}^{p - 1} (\binom{p}{k}) n^{k} + 1 \equiv n + 1 [p]$

car pour $1 \leq k \leq p - 1$ .

$(\binom{p}{k}) \equiv 0 [p] .$

Récurrence établie.
Pour tout $n \in ℤ$ , il existe $r \in {0,1, \dots, p - 1}$ tel que $n \equiv r [p]$ et

$n^{p} \equiv r^{p} \equiv r \equiv n [p] .$

Exercice 72 3636 Correction

Soit $n \geq 2$ un entier. On suppose

\forall a \in {1, \dots, n - 1}, a^{n - 1} \equiv 1 [n] .

Montrer que $n$ est un nombre premier

Solution

Pour tout $a \in {1, \dots, n - 1}$ , $a$ est premier avec $n$ . En effet, un diviseur commun à $a$ et $n$ est diviseur de $a^{n - 1} - 1$ et donc de 1.
On en déduit que $n$ est premier puisque premier avec chaque naturel strictement inférieur à lui-même.

Exercice 73 204 Correction

(Nombres de Carmichael)

Soit $n$ un entier supérieur à 2.
On suppose que $n$ pour tout facteur premier $p$ de $n$ , $p^{2}$ ne divise pas $n$ mais $p - 1$ divise $n - 1$ .
Établir

\forall a \in ℤ, a^{n} \equiv a [n] .

Solution

Par hypothèse, on peut écrire $n = p_{1} p_{2} \dots p_{r}$ avec $p_{1}, \dots, p_{r}$ nombres premiers deux à deux distincts.
Soit $a \in ℤ$ . Considérons $i \in {1, \dots, r}$ .
Si $p_{i}$ ne divise pas $a$ , le petit théorème de Fermat assure $a^{p_{i} - 1} \equiv 1 [p_{i}]$ .
Puisque $p_{i} - 1$ divise $n - 1$ , on a encore $a^{n - 1} \equiv 1 [p_{i}]$ et donc $a^{n} \equiv a [p_{i}]$
Si $p_{i}$ divise $a$ alors $p_{i}$ divise aussi $a^{n}$ et donc $a^{n} \equiv 0 \equiv a [p_{i}]$ .
Enfin, chaque $p_{i}$ divisant $a^{n} - a$ et les $p_{i}$ étant deux à deux premiers entre eux, $n = p_{1} \dots p_{r}$ divise $a^{n} - a$ et finalement $a^{n} \equiv a [n]$ .
La réciproque de ce résultat est vraie.
Ce résultat montre que le petit théorème de Fermat ne caractérise pas les nombres premiers. Les nombres non premiers satisfaisant le petit théorème de Fermat, sont les nombres de Carmichael. Le plus petit d’entre eux est 561, le suivant 1105.

Exercice 74 3686

On désire établir qu’il existe une infinité de nombres premiers de la forme $4 n + 1$ . Pour cela on raisonne par l’absurde et l’on suppose que ceux-ci sont en nombre fini. On pose $N$ le produit de ceux-ci et l’on introduit

M = {(2 N)}^{2} + 1 .

(a)

On suppose qu’il existe un facteur premier $q$ de $M$ de la forme $4 n + 3$ . Établir

${(2 N)}^{q - 1} \equiv - 1 [q] .$
(b)

Conclure en exploitant le petit théorème de Fermat.

Édité le 08-11-2019

	$x - 1 ∣ x + 3$	$\Leftrightarrow \frac{x + 3}{x - 1} = 1 + \frac{4}{x - 1} \in ℤ$
		$\Leftrightarrow x - 1 \in 𝒟 (4) = {1,2,4, - 1, - 2, - 4}$

	$x + 2 ∣ x^{2} + 2$	$\Leftrightarrow \frac{x^{2} + 2}{x + 2} = x - 2 + \frac{6}{x + 2} \in ℤ$
		$\Leftrightarrow x + 2 \in 𝒟 (6) = {1,2,3,6, - 1, - 2, - 3, - 6} .$