Exercice 1 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 2 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 3 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 4 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 5 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 6 4399

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

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

Exercice 7 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 8 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 9 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 10 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 11 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} .$

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

Édité le 29-08-2023

PGCD et PPCM