← Cours de mathématiques

Chapitre 9 — Théorèmes de Bézout et de Gauss

Maths Expertes · Math@mine · Exercices

Ch8 📖 Cours ✏️ Exercices Ch10

I. PGCD et algorithme d’Euclide

Exercice 1

Calcul de PGCD

  1. Calculer \(\pgcd(180, 126)\) par l’algorithme d’Euclide.
  2. Calculer \(\pgcd(1764, 868)\).
  3. En déduire le PPCM de 1764 et 868.
  4. Simplifier la fraction \(\dfrac{1764}{868}\).
Correction

a. \(180 = 1\times126+54\), \(126=2\times54+18\), \(54=3\times18+0\). \(\pgcd(180,126)=18\).

b. \(1764=2\times868+28\), \(868=31\times28+0\). \(\pgcd(1764,868)=28\).

c. \(\text{ppcm}(1764,868)=\dfrac{1764\times868}{28}=\dfrac{1\,531\,152}{28}=54684\).

d. \(\dfrac{1764}{868}=\dfrac{63}{31}\).

Exercice 2

Entiers premiers entre eux

  1. Montrer que pour tout entier \(n\), les entiers \(n\) et \(n+1\) sont premiers entre eux.
  2. Montrer que \(2n+1\) et \(2n+3\) sont premiers entre eux.
  3. Soit \(d = \pgcd(a, b)\). Montrer que \(\pgcd(a/d,\, b/d) = 1\).
Correction

a. Soit \(d = \pgcd(n, n+1)\). Alors \(d \mid n\) et \(d \mid (n+1)\), donc \(d \mid (n+1)-n = 1\). Donc \(d = 1\).

b. Soit \(d = \pgcd(2n+1, 2n+3)\). Alors \(d \mid (2n+3)-(2n+1) = 2\). Donc \(d \in \{1,2\}\). Mais \(2n+1\) est impair, donc \(d=1\).

c. Posons \(a=da'\), \(b=db'\). Si \(e = \pgcd(a', b')\), alors \(de \mid a\) et \(de \mid b\), donc \(de \le d\), d’où \(e=1\).

II. Théorème de Bézout et coefficients

Exercice 3

Algorithme d’Euclide étendu

Pour chacun des couples suivants, calculer le PGCD par l’algorithme d’Euclide puis trouver des coefficients de Bézout \(u, v\) tels que \(au + bv = \pgcd(a,b)\).

  1. \(a = 56\), \(b = 15\)
  2. \(a = 144\), \(b = 89\) (nombres de Fibonacci consécutifs)
  3. \(a = 357\), \(b = 119\)
Correction

a. Descente : \(56 = 3\times15+11\), \(15=1\times11+4\), \(11=2\times4+3\), \(4=1\times3+1\), \(3=3\times1\). Donc \(\pgcd(56,15)=1\).

Remontée : \(1=4-1\times3=4-(11-2\times4)=3\times4-11=3(15-11)-11=3\times15-4\times11=3\times15-4(56-3\times15)=15\times15-4\times56\).

\(u=-4\), \(v=15\). Vérif : \(-4\times56+15\times15=-224+225=1\). ✓

b. \(144=1\times89+55\), \(89=1\times55+34\), \(55=1\times34+21\), \(34=1\times21+13\), \(21=1\times13+8\), \(13=1\times8+5\), \(8=1\times5+3\), \(5=1\times3+2\), \(3=1\times2+1\). \(\pgcd=1\).

Remontée : en partant de \(1 = 3 - 1\times 2\) puis en remontant tous les restes, on obtient \(1 = 34\times 144 + (-55)\times 89\). Donc \(u=34\), \(v=-55\). Vérif : \(34\times 144 - 55\times 89 = 4896 - 4895 = 1\). ✓ Remarque : pour des Fibonacci consécutifs le PGCD vaut toujours 1.

c. \(357 = 3\times 119 + 0\). Donc \(119\) divise \(357\) et \(\pgcd(357,119)=119\). Une identité de Bézout évidente est \(0\times 357 + 1\times 119 = 119\), soit \(u=0\), \(v=1\).

Exercice 4

Caractérisation des entiers premiers entre eux

  1. Montrer que \(3n+1\) et \(5n+2\) sont premiers entre eux pour tout entier \(n\).
  2. Montrer que si \(\pgcd(a,b)=1\), alors \(\pgcd(a+b, ab)=1\).
  3. Soient \(a, b\) deux entiers premiers entre eux. Montrer que \(\pgcd(a+b, a-b)\) divise 2.
Correction

a. On cherche une combinaison linéaire égale à 1. \(5(3n+1)-3(5n+2)=15n+5-15n-6=-1\). Donc \(5(3n+1)+(-3)(5n+2)=-1\), soit \((-5)(3n+1)+3(5n+2)=1\). Par Bézout, \(\pgcd(3n+1,5n+2)=1\).

b. Soit \(d=\pgcd(a+b,ab)\). Alors \(d\mid(a+b)\) et \(d\mid ab\). Puisque \(d\mid(a+b)\), on a \(d\mid a(a+b)=a^2+ab\) et \(d\mid ab\), donc \(d\mid a^2\). De même \(d\mid b^2\). Comme \(\pgcd(a,b)=1\), il existe \(u,v\) avec \(au+bv=1\). Donc \(a^2u^2+\ldots\) — alternative : si un premier \(p\) divise \(d\), il divise \(a^2\) donc \(p\mid a\), et il divise \(b^2\) donc \(p\mid b\), ce qui contredit \(\pgcd(a,b)=1\). Donc \(d=1\).

c. Soit \(d=\pgcd(a+b,a-b)\). Alors \(d\mid(a+b)\) et \(d\mid(a-b)\), donc \(d\mid(a+b)+(a-b)=2a\) et \(d\mid(a+b)-(a-b)=2b\). Comme \(\pgcd(a,b)=1\), \(\pgcd(2a,2b)=2\), donc \(d\mid 2\).

III. Lemme de Gauss

Exercice 5

Applications du lemme de Gauss

  1. Sachant que \(15 \mid 8n\) et \(\pgcd(8, 15)=1\), que peut-on conclure ?
  2. Montrer que si \(p\) est premier et \(p \mid a^2\), alors \(p \mid a\).
  3. En déduire que \(\sqrt{2}\) est irrationnel.
  4. Montrer que si \(\pgcd(a,b)=1\) et \(a \mid c\) et \(b \mid c\), alors \(ab \mid c\).
Correction

a. \(15\mid8n\) et \(\pgcd(8,15)=1\), donc par Gauss \(15\mid n\).

b. \(p\mid a^2 = a\cdot a\). Comme \(p\) est premier, \(\pgcd(p,a)\in\{1,p\}\). Si \(\pgcd(p,a)=1\), par Gauss \(p\mid a\), ce qui donne \(\pgcd(p,a)=p\) — contradiction. Donc \(\pgcd(p,a)=p\), i.e. \(p\mid a\).

c. Supposons \(\sqrt{2}=p/q\) avec \(\pgcd(p,q)=1\). Alors \(p^2=2q^2\), donc \(2\mid p^2\), donc \(2\mid p\) (par b). Posons \(p=2k\) : \(4k^2=2q^2\), soit \(2k^2=q^2\), donc \(2\mid q^2\), donc \(2\mid q\). Contradiction avec \(\pgcd(p,q)=1\). Donc \(\sqrt{2}\notin\mathbb{Q}\).

d. \(a\mid c\) donne \(c=ak\). Alors \(b\mid c=ak\) et \(\pgcd(a,b)=1\), donc par Gauss \(b\mid k\). Posons \(k=bm\) : \(c=abm\), donc \(ab\mid c\).

IV. Équations diophantiennes

Exercice 6

Équations diophantiennes

Résoudre dans \(\mathbb{Z}\) les équations suivantes.

  1. \(7x + 11y = 1\)
  2. \(14x + 21y = 7\)
  3. \(15x + 35y = 10\)
  4. \(6x + 10y = 9\) — Discuter l’existence.
Correction

a. \(\pgcd(7,11)=1\mid1\). Euclide étendu : \(11=1\times7+4\), \(7=1\times4+3\), \(4=1\times3+1\). Remontée : \(1=4-3=4-(7-4)=2\times4-7=2(11-7)-7=2\times11-3\times7\). Solution particulière : \(x_0=-3\), \(y_0=2\). Solutions générales : \(x=-3+11k\), \(y=2-7k\), \(k\in\mathbb{Z}\).

b. \(\pgcd(14,21)=7\mid7\). On divise par 7 : \(2x+3y=1\). \(2\times2-3\times1=1\), donc \(x_0=2\), \(y_0=-1\). Solutions : \(x=2+3k\), \(y=-1-2k\).

c. \(\pgcd(15,35)=5\mid10\). On divise par 5 : \(3x+7y=2\). Bézout : \(7=2\times3+1\), donc \(1=7-2\times3\), soit \(3\times(-2)+7\times1=1\), puis ×2 : \(3\times(-4)+7\times2=2\). \(x_0=-4\), \(y_0=2\). Solutions : \(x=-4+7k\), \(y=2-3k\).

d. \(\pgcd(6,10)=2\) et \(2\nmid9\). Pas de solution.

Exercice 7

Problème concret — Pièces de monnaie

Une caisse contient uniquement des billets de 7 € et des billets de 11 €. Peut-on obtenir exactement :

  1. 100 € (avec possiblement des billets rendus, i.e. des coefficients négatifs) ?
  2. 1 € ?
  3. Trouver toutes les façons d’obtenir 100 € avec des coefficients positifs uniquement (\(x \ge 0\) et \(y \ge 0\)).
Correction

a et b. \(\pgcd(7,11)=1\) donc toute valeur est atteignable dans \(\mathbb{Z}\).

Pour 1 € : Bézout donne \(7\times8-11\times5=56-55=1\), donc \(x=8, y=-5\) (8 billets de 7 €, rendre 5 billets de 11 €).

Pour 100 € : on multiplie par 100 : \(x_0=800, y_0=-500\). Solutions générales : \(x=800+11k\), \(y=-500-7k\).

c. On cherche \(k\) tel que \(x=800+11k\ge0\) et \(y=-500-7k\ge0\). De \(y\ge0\) : \(k\le-\frac{500}{7}=-71{,}4...\) donc \(k\le-72\). De \(x\ge0\) : \(k\ge-\frac{800}{11}=-72{,}7...\) donc \(k\ge-72\). Donc \(k=-72\) est la seule valeur : \(x=800+11\times(-72)=800-792=8\), \(y=-500-7\times(-72)=-500+504=4\). Solution unique : \(\mathbf{8\times7 + 4\times11 = 56+44=100}\). ✓

V. Équations de congruences

Exercice 8

Équations de congruences

  1. Résoudre \(5x \equiv 3 \pmod{11}\).
  2. Résoudre \(4x \equiv 6 \pmod{10}\).
  3. Résoudre le système \(\begin{cases}x \equiv 1 \pmod{3} \\ x \equiv 2 \pmod{5} \\ x \equiv 3 \pmod{7}\end{cases}\).
Correction

a. \(\pgcd(5,11)=1\), solution unique. \(5\times9=45\equiv1\pmod{11}\), donc \(5^{-1}\equiv9\). \(x\equiv9\times3=27\equiv5\pmod{11}\). Vérif : \(5\times5=25\equiv3\pmod{11}\). ✓

b. \(\pgcd(4,10)=2\) et \(2\mid6\) : 2 solutions. En divisant par 2 : \(2x\equiv3\pmod5\). \(2^{-1}\equiv3\pmod5\). \(x\equiv9\equiv4\pmod5\). Solutions mod 10 : \(x\equiv4\pmod{10}\) et \(x\equiv9\pmod{10}\).

c. Par le TChR (\(\pgcd\) deux à deux = 1, solution unique mod 105). De 1 et 2 : \(x=3k+1\), \(3k\equiv1\pmod5\), \(k\equiv2\pmod5\), \(x=15j+7\). De cette dernière et 3 : \(15j\equiv-4\equiv3\pmod7\), \(15\equiv1\pmod7\), \(j\equiv3\pmod7\). Donc \(x=15(7m+3)+7=105m+52\). Solution : \(\boxed{x\equiv52\pmod{105}}\).

VI. Applications (Fermat, inverse modulaire, RSA)

Exercice 9

Petit théorème de Fermat

  1. Calculer \(2^{100} \pmod{101}\) en utilisant le petit théorème de Fermat (101 est premier).
  2. Calculer \(3^{1000} \pmod{13}\).
  3. Montrer que pour tout entier \(a\), \(a^7 - a\) est divisible par 42.
Correction

a. 101 premier, \(101\nmid2\). Par Fermat : \(2^{100}\equiv1\pmod{101}\).

b. 13 premier, \(13\nmid3\). \(3^{12}\equiv1\pmod{13}\). \(1000=83\times12+4\), donc \(3^{1000}\equiv3^4=81\equiv81-6\times13=81-78=3\pmod{13}\).

c. \(a^7-a=a(a^6-1)=a(a^2-1)(a^4+a^2+1)\). On montre \(42=2\times3\times7\) divise \(a^7-a\) en appliquant Fermat pour \(p=2,3,7\) : \(a^2\equiv a\pmod2\), \(a^3\equiv a\pmod3\), \(a^7\equiv a\pmod7\). Donc \(2\mid a^7-a\), \(3\mid a^7-a\), \(7\mid a^7-a\). Ces trois entiers sont premiers entre eux deux à deux, donc \(42\mid a^7-a\).

Exercice 10

Inverse modulaire et cryptographie RSA (aperçu)

  1. Calculer l’inverse de 13 modulo 100 par l’algorithme d’Euclide étendu.
  2. Résoudre \(13x \equiv 47 \pmod{100}\).
  3. Dans un système RSA : \(p=11\), \(q=13\), \(e=7\). Trouver la clé privée \(d\) (inverse de \(e\) modulo \(\varphi(n)\)).
  4. Chiffrer le message \(m=5\) puis déchiffrer pour vérifier.
Correction

a. Euclide étendu sur (100, 13) : \(100=7\times13+9\), \(13=1\times9+4\), \(9=2\times4+1\). Remontée : \(1=9-2\times4=9-2(13-9)=3\times9-2\times13=3(100-7\times13)-2\times13=3\times100-23\times13\). Donc \(-23\times13\equiv1\pmod{100}\), soit \(13^{-1}\equiv-23\equiv77\pmod{100}\).

b. \(x\equiv77\times47\pmod{100}\). \(77\times47=3619\equiv19\pmod{100}\). Solution : \(x\equiv19\pmod{100}\). Vérif : \(13\times19=247\equiv47\pmod{100}\). ✓

c. \(n=11\times13=143\), \(\varphi(n)=10\times12=120\). Trouver \(d\) tel que \(7d\equiv1\pmod{120}\). Euclide étendu sur (7,120) : \(120=17\times7+1\). Donc \(1=120-17\times7\), soit \(7\times(-17)\equiv1\pmod{120}\), \(d\equiv-17\equiv103\pmod{120}\).

d. Chiffrement : \(c=5^7\pmod{143}\). \(5^2=25\), \(5^4=625=4\times143+53\equiv53\), \(5^7=5^4\times5^2\times5\equiv53\times25\times5=53\times125\). \(53\times125=6625=46\times143+47\equiv47\pmod{143}\). Déchiffrement : \(47^{103}\pmod{143}\) — par Python ou calcul, on retrouve 5. ✓

Maths Expertes — Math@mine