Lessons and exercises follow the school system and stay in its language.Les leçons et les exercices suivent le système scolaire et restent dans sa langue.Lektionen und Übungen folgen dem Schulsystem und bleiben in seiner Sprache.

PGCD, Bézout et Gauss

Imprimer le chapitre

Toutes les leçons du chapitre, prêtes pour le papier. Les séries d'exercices sont notées A, B, C… et corrigées à la fin.

Pour obtenir un PDF, choisis « Enregistrer au format PDF » dans la fenêtre d'impression.

1. PGCD et algorithme d'Euclide

Échauffement

Trois questions rapides sur des leçons déjà vues.

  1. Quel est le reste de la division euclidienne de 1414 par 3 ?
  2. Quel est le reste de la division euclidienne de −10-10 par 4 ?
  3. On sait que 9 divise xx et yy. Quel nombre 9 divise-t-il toujours ?
    1. 7x+4y7x + 4y
    2. x+1x + 1
    3. xy\dfrac{x}{y}

Découvrir

Quel est le plus grand diviseur commun à 12 et 18 ?

  1. 66
  2. 3636

L'idée clé

L'algorithme d'Euclide répète des divisions euclidiennes.

PGCD(a;b)=PGCD(b;r)\mathrm{PGCD}(a ; b) = \mathrm{PGCD}(b ; r), où rr est le reste de la division de aa par bb. Le PGCD est le dernier reste non nul.

aa et bb sont premiers entre eux si PGCD(a;b)=1\mathrm{PGCD}(a ; b) = 1.

Exemple corrigé

Calcule PGCD(252;105)\mathrm{PGCD}(252 ; 105).

PGCD(105;42)\mathrm{PGCD}(105 ; 42)
252 = 105 × 2 + 42.
PGCD(42;21)\mathrm{PGCD}(42 ; 21)
105 = 42 × 2 + 21.
2121
42 = 21 × 2 + 0.

À toi, guidé

À toi : calcule PGCD(35;14)\mathrm{PGCD}(35 ; 14).

77
35 = 14 × 2 + 7, 14 = 7 × 2.

Entraînement ★

  1. Calcule PGCD(21;24)\mathrm{PGCD}(21 ; 24).
  2. Calcule PGCD(350;400)\mathrm{PGCD}(350 ; 400).
  3. Calcule PGCD(14;16)\mathrm{PGCD}(14 ; 16).

Attention !

Entraînement ★★

  1. Les nombres 55 et 66 sont-ils premiers entre eux ?
    1. Oui, toujours
    2. Seulement s'ils sont premiers
    3. Non
  2. Les nombres 22 et 33 sont-ils premiers entre eux ?
    1. Oui, toujours
    2. Seulement s'ils sont premiers
    3. Non
  1. Calcule PGCD(12;4)\mathrm{PGCD}(12 ; 4).
  1. Dans l'algorithme d'Euclide pour 1717 et 7, on remplace le couple par (7 ; rr). Que vaut rr ?

Bilan

Trois questions pour vérifier que c'est acquis.

  1. Calcule PGCD(21;24)\mathrm{PGCD}(21 ; 24).
  2. Calcule PGCD(350;400)\mathrm{PGCD}(350 ; 400).
  3. Calcule PGCD(14;16)\mathrm{PGCD}(14 ; 16).

Fiche résumé

PGCD

  • PGCD(a;b)=PGCD(b;r)\mathrm{PGCD}(a ; b) = \mathrm{PGCD}(b ; r).
  • Dernier reste non nul.

Attention : ne confonds pas avec le dernier quotient.

Il reste une étape facultative : un défi. Tente-le, ou termine la leçon maintenant.

Défi ★★★

  1. Calcule PGCD(108;162)\mathrm{PGCD}(108 ; 162).

2. Théorème de Bézout

Échauffement

Trois questions rapides sur des leçons déjà vues.

  1. Calcule PGCD(21;24)\mathrm{PGCD}(21 ; 24).
  2. Les nombres 55 et 66 sont-ils premiers entre eux ?
    1. Oui, toujours
    2. Seulement s'ils sont premiers
    3. Non
  3. Calcule PGCD(12;4)\mathrm{PGCD}(12 ; 4).

Découvrir

On a 3×2+5×(−1)=13 \times 2 + 5 \times (-1) = 1. Que peut-on dire de 3 et 5 ?

  1. Ils sont premiers entre eux
  2. Ils ont 2 pour diviseur commun

L'idée clé

Le théorème relie PGCD et combinaisons linéaires.

Bézout : aa et bb sont premiers entre eux si et seulement s'il existe des entiers uu et vv tels que au+bv=1au + bv = 1.

Plus généralement, il existe uu et vv tels que au+bv=PGCD(a;b)au + bv = \mathrm{PGCD}(a ; b).

Exemple corrigé

Trouve un couple (u;v)(u ; v) tel que 7u+3v=17u + 3v = 1.

7=3×2+17 = 3 \times 2 + 1
Euclide.
1=7×1+3×(−2)1 = 7 \times 1 + 3 \times (-2)
On isole 1.
(u;v)=(1;−2)(u ; v) = (1 ; -2)
On lit.

À toi, guidé

À toi : avec 5u+2v=15u + 2v = 1 et u=1u = 1, que vaut vv ?

−2-2
5 + 2v = 1.

Entraînement ★

  1. On a 7×1+3×v=17 \times 1 + 3 \times v = 1. Que vaut vv ?
  2. On a 77×1+38×v=177 \times 1 + 38 \times v = 1. Que vaut vv ?
  3. On a 9×1+4×v=19 \times 1 + 4 \times v = 1. Que vaut vv ?

Attention !

Entraînement ★★

  1. Existe-t-il des entiers uu et vv tels que 12u+24v=112u + 24v = 1 ?
    1. Non, car le PGCD n'est pas 1
    2. Oui, toujours
    3. Oui, avec u=v=1u = v = 1
  2. Existe-t-il des entiers uu et vv tels que 10u+20v=110u + 20v = 1 ?
    1. Non, car le PGCD n'est pas 1
    2. Oui, toujours
    3. Oui, avec u=v=1u = v = 1
  1. Avec u=1u = 1 et v=−2v = -2, que vaut (5)u+2v(5)u + 2v ?
  1. Selon le théorème de Bézout, que signifie l'existence d'entiers uu, vv tels que au+bv=1au + bv = 1 ?
    1. aa et bb sont premiers entre eux
    2. aa divise bb
    3. aa et bb sont des nombres premiers

Bilan

Trois questions pour vérifier que c'est acquis.

  1. On a 7×1+3×v=17 \times 1 + 3 \times v = 1. Que vaut vv ?
  2. On a 77×1+38×v=177 \times 1 + 38 \times v = 1. Que vaut vv ?
  3. On a 9×1+4×v=19 \times 1 + 4 \times v = 1. Que vaut vv ?

Fiche résumé

Bézout

  • au+bv=1  ⟺  PGCD(a;b)=1au + bv = 1 \iff \mathrm{PGCD}(a ; b) = 1.
  • On remonte l'algorithme d'Euclide.

Attention : le couple (u;v)(u ; v) n'est pas unique.

Il reste une étape facultative : un défi. Tente-le, ou termine la leçon maintenant.

Défi ★★★

  1. On cherche uu et vv entiers tels que 13u+8v=113u + 8v = 1. Avec l'algorithme d'Euclide, on trouve u=−3u = -3. Que vaut vv ?

3. Théorème de Gauss

Échauffement

Trois questions rapides sur des leçons déjà vues.

  1. On a 7×1+3×v=17 \times 1 + 3 \times v = 1. Que vaut vv ?
  2. Existe-t-il des entiers uu et vv tels que 12u+24v=112u + 24v = 1 ?
    1. Non, car le PGCD n'est pas 1
    2. Oui, toujours
    3. Oui, avec u=v=1u = v = 1
  3. Avec u=1u = 1 et v=−2v = -2, que vaut (5)u+2v(5)u + 2v ?

Découvrir

3 divise 5x5x. Peut-on affirmer que 3 divise xx ?

  1. Oui, car 3 et 5 sont premiers entre eux
  2. Non, jamais

L'idée clé

Ce théorème sert à résoudre des équations en entiers.

Gauss : si aa divise bcbc et si aa et bb sont premiers entre eux, alors aa divise cc.

Exemple corrigé

On sait que 7x=4y7x = 4y, avec xx et yy entiers. Que dire de yy ?

7∣4y7 \mid 4y
7 divise 4y.
7∣y7 \mid y
7 et 4 sont premiers entre eux.

À toi, guidé

À toi : 5 divise 3n3n. Lequel divise nn ?

55
5 et 3 sont premiers entre eux.

Entraînement ★

  1. On sait que 5 divise 11n11n, avec nn entier. Quel est le plus petit entier n>0n > 0 possible ?
  2. On sait que 7 divise 8n8n, avec nn entier. Quel est le plus petit entier n>0n > 0 possible ?
  3. On sait que 3 divise 8n8n, avec nn entier. Quel est le plus petit entier n>0n > 0 possible ?

Attention !

Entraînement ★★

  1. Quelle hypothèse faut-il pour appliquer le théorème de Gauss à « aa divise bcbc » ?
    1. aa et bb sont premiers entre eux
    2. aa est pair
    3. bb et cc sont égaux
  2. Quelle hypothèse faut-il pour appliquer le théorème de Gauss à « aa divise bcbc » ?
    1. aa et bb sont premiers entre eux
    2. aa est pair
    3. bb et cc sont égaux
  1. 7 divise 9n9n, et 7 et 9 sont premiers entre eux. Quel est le plus petit entier n>0n > 0 possible ?
  1. 6 divise 4×34 \times 3. Peut-on en conclure que 6 divise 4 ou 3 ?
    1. Non : 6 n'est premier ni avec 4 ni avec 3
    2. Oui : par le théorème de Gauss
    3. Oui : 6 divise toujours un facteur

Bilan

Trois questions pour vérifier que c'est acquis.

  1. On sait que 5 divise 11n11n, avec nn entier. Quel est le plus petit entier n>0n > 0 possible ?
  2. On sait que 7 divise 8n8n, avec nn entier. Quel est le plus petit entier n>0n > 0 possible ?
  3. On sait que 3 divise 8n8n, avec nn entier. Quel est le plus petit entier n>0n > 0 possible ?

Fiche résumé

Gauss

  • Si a∣bca \mid bc et PGCD(a;b)=1\mathrm{PGCD}(a ; b) = 1, alors a∣ca \mid c.
  • Base des équations diophantiennes.

Attention : vérifie toujours « premiers entre eux ».

Il reste une étape facultative : un défi. Tente-le, ou termine la leçon maintenant.

Défi ★★★

  1. 12 divise 8n8n. Quel est le plus petit entier n>0n > 0 possible ?

4. Congruence ax ≡ b, inverse modulo n et chiffrement

Échauffement

Trois questions rapides sur des leçons déjà vues.

  1. Quel est le plus petit entier positif xx tel que 21≡x [5]21 \equiv x\ [5] ?
  2. Quel est le reste de la division de 282^{ 8 } par 5 ?
  3. On sait que x≡2 [9]x \equiv 2\ [9] et y≡1 [9]y \equiv 1\ [9]. Quel est le reste de x+yx + y modulo 9 ?

Découvrir

On veut résoudre 3x≡1 [7]3x \equiv 1\ [7]. Quelle valeur de xx convient ?

  1. 55
  2. 13\dfrac{1}{3}

L'idée clé

On ne divise pas : on multiplie par un inverse.

Si aa et nn sont premiers entre eux, il existe un inverse a′a' de aa modulo nn : aa′≡1 [n]aa' \equiv 1\ [n]. Alors ax≡b [n]  ⟺  x≡a′b [n]ax \equiv b\ [n] \iff x \equiv a'b\ [n].

Chiffrement affine : on code xx par y≡ax+b [26]y \equiv ax + b\ [26] ; pour déchiffrer, on utilise l'inverse de aa modulo 26.

Exemple corrigé

Résous 3x≡4 [7]3x \equiv 4\ [7].

5×3≡1 [7]5 \times 3 \equiv 1\ [7]
L'inverse de 3 est 5.
x≡20 [7]x \equiv 20\ [7]
On multiplie par 5.
x≡6 [7]x \equiv 6\ [7]
On réduit.

À toi, guidé

À toi : quel est l'inverse de 2 modulo 5 ?

33
2 × 3 = 6 ≡ 1.

Entraînement ★

  1. Résous 3x≡12 [7]3x \equiv 12\ [7] : donne la solution xx entre 0 et 6. (L'inverse de 3 modulo 7 est 5.)
  2. Résous 3x≡9 [7]3x \equiv 9\ [7] : donne la solution xx entre 0 et 6. (L'inverse de 3 modulo 7 est 5.)
  3. Résous 3x≡6 [7]3x \equiv 6\ [7] : donne la solution xx entre 0 et 6. (L'inverse de 3 modulo 7 est 5.)

Attention !

Entraînement ★★

  1. Avec le chiffrement y≡3x+1 [26]y \equiv 3x + 1\ [26], quel nombre yy code x=3x = 3 ?
  2. Avec le chiffrement y≡3x+1 [26]y \equiv 3x + 1\ [26], quel nombre yy code x=8x = 8 ?
  1. Quel est l'inverse de 2 modulo 5 ?
  1. Résous 2x≡10 [11]2x \equiv 10\ [11] : donne xx entre 0 et 10.

Bilan

Trois questions pour vérifier que c'est acquis.

  1. Résous 3x≡12 [7]3x \equiv 12\ [7] : donne la solution xx entre 0 et 6. (L'inverse de 3 modulo 7 est 5.)
  2. Résous 3x≡9 [7]3x \equiv 9\ [7] : donne la solution xx entre 0 et 6. (L'inverse de 3 modulo 7 est 5.)
  3. Résous 3x≡6 [7]3x \equiv 6\ [7] : donne la solution xx entre 0 et 6. (L'inverse de 3 modulo 7 est 5.)

Fiche résumé

Inverse modulo nn

  • Il existe si PGCD(a;n)=1\mathrm{PGCD}(a ; n) = 1.
  • ax≡b  ⟺  x≡a′b [n]ax \equiv b \iff x \equiv a'b\ [n].

Attention : on multiplie, on ne divise pas.

Il reste une étape facultative : un défi. Tente-le, ou termine la leçon maintenant.

Défi ★★★

  1. Quel est l'inverse de 3 modulo 11, entre 0 et 10 ?

5. Équations diophantiennes

Échauffement

Trois questions rapides sur des leçons déjà vues.

  1. On sait que 5 divise 11n11n, avec nn entier. Quel est le plus petit entier n>0n > 0 possible ?
  2. Quelle hypothèse faut-il pour appliquer le théorème de Gauss à « aa divise bcbc » ?
    1. aa et bb sont premiers entre eux
    2. aa est pair
    3. bb et cc sont égaux
  3. 7 divise 9n9n, et 7 et 9 sont premiers entre eux. Quel est le plus petit entier n>0n > 0 possible ?

Découvrir

L'équation 3x+6y=13x + 6y = 1 a-t-elle des solutions entières ?

  1. Non
  2. Oui

L'idée clé

ax+by=cax + by = c a des solutions si et seulement si PGCD(a;b)\mathrm{PGCD}(a ; b) divise cc.

On trouve une solution particulière (x0;y0)(x_0 ; y_0), puis on utilise Gauss. Si aa et bb sont premiers entre eux, les solutions sont x=x0+bkx = x_0 + bk, y=y0−aky = y_0 - ak, k∈Zk \in \mathbb{Z}.

Exemple corrigé

Résous 3x+5y=13x + 5y = 1.

(x0;y0)=(2;−1)(x_0 ; y_0) = (2 ; -1)
Solution particulière.
3(x−2)=5(−1−y)3(x - 2) = 5(-1 - y)
On soustrait.
x=2+5kx = 2 + 5k et y=−1−3ky = -1 - 3k
Gauss.

À toi, guidé

À toi : pour 2x+3y=12x + 3y = 1, on a la solution (2;−1)(2 ; -1). Combien vaut xx pour k=1k = 1 dans x=2+3kx = 2 + 3k ?

55
2 + 3.

Entraînement ★

  1. Les solutions de 3x+5y=13x + 5y = 1 sont x=2+5kx = 2 + 5k, y=−1−3ky = -1 - 3k. Que vaut xx pour k=2k = 2 ?
  2. Les solutions de 3x+5y=13x + 5y = 1 sont x=2+5kx = 2 + 5k, y=−1−3ky = -1 - 3k. Que vaut xx pour k=24k = 24 ?
  3. Les solutions de 3x+5y=13x + 5y = 1 sont x=2+5kx = 2 + 5k, y=−1−3ky = -1 - 3k. Que vaut xx pour k=1k = 1 ?

Attention !

Entraînement ★★

  1. L'équation 8x+16y=98x + 16y = 9 a-t-elle des solutions entières ?
    1. Non
    2. Oui, une seule
    3. Oui, une infinité
  2. L'équation 4x+8y=54x + 8y = 5 a-t-elle des solutions entières ?
    1. Non
    2. Oui, une seule
    3. Oui, une infinité
  1. Les solutions de 3x+5y=13x + 5y = 1 sont x=2+5kx = 2 + 5k, y=−1−3ky = -1 - 3k. Que vaut yy pour k=2k = 2 ?
  1. Une équation ax+by=cax + by = c a une solution entière. Combien en a-t-elle en tout ?
    1. Une infinité
    2. Une seule
    3. Deux

Bilan

Trois questions pour vérifier que c'est acquis.

  1. Les solutions de 3x+5y=13x + 5y = 1 sont x=2+5kx = 2 + 5k, y=−1−3ky = -1 - 3k. Que vaut xx pour k=2k = 2 ?
  2. Les solutions de 3x+5y=13x + 5y = 1 sont x=2+5kx = 2 + 5k, y=−1−3ky = -1 - 3k. Que vaut xx pour k=24k = 24 ?
  3. Les solutions de 3x+5y=13x + 5y = 1 sont x=2+5kx = 2 + 5k, y=−1−3ky = -1 - 3k. Que vaut xx pour k=1k = 1 ?

Fiche résumé

Équations diophantiennes

  • Existence : PGCD(a;b)∣c\mathrm{PGCD}(a ; b) \mid c.
  • Solution particulière, puis Gauss.

Attention : il y a une infinité de solutions.

Il reste une étape facultative : un défi. Tente-le, ou termine la leçon maintenant.

Défi ★★★

  1. Combien de couples d'entiers positifs ou nuls (x;y)(x ; y) vérifient 3x+5y=753x + 5y = 75 ?

6. Compter les diviseurs

Découvrir

12=22×312 = 2^2 \times 3 a pour diviseurs 1, 2, 3, 4, 6, 12 : six diviseurs. Peut-on trouver ce nombre sans les écrire ?

  1. Oui : (2+1)(1+1)=6(2 + 1)(1 + 1) = 6
  2. Oui : 2+1=32 + 1 = 3

L'idée clé

Compter les diviseurs.

Si n=p1a1×p2a2×⋯×pkakn = p_1^{a_1} \times p_2^{a_2} \times \dots \times p_k^{a_k} (décomposition en facteurs premiers), le nombre de diviseurs positifs de nn est

(a1+1)(a2+1)⋯(ak+1)(a_1 + 1)(a_2 + 1) \cdots (a_k + 1).

Exemple corrigé

Nombre de diviseurs de 360=23×32×5360 = 2^3 \times 3^2 \times 5.

(3+1)(2+1)(1+1)(3 + 1)(2 + 1)(1 + 1)
Exposants 3, 2, 1.
=24= 24 diviseurs
On multiplie.

À toi, guidé

À toi : nombre de diviseurs de 252^5 ?

66
5+15 + 1.

Entraînement ★

  1. Combien de diviseurs positifs a 26×322^{ 6 } \times 3^{ 2 } ?
  2. Combien de diviseurs positifs a 24×332^{ 4 } \times 3^{ 3 } ?
  3. Combien de diviseurs positifs a 23×352^{ 3 } \times 3^{ 5 } ?

Entraînement ★★

  1. Combien de diviseurs positifs a n=25×52×72n = 2^{ 5 } \times 5^{ 2 } \times 7^{ 2 } ?
  2. Combien de diviseurs positifs a n=22×52×71n = 2^{ 2 } \times 5^{ 2 } \times 7^{ 1 } ?

Bilan

Deux questions pour vérifier.

  1. Combien de diviseurs positifs a 26×322^{ 6 } \times 3^{ 2 } ?
  2. Combien de diviseurs positifs a 24×332^{ 4 } \times 3^{ 3 } ?

Fiche résumé

Nombre de diviseurs

  • (a1+1)(a2+1)⋯(a_1 + 1)(a_2 + 1) \cdots
  • Un carré parfait a un nombre impair de diviseurs.

On a choisi 360 degrés pour le tour complet en partie parce que 360 a beaucoup de diviseurs.

7. Histoire de l'arithmétique : Euclide, Fermat et Gauss

Découvrir

Le livre VII des Éléments d'Euclide (vers 300 av. J.-C.) contient une méthode pour trouver le PGCD de deux nombres. Laquelle ?

  1. Les divisions successives : l'algorithme d'Euclide
  2. Écrire tous les diviseurs et comparer

L'idée clé

De l'algorithme d'Euclide aux congruences.

150010001500vers 300 av. J.-C.Euclidevers 300 av. J.-C.Euclide
  1. Étape 1150010001500vers 300 av. J.-C.Euclidevers 300 av. J.-C.EuclideEuclide vers 300 av. J.-C.Portrait imaginéAuteur inconnu. Domaine publicVers 300 av. J.-C. : le livre VII des Éléments et l'algorithme d'Euclide.
  2. Étape 2150010001500vers 300 av. J.-C.Euclide1640Fermatvers 300 av. J.-C.Euclide1640FermatPierre de Fermat vers 1607 – 1665Rolland Lefebvre. Domaine public1640 : correspondance de Fermat et Frenicle sur les nombres.
  3. Étape 3150010001500vers 300 av. J.-C.Euclide1640Fermat1801Gaussvers 300 av. J.-C.Euclide1640Fermat1801GaussCarl Friedrich Gauss 1777–1855Gottlieb Biermann / After Christian Albrecht Jensen, 1840. Domaine publicÉté 1801 : Gauss publie les Disquisitiones arithmeticae.

Le livre VII des Éléments d'Euclide est une introduction à la théorie des nombres et contient l'algorithme d'Euclide. Fermat (1601–1665) échange des problèmes de nombres avec Frenicle de Bessy, notamment en 1640. À l'été 1801, Gauss publie les Disquisitiones arithmeticae (« Recherches arithmétiques »), qui fondent la théorie moderne des nombres.

Exemple corrigé

PGCD de 252 et 198 par l'algorithme d'Euclide.

54=1×36+1854 = 1 \times 36 + 18, 36=2×18+036 = 2 \times 18 + 0
252=1×198+54252 = 1 \times 198 + 54, 198=3×54+36198 = 3 \times 54 + 36.
PGCD=18\mathrm{PGCD} = 18
Dernier reste non nul.

Entraînement ★

  1. Quel livre Gauss publie-t-il à l'été 1801 ?
    1. Les Disquisitiones arithmeticae
    2. Les Éléments
    3. La Géométrie
  1. Première étape de l'algorithme d'Euclide : quel est le reste de la division euclidienne de 252 par 15 ?
  2. Première étape de l'algorithme d'Euclide : quel est le reste de la division euclidienne de 122 par 17 ?
  1. Avec la notation de Gauss : x≡2(mod8)x \equiv 2 \pmod{ 8 } et y≡2(mod8)y \equiv 2 \pmod{ 8 }. Quel est le reste de x+yx + y modulo 8 ?

Fiche résumé

L'arithmétique aujourd'hui

  • Cryptographie : les paiements en ligne reposent sur les nombres premiers et les congruences.
  • Codes correcteurs : numéros ISBN, IBAN et cartes bancaires ont une clé de contrôle.
  • Calendriers : les jours de la semaine se calculent modulo 7.

Sources : biographies d'Euclide, de Fermat et de Gauss sur MacTutor (voir « Sources et crédits »).