PGCD, Algorithme d'Euclide et Théorème de Bézout
L'essentiel du cours (2 notions)
Algorithme d'Euclide et écriture du PGCD
Propriété : Pour $a,b \in \mathbb{Z}^*$, le dernier reste non nul des divisions euclidiennes successives est $\text{PGCD}(a,b)$. Il existe $(x,y) \in \mathbb{Z}^2$ tel que $ax + by = \text{PGCD}(a,b)$.
Méthode : 1. Effectuer les divisions euclidiennes successives jusqu'au reste nul. 2. Remonter la suite des égalités pour exprimer le PGCD sous la forme $ax + by$.
Exemple : $17 = 5 \times 3 + 2$ puis $5 = 2 \times 2 + 1$. $\text{PGCD}(17,5) = 1$. Remontée : $1 = 5 - 2 \times 2 = 17 \times (-2) + 5 \times 7$.
Théorème de Bézout
Définition : Deux entiers relatifs non nuls $a$ et $b$ sont dits premiers entre eux lorsque leur PGCD vaut $1$, soit $\text{PGCD}(a,b) = 1$.
Propriété : Deux entiers $a$ et $b$ sont premiers entre eux si et seulement s'il existe $(x,y) \in \mathbb{Z}^2$ tel que $ax + by = 1$.
Exemple : Comme $7 \times (-3) + 11 \times 2 = 1$, d'après le théorème de Bézout, $7$ et $11$ sont premiers entre eux.
On considère les entiers $a = 122$ et $b = 35$.
En utilisant l'algorithme d'Euclide :
- Calculer $\text{PGCD}(122, 35)$ puis déterminer un couple d'entiers relatifs $(x_0, y_0)$ vérifiant $122 x_0 + 35 y_0 = \text{PGCD}(122, 35)$.
- En déduire l'expression générale des entiers $x$ vérifiant l'égalité, puis déterminer la plus petite valeur entière $x$ strictement positive solution de $122 x + 35 y = 1$.
Saisir la valeur minimale strictement positive de $x$.
On considère les entiers $a = 37$ et $b = 24$.
À l'aide de l'algorithme d'Euclide et du théorème de Bézout, on cherche un couple d'entiers relatifs $(u, v)$ tel que :
$$37u + 24v = 1$$avec la condition $0 \le u < 24$.
Déterminer la valeur de l'entier $u$.
Soit $n$ un entier naturel non nul. On définit les entiers $a_n = 11n + 4$ et $b_n = 7n + 1$.
Un élève affirme que pour tout entier naturel non nul $n$, les entiers $a_n$ et $b_n$ sont premiers entre eux.
Déterminer le plus petit entier naturel non nul $n$ qui infirme cette affirmation.
Saisir la valeur de cet entier $n$.
On considère les deux entiers $a = 348$ et $b = 129$.
En effectuant l'algorithme d'Euclide puis en remontant successivement les égalités obtenues, on détermine un couple d'entiers relatifs $(x, y)$ satisfaisant l'égalité :
$$a x + b y = \text{PGCD}(a, b)$$Un paramètre entier $k$ est défini par la relation $k = 2x + y$.
Saisir la valeur de $k$.
Pour tout entier naturel non nul $k$, on pose $a = 15k + 7$ et $b = 4k + 1$.
Déterminer le plus petit entier naturel $k$ strictement supérieur à $100$ tel que $a$ et $b$ ne soient pas premiers entre eux.
Saisir la valeur de $k$.
Pour tout entier naturel $n$, on pose $A(n) = 3n^2 + 11n + 19$ et $B(n) = 2n + 3$.
On cherche à déterminer la plus petite valeur de l'entier naturel $n$ supérieure ou égale à $100$ pour laquelle les entiers $A(n)$ et $B(n)$ ne sont pas premiers entre eux.
Saisir la valeur de $n$.