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.

Exercice 8 5964 CENTRALE (MP)Correction

Pour $n \in ℕ^{*}$ , on note $τ (n)$ le nombre de diviseurs positifs de $n$ et $σ (n)$ la somme de ceux-ci.

(a)

Coder une fonction qui donne $σ (n)$ et une autre qui donne $τ (n)$ .
(b)

Déterminer $n \geq 2$ tel que $σ (τ (n)) = n$ .
(c)

Tracer $n \mapsto σ (τ (n))$ et $n \mapsto 2^{5 / 2} n^{3 / 4}$ et conjecturer une inégalité.
(d)

Montrer $τ (n) \leq 2 \sqrt{n}$ .
(e)

Démontrer la conjecture de la question (c).
(f)

En déduire les points fixes de $σ \circ τ$ .
(g)

De même trouver les points fixes de $τ \circ σ$ .

On considère la série

\sum_{n \geq 1} \frac{τ^{2} (n)}{n^{3}} .

(h)

Montrer que cette série converge et donner une valeur approchée de $S$ à $10^{- 3}$ près.

Solution

(a)

On parcourt les entiers allant de $1$ à $n$ et l’on cumule les diviseurs de $n$ .

def s(n):
    res = 0
    for d in range(1, n+1):
        if n % d == 0:
            res += d
    return res

def t(n):
    res = 0
    for d in range(1, n+1):
        if n % d == 0:
            res += 1
    return res

(b)
À l’aide d’une boucle while, on recherche $n$ convenable.
```
n = 2
while s(t(n)) != n:
    n += 1
print(n)
```
On obtient $n = 3$ .

(c)

On représente les deux courbes


import matplotlib.pyplot as plt

N = list(range(1, 21))
plt.plot(N, [s(t(n)) for n in N])
plt.plot(N, [2**(5/2)*n**(3/4) for n in N])
plt.show()

On observe $σ (τ (n)) \leq 2^{5 / 2} n^{3 / 4}$ .

(d)

Les diviseurs $d$ de $n$ vont par paires $(d, n / d)$ et l’un des deux entiers est assurément inférieur à $\sqrt{n}$ . Il y a au plus $\sqrt{n}$ paires $(d, n / d)$ avec $d \leq n / d$ . Il y a donc au plus $2 \sqrt{n}$ diviseurs positifs de $n$ .
(e)

Il y a au plus $2 \sqrt{n}$ diviseurs de $n$ tous inférieurs à $n$ donc

$σ (n) \leq 2 \sqrt{n} \cdot n = 2 n^{3 / 2} .$

On en déduit

$σ (τ (n)) \leq 2 τ {(n)}^{3 / 2} \leq 2 \cdot 2^{3 / 2} \cdot n^{3 / 4} = 2^{5 / 2} \cdot n^{3 / 4} .$
(f)

Pour $n > 2^{10}$ ,

$n^{1 / 4} > 2^{5 / 2} donc n > 2^{5 / 2} \cdot n^{3 / 4} > σ (τ (n)) .$

Il n’y a donc pas de points fixes à $σ \circ τ$ en dehors de $⟦ 1; 1024 ⟧$
Il suffit de rechercher les solutions dans cet intervalle pour conclure.
```
n = 2
while n <= 1024:
    if s(t(n)) == n:
        print(n)
    n += 1
```
On obtient les valeurs $3$ , $4$ et $12$ .
(g)

On a

$τ (σ (n)) \leq 2 \sqrt{σ (n)} \leq 2 \cdot 2^{1 / 2} \cdot n^{3 / 4} = 2^{3 / 2} \cdot n^{3 / 4} .$

Cette fois-ci, les solutions figurent nécessairement dans $⟦ 1; 2^{6} ⟧$ . On obtient les valeurs $2$ , $3$ et $6$ .
(h)

On a

$0 \leq \frac{τ^{2} (n)}{n^{3}} \leq \frac{4 n}{n^{3}} = \frac{4}{n^{2}} .$

Par comparaison de séries à termes positifs, la série étudiée converge.
Le reste de rang $n$ de cette série vérifie

$0 \leq R_{n} = \sum_{k = n + 1}^{+ \infty} \frac{τ^{2} (k)}{k^{3}} \leq 4 \sum_{k = n + 1}^{+ \infty} \frac{1}{k^{2}} \leq 4 \int_{n}^{+ \infty} \frac{d t}{t^{2}} = \frac{4}{n} .$

Pour $n$ vérifiant $4 / n \leq 0.5 \cdot 10^{- 3}$ (par exemple $n = 8 000$ ), une valeur décimale approchée de $S_{n}$ à $10^{- 3}$ près répond à la question.
```
def S(n):
    res = 0
    for i in range(1, n+1):
        res += t(i)**2 / i**3
    return res

print(S(8000))
```
On obtient $S = 2, 052$ à $10^{- 3}$ près.

[<] Divisibilité[>] Calculs en congruence

Exercice 9 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 10 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 11 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 12 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 13 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 14 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 15 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 16 1194

Soient $x$ et $y$ deux entiers. Établir

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

Exercice 17 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 18 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 19 4398

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

Exercice 20 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 21 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 22 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 23 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 24 4399

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

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

Exercice 25 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 26 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 27 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 28 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 29 4409

(Suite de Fibonacci)

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

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

(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 30 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 31 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 32 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 33 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 34 1205 Correction

Soit $n \in ℕ^{*}$ .

(a)

Montrer que $n + 1$ et $2 n + 1$ sont premiers entre eux.
(b)

En déduire

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

Solution

(a)

On peut écrire $2 \times (n + 1) - 1 \times (2 n + 1) = 1$ . Par le théorème de Bézout, $(n + 1) \land (2 n + 1) = 1$ .
(b)

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 35 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 36 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 37 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 38 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 39 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.

Exercice 40 5734 Correction

Soient $n \in ℕ^{*}$ . Pour $q \in ℤ$ , on considère l’application

φ_{q} : {\begin{matrix} 𝕌_{n} & \to & 𝕌_{n} \\ z & \mapsto & z^{q} . \end{matrix}

(a)

Soient $p, q \in ℤ$ . Calculer $φ_{p} \circ φ_{q}$ .
(b)

On suppose que $n$ et $q$ sont premiers entre eux. Vérifier que l’application $φ_{q}$ est bijective.
(c)

Inversement, on suppose l’application $φ_{q}$ bijective, montrer que $n$ et $q$ sont premiers entre eux.

Solution

(a)

Pour tout $z \in 𝕌_{n}$ ,

$(φ_{p} \circ φ_{q}) (z) = φ_{p} (φ_{q} (z)) = φ_{p} (z^{q}) = {(z^{q})}^{p} = z^{p q} = φ_{p q} (z) .$

On a donc $φ_{p} \circ φ_{q} = φ_{p q}$ .
(b)

Supposons $n$ et $q$ premiers entre eux. Il existe $k, ℓ \in ℤ$ tels que $n k + q ℓ = 1$ . On vérifie $φ_{q} \circ φ_{ℓ} = φ_{q ℓ}$ avec

$\forall z \in 𝕌_{n}, φ_{q ℓ} (z) = z^{q ℓ} = z^{1 - n k} = z \cdot {(z^{n})}^{- k} = z .$

On a donc $φ_{q} \circ φ_{ℓ} = {Id}_{𝕌_{n}}$ . On vérifie de même $φ_{ℓ} \circ φ_{q} = {Id}_{𝕌_{n}}$ . On en déduit que $φ_{q}$ est bijective (et l’application $φ_{ℓ}$ est sa bijection réciproque).
(c)

Supposons l’application $φ_{q}$ bijective. Puisque $e^{2 i π / n}$ est élément de $𝕌_{n}$ , il existe $z \in 𝕌_{n}$ tel que $φ_{q} (z) = e^{2 i π / n}$ , c’est-à-dire il existe $k \in ⟦ 0; n - 1 ⟧$ tel que

${(e^{2 i k π / n})}^{q} = e^{2 i π / n} soit e^{2 i k q π / n} = e^{2 i π / n} .$

Par égalité de deux exponentielles imaginaires, il existe $ℓ \in ℤ$ tel que

$\frac{2 k q π}{n} = \frac{2 π}{n} + 2 π ℓ$

et donc

$k q - n ℓ = 1 .$

On en déduit que $k$ et $ℓ$ sont premiers entre eux.

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

Exercice 41 2653 ENTPE (MP)

Soit $p$ un nombre premier supérieur à $5$ .

Montrer que $p^{2} - 1$ est divisible par $24$ .

Exercice 42 3209 ENTPE (MP)Correction

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 43 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 44 4402

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

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

Exercice 45 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 46 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 47 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

Supposons $n = a b$ avec $a, b \in ℕ^{*}$ . On a alors

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

On a $2^{a} - 1 ∣ 2^{n} - 1$ . On en déduit $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 s’agit d’un nombre premier.

Exercice 48 1220

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

Exercice 49 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 50 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 51 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 52 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 53 2654 MINES (MP)

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

Exercice 54 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 55 1211

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

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

Exercice 56 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 57 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 58 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 59 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$ réelle et où les coefficients $a_{0}, a_{1}, \dots, a_{n - 1}$ sont supposés entiers.

Montrer que les solutions de $(E)$ sont des nombres entiers ou des nombres irrationnels.

Solution

Supposons $x = p / q \in ℚ$ une solution 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 des nombres entiers et cela répond à la question posée.

Exercice 60 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 61 1229 Correction

Soient $n \in ℕ ∖ {0, 1}$ et $n = \prod_{k = 1}^{N} p_{k}^{α_{k}}$ sa décomposition en produit de facteurs premiers.

Quel est le nombre de diviseurs positifs de $n$ ?

Solution

Les diviseurs positifs de $n$ 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 62 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$ deux nombres premiers distincts.

Exercice 63 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 64 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 65 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 $N = (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 $x \in ℤ$ .

Exercice 66 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 ce contexte.

(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 la valeur paire.

(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 67 4411

(Formule d’inversion de Möbius)

Pour $n \in ℕ^{*}$ , on pose¹¹ 1 En particulier, $μ (1) = 1$ .

μ (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}

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

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

où la somme porte sur les entiers $d$ diviseurs positifs de $n$ .

(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 68 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 69 3725

(Théorème d’Aubry)

Soient $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 70 5930 Correction

Soient $a, b \in ℤ$ et $p$ un nombre premier. On suppose qu’il existe $α \in ℕ^{*}$ tel que $p^{α}$ divise le ppcm de $a$ et $b$ . Établir que $p^{α}$ divise $a$ ou $b$ .

Solution

Notons $v_{p} (n)$ la valuation $p$ -adique $n \in ℕ^{*}$ :

v_{p} (n) = \max {k \in ℕ | p^{k} ∣ n} .

On sait

v_{p} (a \lor b) = \max (v_{p} (a), v_{p} (b)) .

Si $p^{α}$ divise $a \lor b$ , alors $\max (v_{p} (a), v_{p} (b)) \geq α$ et donc $v_{p} (a) \geq α$ ou $v_{p} (b) \geq α$ . On en déduit que $p^{α}$ divise $a$ ou $b$ .

Exercice 71 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 72 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 73 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.

Exercice 74 5689 Correction

Soit $n \in ℕ^{*}$ . Si $n = \bar{ε_{p} ε_{p - 1} \dots ε_{0}}$ est l’espression de $n$ en base $2$ on note

s (n) = ε_{0} + \dots + ε_{p} et v (n) la valuation de n en base 2

(a)

Écrire une fonction calculant $v (n)$ et $s (n)$ .
(b)

Si $n \in {2, \dots {,10}^{4}}$ , vérifier numériquement que $v (n) = s (n - 1) - s (n) + 1$ .
(c)

Prouver que pour tout $n \geq 2$ , $v (n) = s (n - 1) - s (n) + 1$ .
(d)

Calculer $v (n!)$ en fonction de $n$ et $s (n)$ .
(e)

Soit $n \in ℕ^{*}$ . Montrer que $n$ est une puissance de $2$ si, et seulement si, $(\binom{n}{k})$ est un entier pair pour tout $k = 1, \dots, n - 1$ .

Solution

(a)

Tant qu’une puissance de $2$ divise $n$ , on passe à la puissance suivante:

def v(n):
    k = 0
    p = 1
    while n % (2*p) == 0:
        k = k + 1
        p = 2 * p
    return k

Pour calculer $s (n)$ , une solution récursive est possible:

def s(n):
    if n == 0:
        return 0
    elif n % 2 == 0:
        return s(n//2)
    else:
        return 1 + s((n-1) // 2)

(b)

On vérifie qu’aucune valeur n’échoue

for n in range(2, 10**4+1):
    if v(n) != s(n-1) - s(n) + 1:
        print(f"Echec pour la valeur {n}")

(c)

Posons $p$ la valuation de $n$ en base $2$ . L’écriture en base $2$ de $n$ se termine par $\bar{10 \dots 0}$ avec un nombre de zéro égal à $p$ . L’écriture de $n - 1$ commence par les mêmes chiffres mais se termine par $\bar{01 \dots 1}$ . On en déduit $s (n - 1) - s (n) = p - 1 = v (n) - 1$ .
(d)

Pour $p, q \in ℕ^{*}$ , $v (p q) = v (p) + v (q)$ donc

$v (n!) = \sum_{k = 1}^{n} v (k) = v (1) + \sum_{k = 2}^{n} (s (k - 1) - s (k) + 1) = n - s (n)$
(e)

Cas: $n = 1$ ou $n = 2$ . C’est immédiat.

Cas: $n \geq 3$ . Soit $k \in {1, \dots, n - 1}$ . On remarque

$v ((\binom{n}{k})) = v (n!) - v (k!) - v ((n - k)!) = s (k) + s (n - k) - s (n)$

Si $n$ vaut $2^{p}$ , son écriture en base de $2$ est de la forme $\bar{10 \dots 0}$ avec $p$ chiffres $0$ . Pour $k \in {1, \dots, n - 1}$ , les chiffres de l’écriture en base $2$ de $n - k$ sont les « inverses » des chiffres en base de $2$ de $k$ puisque $k + (n - k) = n$ . En particulier, $s (k) + s (n - k) = p$ . On a donc $s (k) + s (n - k) - s (n) = p - 1 > 0$ . Le coefficient binomial $(\binom{n}{k})$ est pair.

Si $n$ n’est pas une puissance de $2$ , on peut écrire avec $n = \bar{ε_{p} \dots ε_{q + 1} 10 \dots 0}$ . Considérons alors $k = 2^{q}$ . On a $s (k) = 1$ et $s (n - k) = ε_{p} + \dots + ε_{q + 1}$ donc $s (k) + s (n - k) = s (n)$ . Par conséquent, la valuation en base $2$ du coefficient binomial $(\binom{n}{k})$ est nulle: c’est entier est impair.

[<] Valuation p-adique

Exercice 75 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 76 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 77 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 78 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 22-11-2024

	$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} .$