BURHAN.

Nombres premiers entre eux et théorème de Bézout : Cours de Mathématiques 2BAC Sciences Mathématiques, chapitre Arithmétique dans ℤ

Nombres premiers entre eux et théorème de Bézout : notion du chapitre Arithmétique dans ℤ du programme de maths 2BAC SM, expliquée pas à pas, avec 2 exemples guidés. Pour les élèves de 2BAC SM A et SM B, option française (BIOF).

Notions du cours (11)

Apprendre avec Burhan

Premiers entre eux et théorème de Bézout

Étape 1 sur 4

Ce que donnent les combinaisons

Prouver que deux expressions en nn sont premières entre elles tient en deux lignes, à condition de savoir fabriquer un 11.

Ce 11 s'écrit avec les deux nombres : c'est toute l'idée de Bézout. Commence par une petite enquête.

Devine : Des combinaisons de 6 et 10

On cherche des entiers relatifs uu et vv tels que 6u+10v6u + 10v vaille 11, puis 22. Qu'en penses-tu ?

Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.

Choix A :On peut obtenir 11 et 22.

Faux.

6u+10v=2(3u+5v)6u + 10v = 2(3u + 5v) est toujours pair : il ne vaut jamais 11.

Choix B :On ne peut pas obtenir 11, mais on peut obtenir 22.

Juste.

6u+10v6u + 10v est pair, donc différent de 11. Et 6×2+10×(−1)=26 \times 2 + 10 \times (-1) = 2.

Choix C :On peut obtenir 11, mais pas 22.

Faux.

Tout est pair dans 6u+10v6u + 10v : si 11 était atteint, il serait pair.

Choix D :On n'obtient ni 11 ni 22.

Faux.

22 est atteint : 6×2+10×(−1)=12−10=26 \times 2 + 10 \times (-1) = 12 - 10 = 2.

Besoin d'aide ? Indice 1

Factorise 6u+10v6u + 10v par 22.

Encore bloqué ? Indice 2

Pour obtenir 22, essaie u=2u = 2.

Voir la correction complète

6u+10v=2(3u+5v)6u + 10v = 2(3u + 5v) est toujours pair : 11 est impossible. Le couple (2,−1)(2, -1) donne 6×2+10×(−1)=26 \times 2 + 10 \times (-1) = 2. Le plus petit entier strictement positif atteint est donc 22, c'est-à-dire 6∧106 \wedge 10.

DéfinitionEntiers premiers entre eux

Deux entiers relatifs aa et bb, non tous les deux nuls, sont premiers entre eux si a∧b=1a \wedge b = 1, c'est-à-dire si leur seul diviseur commun positif est 11.

ExemplePremiers entre eux ou non ?

  • 9∧28=19 \wedge 28 = 1 : 99 et 2828 sont premiers entre eux, sans être premiers.
  • 21∧35=721 \wedge 35 = 7 : ils ne sont pas premiers entre eux.

Continuer : L'identité de Bézout →

Étape 2 sur 4

L'identité de Bézout

Pourquoi le PGCD est-il toujours une combinaison au+bvau + bv ? Idée : on prend la plus petite combinaison strictement positive, et on montre qu'elle divise aa et bb.

Rappel. Toute partie non vide de N\mathbb{N} possède un plus petit élément. Par exemple, les entiers naturels non nuls de la forme 6u+10v6u + 10v ont pour plus petit élément 22.

ThéorèmeIdentité de Bézout

Soient aa et bb deux entiers relatifs non tous les deux nuls, et d=a∧bd = a \wedge b.

  1. Il existe deux entiers relatifs uu et vv tels que au+bv=dau + bv = d.
  2. Un entier relatif divise à la fois aa et bb si et seulement s'il divise dd.

Démonstration

Étape 1. L'ensemble EE des entiers naturels non nuls de la forme au+bvau + bv, avec u,v∈Zu, v \in \mathbb{Z}, contient a2+b2=a×a+b×b>0a^2 + b^2 = a \times a + b \times b > 0. Partie non vide de N\mathbb{N}, il a donc un plus petit élément m=au0+bv0m = au_0 + bv_0.

Étape 2 (m∣am \mid a). On écrit a=mq+ra = mq + r avec 0≤r<m0 \leq r < m (« Division euclidienne dans ℤ »). Alors r=a(1−qu0)+b(−qv0)r = a(1 - qu_0) + b(-qv_0). Si r>0r > 0, alors r∈Er \in E et r<mr < m : impossible. Donc r=0r = 0 et m∣am \mid a. De même, m∣bm \mid b.

Étape 3 (m=dm = d). mm est un diviseur commun positif, donc m≤dm \leq d. Or d∣ad \mid a et d∣bd \mid b, donc d∣au0+bv0=md \mid au_0 + bv_0 = m (« Propriétés de la divisibilité », point 2), puis d≤md \leq m (« Propriétés de la divisibilité », point 3). Ainsi d=m=au0+bv0d = m = au_0 + bv_0.

Étape 4 (point 2). Si c∣ac \mid a et c∣bc \mid b, alors c∣au0+bv0=dc \mid au_0 + bv_0 = d. Si c∣dc \mid d, alors c∣ac \mid a et c∣bc \mid b par transitivité (« Propriétés de la divisibilité », point 1).

À retenirCe qu'il faut retenir de la preuve

On ne calcule pas uu et vv : on prend la plus petite valeur strictement positive mm de au+bvau + bv.

La division euclidienne par mm et la minimalité montrent que mm divise aa et bb. Deux inégalités, m≤dm \leq d et d≤md \leq m, donnent ensuite m=dm = d.

Vérifie : Une inégalité de l'étape 3

À l'étape 3, comment obtient-on d≤md \leq m ?

Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.

Choix A :mm est le plus petit élément de EE.

Faux.

La minimalité de mm sert à l'étape 2. Elle compare mm aux éléments de EE, pas à dd.

Choix B :dd est le plus grand diviseur commun et mm en est un.

Faux.

Cet argument est correct, mais il donne l'autre inégalité : m≤dm \leq d.

Choix C :dd divise aa et bb, donc dd divise au0+bv0=mau_0 + bv_0 = m, avec m>0m > 0.

Juste.

Un diviseur commun divise toute combinaison, et un diviseur d'un entier non nul ne le dépasse pas (propriétés de la divisibilité, points 2 et 3).

Voir la correction complète

Comme d∣ad \mid a et d∣bd \mid b, on a d∣au0+bv0=md \mid au_0 + bv_0 = m. Or m≠0m \neq 0, donc d≤∣m∣=md \leq \lvert m \rvert = m. Avec m≤dm \leq d, on obtient d=md = m.

ExempleNi unicité, ni cas nul

  • Le couple n'est pas unique : 6×2+10×(−1)=26 \times 2 + 10 \times (-1) = 2 et 6×(−3)+10×2=26 \times (-3) + 10 \times 2 = 2.
  • L'hypothèse « non tous les deux nuls » est nécessaire : si a=b=0a = b = 0, toute combinaison vaut 00, et a∧ba \wedge b n'est pas défini.

Pour d=1d = 1, l'identité donne au+bv=1au + bv = 1. Et la réciproque ? Pourquoi une telle égalité suffit-elle à prouver a∧b=1a \wedge b = 1 ? Regarde ce que divise un diviseur commun.

← Étape précédenteContinuer : Le théorème de Bézout →

Étape 3 sur 4

Le théorème de Bézout

ThéorèmeThéorème de Bézout

Deux entiers relatifs aa et bb sont premiers entre eux si et seulement s'il existe deux entiers relatifs uu et vv tels que au+bv=1.au + bv = 1.

Démonstration

Sens direct. Si a∧b=1a \wedge b = 1, alors aa et bb ne sont pas tous les deux nuls et l'identité de Bézout (point 1) fournit uu et vv tels que au+bv=1au + bv = 1.

Réciproque. Supposons au+bv=1au + bv = 1. Alors aa et bb ne sont pas tous les deux nuls. Soit cc un diviseur commun positif de aa et bb. D'après « Propriétés de la divisibilité » (point 2), c∣au+bv=1c \mid au + bv = 1, donc c≤1c \leq 1 (« Propriétés de la divisibilité », point 3), c'est-à-dire c=1c = 1. Le seul diviseur commun positif est 11 : a∧b=1a \wedge b = 1.

À retenirCe qu'il faut retenir de la preuve

Le sens direct est le cas d=1d = 1 de l'identité de Bézout.

La réciproque n'utilise que les propriétés de la divisibilité. Retiens surtout le rôle du 11 : son seul diviseur positif est 11.

Vérifie : La réciproque

Dans la réciproque, on suppose au+bv=1au + bv = 1. Quel argument fait passer de « cc divise aa et bb » à « cc divise 11 » ?

Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.

Choix A :Un diviseur commun de aa et bb divise toute combinaison au+bvau + bv.

Juste.

C'est le point 2 des propriétés de la divisibilité, appliqué à au+bv=1au + bv = 1.

Choix B :Le théorème de Gauss.

Faux.

Gauss se démontre à partir de Bézout : l'utiliser ici rendrait le raisonnement circulaire.

Choix C :La transitivité : c∣ac \mid a et a∣1a \mid 1.

Faux.

Rien n'assure que aa divise 11 : la transitivité ne s'applique pas ici.

Voir la correction complète

Si c∣ac \mid a et c∣bc \mid b, alors c∣au+bvc \mid au + bv (propriétés de la divisibilité, point 2), c'est-à-dire c∣1c \mid 1. Pour cc positif, cela donne c=1c = 1 : le seul diviseur commun positif est 11, et a∧b=1a \wedge b = 1.

AttentionLa réciproque de Bézout ne vaut que pour 1

10×2+4×(−3)=810 \times 2 + 4 \times (-3) = 8, et pourtant 10∧4=210 \wedge 4 = 2, pas 88.

Une égalité au+bv=kau + bv = k montre seulement que a∧ba \wedge b divise kk. Pour k=1k = 1, elle suffit : a∧b=1a \wedge b = 1. Pour conclure a∧b=ka \wedge b = k avec k≥2k \geq 2, il faut en plus vérifier que kk divise aa et bb.

← Étape précédenteContinuer : Construire un couple de Bézout →

Étape 4 sur 4

Construire un couple de Bézout

Méthoderemonter l'algorithme d'Euclide

  1. Isoler les restes des divisions de l'algorithme d'Euclide.
  2. Remonter du dernier reste non nul, en remplaçant chaque reste par son expression.
  3. Vérifier le couple trouvé par un calcul direct.

Avec le tableau de 391391 et 299299 : 23=299−3×9223 = 299 - 3 \times 92 et 92=391−29992 = 391 - 299.

23=299−3×(391−299)=4×299−3×391.\begin{aligned} 23 &= 299 - 3 \times (391 - 299) \\ &= 4 \times 299 - 3 \times 391. \end{aligned}

Rédaction attendue. « On a 391×(−3)+299×4=23=391∧299391 \times (-3) + 299 \times 4 = 23 = 391 \wedge 299 : le couple (u,v)=(−3,4)(u, v) = (-3, 4) convient. »

À toi : une remontée en trois étapes

L'algorithme d'Euclide donne, pour 8383 et 1919 : 83=19×4+783 = 19 \times 4 + 7, 19=7×2+519 = 7 \times 2 + 5, 7=5×1+27 = 5 \times 1 + 2 et 5=2×2+15 = 2 \times 2 + 1. La remontée est commencée :

1=5−2×2=5−2×(7−5)=3×5−2×7.\begin{aligned} 1 &= 5 - 2 \times 2 \\ &= 5 - 2 \times (7 - 5) = 3 \times 5 - 2 \times 7. \end{aligned}

Termine-la : trouve des entiers uu et vv tels que 83u+19v=183u + 19v = 1, puis vérifie ton couple.

Besoin d'aide ? Indice 1

Isole le reste 55 dans la deuxième division : 5=19−2×75 = 19 - 2 \times 7.

Encore bloqué ? Indice 2

Remplace 55 dans 3×5−2×73 \times 5 - 2 \times 7, puis regroupe les 77 : tu dois obtenir 3×19−8×73 \times 19 - 8 \times 7.

Encore bloqué ? Indice 3

Garde 1919 et 77 comme des briques, sans calculer les produits. Remplace enfin 77 par 83−4×1983 - 4 \times 19.

Voir la solution complète
1=3×5−2×7=3×(19−2×7)−2×7=3×19−8×7=3×19−8×(83−4×19)=35×19−8×83.\begin{aligned} 1 &= 3 \times 5 - 2 \times 7 \\ &= 3 \times (19 - 2 \times 7) - 2 \times 7 = 3 \times 19 - 8 \times 7 \\ &= 3 \times 19 - 8 \times (83 - 4 \times 19) = 35 \times 19 - 8 \times 83. \end{aligned}

Vérification. 83×(−8)+19×35=−664+665=183 \times (-8) + 19 \times 35 = -664 + 665 = 1. Le couple (u,v)=(−8,35)(u, v) = (-8, 35) convient. D'après le théorème de Bézout, 8383 et 1919 sont premiers entre eux.

À toi : Coin examen

Soit nn un entier naturel. Montrer que 5n+25n + 2 et 3n+13n + 1 sont premiers entre eux. (0,5 point, barème indicatif BURHAN.)

Point important : établir une relation au+bv=1au + bv = 1 est une question à maîtriser.

Besoin d'aide ? Indice 1

Cherche des entiers uu et vv, indépendants de nn, qui éliminent nn.

Encore bloqué ? Indice 2

Essaie u=3u = 3 et v=−5v = -5.

Encore bloqué ? Indice 3

Conclus en citant le théorème de Bézout et le couple trouvé.

Voir la solution complète

Rédaction attendue.

On a 3(5n+2)−5(3n+1)=15n+6−15n−5=13(5n + 2) - 5(3n + 1) = 15n + 6 - 15n - 5 = 1. (0,25 point)

Ainsi (5n+2)×3+(3n+1)×(−5)=1(5n + 2) \times 3 + (3n + 1) \times (-5) = 1, avec 33 et −5-5 entiers. D'après le théorème de Bézout, 5n+25n + 2 et 3n+13n + 1 sont premiers entre eux. (0,25 point)

← Étape précédenteFin de la notion

S'entraîner sur cette notion

Sources du cours

  • Référentiel BURHAN du chapitre « Arithmétique dans ℤ » (2bac · sciences-mathematiques · mathematiques)