Identité de Bezout
Created by Dhaouadi Nejib 2020
Dans cet article, on designe par entier tout élément de ℤ et par entier naturel tout élément de ℕ
I. PGCD de deux entiers
☛ Théorème et définition
Si a et b sont deux entiers non tous nuls, alors il existe un unique entier naturel d qui vérifie les deux conditions suivantes:
- d divise a et d divise b.
- Si un entier k divise a et b alors il divise d.
L’entier d défini plus haut est noté
a∧b et appelé
le plus grand commun diviseur de a et b.
Conséquences
Pour tous entiers a et b non tous nuls, a∧b>0.
Pour tous entiers a et b non tous nuls, a∧b=|a|∧|b|.
L'égalité a∧b=|a|∧|b| nous permet de généraliser les propriétés du plus grand commun diviseur de deux entiers naturels non nuls à celles du plus grand commun diviseur de deux entiers non nuls.
➽ Propriétés
Soit a et b deux entiers non tous nuls.
- Si b|a alors a∧b=|b|.
- Pour tout entier non nul a, a∧0=|a|.
- Si b ne divise pas a et si r est le reste modulo b de a alors a∧b= b∧r.
- a∧b=b∧a
- Pour tout entier non nul k, ka∧kb=|k|(a∧b).
- (a∧b)∧c=a∧(b∧c)
Exemples✍
Cherchons 1155∧462.
On a 1155=462*2+231 donc 1155∧462=462∧231=231 car 231|462.
Cherchons 196625∧654.
Sur votre calculatrice, en tapant 196625$\boxed{ab╱c}$654 elle affiche 300 425 654 c-à-d $\frac {196625}{654}=300+\frac{425}{654}$ avec 425 et 654 premiers entre eux.
Ainsi on a: 196625=654×300+425 donc 196625∧654=654∧425=1.
Calcul du PGCD: l'algorithme d'Euclide
Soit a et b deux entiers non nul.
Faisons les divisions euclidiennes successives:
| $a=bq_1+r_1 \;\;\; avec \;\;\; r_1<|b|\\
b=r_1q_2+r_2 \;\;\; avec \;\;\; r_2<r_1\\ r_1=r_2q_3+r_3 \;\;\; avec \;\;\; r_3<r_2 \\
r_2=r_3q_4+r_4 \;\;\; avec \;\;\; r_4<r_3 \\
\dots \\
r_{n-2}=r_{n-1}q_n+r_n \;\;\; avec \;\;\; r_n<r_{n-1} \\
r_{n-1}=r_nq_{n+1}+0 \;\;\; \\
$ |
On sait que:
$a∧b=b∧r_1=r_1∧r_2$$=r_2∧r_3=\dots=r_{n-1}∧r_n $
La suite ($r_n$) est une suite d'entiers naturels strictement décroissante et minorée par 0 donc elle est convergente et on admet qu'elle converge vers 0 c-à-d que la suite des restes finie par un reste nul r
n+1 et par suite r
n est le dernier reste non nul et $a∧b=r_{n-1}∧r_n=r_n $ car $r_n|r_{n-1}$
Algorithme d'Euclide
Saisir deux entiers pour trouver leur pgcd à l'aide de l'algorithme d'Euclide
Exercice 1
1) Montrer que pour tout entier n, $\small{(5n^3-n) ∧(n+2)=(n+2)∧38 }$
2) Déterminer l'ensemble des entiers n tels que :$n+2$ divise $5n^3-n$.
3) On pose $d=(5n^3-n) ∧(n+2)$.
Déterminer les valeurs possibles de d.
4) Résoudre dans ℤ l'équation : $(5n^3-n) ∧(n+2)=19$
Cliquer ici pour voir les solutions
1) $\Tiny{5n^3-n = 5n^2(n+2)-10n^2-n \\
=5n^2(n+2)-10n(n+2)+20n-n \\
=5n^2(n+2)-10n(n+2)+19n \\
=5n^2(n+2)-10n(n+2)+19(n+2)-38 \\
=(n+2)(5n^2-10n+19)-38} $
Ainsi on a: $\small{5n^3-n}$$\small{=(n+2)(5n^2-10n+19)-38}$ (*)
∀n∈ℤ, $5n^3-n\neq 0$ ou $n+2\neq 0$
et tout diviseur commun de $5n^3-n$ et $n+2$ est aussi un diviseur commun de $n+2$ et 38, la réciproque est aussi vraie.
Alors l'ensemble des diviseurs communs de $5n^3-n$ et $n+2$ est égal à l'ensemble des diviseurs communs de $n+2$ et 38, ce qui permet de conclure que $(5n^3-n)∧(n+2)$=$(n+2)∧38$
2) D'après l'égalité (*), n+2 divise $5n^3-n$ ⇔ n+2 divise 38 ⇔ n+2∈{-38,-19,-2,-1,1,2,19,38}⇔n∈{-40,-21,-4,-3,-1,0,17,36}
3) D'après 1) d=(n+2)∧38 donc d|38 alors d∈{1,2,19,38}
4) d=19⇔(n+2)∧38=19⇔$\left\{{\begin{aligned}&{n+2=19p}\\&{38=19q}\\&{p∧q=1}\end{aligned}}\right.$⇔$\left\{{\begin{aligned}&{n+2=19p}\\&{q=2}\\&{p∧2=1}\end{aligned}}\right.$⇔$\left\{{\begin{aligned}&{n+2=19p}\\&{p \;entier\; impair}\end{aligned}}\right.$⇔$n=19(2k+1)-2$$=38k+17$ où k∈ℤ
II. Entiers premiers entre eux
☛ Définition
Deux entiers a et b non tous nuls sont dits premiers entre eux, si a∧b = 1.
Exercice 2
Soit n un entier et d un entier naturel non nul.
1. Montrer que si d est un diviseur commun de n+1 et n+9 , alors d divise 8.
2. En déduire que si n est pair alors n+1 et n+9 sont premiers entre eux.
Cliquer ici pour montrer les solutions
1. Pour tout entier n, n+9=(n+1)+8 donc si d est un diviseur commun de n+1 et n+9 alors d divise 8.
2. Si d=(n+1)∧(n+9) alors d divise 8
Si n est pair alors chacun des entiers n+1 et n+9 est impair donc d est impair.
Finalement si n est pair alors d est un diviseur impair de 8 donc d=1 d'où n+1 et n+9 sont premiers entre eux.
☛ Théorème
Soit a et b deux entiers non tous nuls.
Il existe un unique couple d’entiers (a',b') tel que : a=(a∧b)a' , b=(a∧b)b' et a'∧b' = 1.
Démonstration
Posons d=a∧b donc il existe deux entiers a' et b' tels que a=da' et b=db' et on a : d=a∧b=da'∧db'=d(a'∧b') donc a'∧b'=1.
Pour l'unicité, il suffit de remarquer que a=(a∧b)a'=(a∧b)a" ⇒ a'=a" car a∧b≠0 et aussi b=(a∧b)b'=(a∧b)b" ⇒ b'=b".
Exercice 3
Pour tout entier n, on pose a=n-2 et b=3n+1.
Déterminer a∧b , suivant les valeurs de n.
Cliquer ici pour voir les solutions
Pour tout entier n, 3n+1=3(n-2)+7 donc
d=(3n+1)∧(n-2)=(n-2)∧7 alors d=1 ou d=7
- d=7 ⇔7 divise n-2⇔n-2=7k, k∈ℤ⇔n=7k+2, k∈ℤ
- d=1⇔7 ne divise pas n-2⇔n≠7k+2, k∈ℤ ou encore n=7k+r où r∈{0,1,3,4,5,6}
☛ Théorème de Gauss
Soit a, b et c trois entiers non nuls
Si a divise le produit bc avec a∧b=1 alors a divise c.
Démonstration
On a: ac∧bc=|c|(a∧b)=|c|. Or a divise bc donc il existe un entier q tel que bc=qa donc ac∧bc=ac∧qa=|a|(c∧q)=|c| ce qui prouve que a divise c.
Exercice 4
Résoudre dans ℤ2 l'équation $5x-7y=5$
Cliquer ici pour voir les solutions
$5x-7y=5\Longleftrightarrow$ $5(x-1)=7y$
5|7y avec 5∧7=1 donc d'après le théorème de Gauss 5|y c-à-d y=5k où k∈ℤ
En remplaçant dans l'équation on obtient : 5(x-1)=7×5k⇔x-1=7k ou encore x=7k+1
Réciproquement si x=7k+1 et y=5k alors 5(7k+1)-7(5k)=5 ce qui est vrai donc l'ensemble des solutions est {(7k+1,5k), k∈ℤ}
☛ Théorème (Corollaire de Gauss)
Soit p et q deux entiers naturels non nuls et a un entier.
Si $\left\{{\begin{align}&{a\equiv 0\;\;(mod\;p)\;\;\;}\\&{a\equiv 0\;\;(mod\;q)}\\&{p∧q=1}\end{align}}\right.$ alors $a\equiv 0\;\;(mod\;pq)$
Démonstration
$a\equiv 0\;\;(mod\;p)$⇒a=kp et $a\equiv 0\;\;(mod\;q)$⇒a=k'q donc kp=k'q alors q|kp et puisque p∧q=1 donc d'après le théorème de Gauss q|k ou encore k=k"q ce qui donne a=kp=k"qp d'où pq|a c-à-d $a\equiv 0\;\;(mod\;pq)$
Exemple✍
$576\equiv 0\;\;(mod\;9)$ et $576\equiv 0\;\;(mod\;16)$ (car 567=9×64) avec 16∧9=1 donc $576\equiv 0\;\;(mod\;9×16)$ ou encore $576\equiv 0\;\;(mod\;144)$
Exercice 5
Montrer que pour tout entier n, $n(n+1)(n+2) \equiv 0\;\;(mod\;6)$
Cliquer ici pour voir les solutions
Posons $A=n(n+1)(n+2)$ où n est un entier.
n est pair ou n+1 est pair alors A est pair ou encore $A \equiv 0\;\;(mod\;2)$
- Si n=3k, k∈ℤ alors 3|n
- Si n=3k+1 alors n+2=3(k+1) donc 3|(n+2)
- Si n=3k+2 alors n+1=3(k+1) donc 3|(n+1)
Alors l'un des entiers n, n+1 ou n+2 est divisible par 3 donc A est divisible par 3
On a : $A \equiv 0\;\;(mod\;2)$ et $A \equiv 0\;\;(mod\;3)$ et puisque 2∧3=1 alors $A \equiv 0\;\;(mod\;6)$ pour tout entier n.
III. PPCM de deux entiers
☛Théorème et définition
Pour tous entiers a et b non nuls il existe un unique entier m strictement positif qui
vérifie les deux conditions suivantes.
- m est un multiple commun de a et b
- Tout multiple commun de a et b est un multiple de m.
L’entier m ainsi défini est
le plus petit commun multiple de a et b et est noté
a∨b .
Conséquences
- Pour tous entiers a et b non nuls, a∨b=|a|∨|b|
- Pour tous entiers a et b non nuls, (a∧b)×(a∨b)=|ab|
Démonstration
La première conséquence est évidente en effet a∨b>0 par définition
Montrons l'égalité (a∧b)×(a∨b)=|ab|
Posons d=a∧b et m=$\frac {|ab|}{d}$
On sait qu'il existe deux entiers a' et b' tels que a=a'd et b=b'd et a'∧b'=1.
m=$\frac {|a'b'|d^2}{d}$=d|a'b'|=|a||b'|=|b||a'| donc c'est un multiple commun de a et b.
Soit M un multiple commun de a et b, alors M=ap=bq où p et q des entiers donc a'dp=b'dq ou encore a'p=b'q on déduit alors que a' divise b'q or a'∧b'=1 donc d'après le théorème de Gauss a' divise q c-à-d q=a'k où k est un entier
Remplaçons alor q dans l'égalité M=bq on obtient M=ba'k=db'a'k donc |M|=m|k| et par suite M est un multiple de m.
En conclusion m=d|a'b'| est le ppcm de a et b et on a: md=|(da')(db')|=|ab|.
L'égalité a∨b=|a|∨|b| permet d’affirmer que les propriétés du plus petit commun
multiple de deux entiers non nuls sont les mêmes que celles du plus petit commun multiple de deux entiers naturels non nuls.
➽ Propriétés
Soit a, b et c trois entiers non nuls.
- Si b divise a alors : a∨b=|a|.
- Pour tout entier non nul k, ka∨kb=|k|(a∨b)
- a∨b=b∨a
- (a∨b)∨c=a∨(b∨c)
Exercice 6
Résoudre dans ℤ×ℤ les systèmes suivants:
$1)\left\{{\begin{align}&{ab=-1176\;\;\;} \\&{a∨b=84}\end{align}}\right.\;\;\;\;\;\;$ $2)\left\{{\begin{align}&{ab=168\;\;\;}\\&{a∨b=24}\end{align}}\right.$
Cliquer ici pour voir les solutions
Posons d=a∧b et m=a∨b
$1)\left\{{\begin{align}&{ab=-1176\;\;\;}\\&{m=84}\end{align}}\right.$
$\Longleftrightarrow
\left\{{\begin{align}&{84d=1176\;\;\;}\\&{ab=-1176}\end{align}}\right.$
$\Longleftrightarrow \left\{{\begin{align}&{d=14\;\;\;\;\;\;\;\;\;\;}\\&{ab=-1176}\end{align}}\right. $
$\Longleftrightarrow \left\{{\begin{align}&{a=14a'\;\;\;\;\;\;}\\&{b=14b'}\\&{a'∧b'=1}\\&{ab=-1176}\end{align}}\right.$ $\Longleftrightarrow \left\{{
\begin{align}
& {a=14a'\;\;\;}\\
& {b=14b'}\\
& {a'\wedge b'=1}\\
& {a'b'=-6\;\;}
\end{align}
}\right.$
Alors (a',b') ∈{(-6,1);(-3,2);(-2,3);(-1,6);(1,-6);(2,-3);(3,-2);(6,-1)}
Donc l'ensemble des solutions est {(-84,14);(-42,28);(-28,42);(-14,84);(14,-84);(28,-42);(42,-28);(84,-14)}
$2)\left\{{\begin{align}&{ab=168\;\;\;}\\&{m=24}\end{align}}\right.$ $\Longleftrightarrow \left\{{\begin{align}&{ab=168\;\;\;}\\&{24d=168}\end{align}}\right.$
$\Longleftrightarrow \left\{{\begin{align}&{ab=168\;\;\;}\\&{d=7}\end{align}}\right.$
$\Longleftrightarrow \left\{{\begin{align}&{a=7a'\;\;\;}\\&{b=7b'}\\&{a'∧b'=1}\\&{ab=168\;\;\;\;}\end{align}}\right.$
$\Longleftrightarrow \left\{{\begin{align}&{a=7a'\;\;\;}\\&{b=7b'}\\&{a'∧b'=1}\\&{49a'b'=168\;\;\;\;}\end{align}}\right.\Longrightarrow$ 49 divise 168 ce qui est impossible donc ce système n'admet aucune solution.
IV. Inverse modulo n
☛ Théorème
Soit a et b deux entiers naturels non nuls tels que b≥2 et a∧b=1.
Il existe et unique un entier u non nul inferieur à b-1 tel que $au \equiv 1\;\;(mod\;b)$
On dit que u est un inverse de a modulo b.
Démonstration
Soit i et j deux entiers tels que $0≤i<j<b$
$ia\equiv ja\;\;(mod\;b)$ $\Longleftrightarrow a(i-j)\equiv 0\;\;(mod\;b)$ or a∧b=1 donc b divise i-j ce qui est impossible car 0<j-i<b
Donc ia et ja ont nécessairement des restes modulo b
distincts. Par suite, à chaque élément ia de {0,a,2a,...,(b-1)a}, correspond un seul reste de {0,1,...,b-1} ou encore il existe un seul entier u∈{0,1,...,b-1} tel que $au\equiv 1\;\;(mod\;b)$
Il est évident que u non nul car b≥2 donc l'équalité $0\equiv 1\;\;(mod\;b)$ est impossible.
Exemple✍
Résoudre dans ℤ l'équation $3x \equiv 5\;\;(mod\;37)$
On commence par la résolution de l'équation $3x \equiv 1\;\;(mod\;37)$ (*)
D'après le théorème précédent, 3 et 37 sont premiers entre eux donc l'équation (*) admet une seule solution dans {1,...,36}
L'idée la plus simple est de penser à 3×12=36=37-1. Si vous pouvez penser rapidement à 3×25=75=2×37+1 ça sera mieux. Je reprend la première idée, $3\times 12=36\equiv -1\;\;(mod\;37)$ $\Longrightarrow 3\times(-12)\equiv 1\;\;(mod\;37)$ $\Longrightarrow 3\times(-12+37)\equiv 1\;\;(mod\;37)$ ou encore $3\times25\equiv 1\;\;(mod\;37)$
Revenons à la première équation
$3x \equiv 5\;\;(mod\;37)$ $\Longleftrightarrow 25\times 3x \equiv 25\times5\;\;(mod\;37)$ $\Longleftrightarrow x\equiv 125 \equiv 14 \;\;(mod\;37)$ alors l'ensemble des solutions est {37k+14, k∈ℤ}
Exercice 7
Montrer que les entiers 7 et 11 sont inversibles modulo 60 et déterminer leurs inverses.
Cliquer ici pour voir les solutions
- Comme 7 et 11 sont premiers avec 60 alors ils sont inversibles modulo 60
- On a 11×11=121≡1 (mod 60) donc l'inverse modulo 60 de 11 est 11
-
A l'aide de l'algorithme d'Euclide, déterminons les entiers u et v tels que 7u+60v=1
60 = 7 × 8 + 4
7 = 4 × 1 + 3
4 = 3 × 1 + 1
Alors on déduit:
1=4-3
=4-(7-4) ------> car 3=7-4
=2×4-7
=2(60-7×8)-7 ------> car 4=60-7×8
=7×(-17)+2×60
7×(-17)+2×60=1 donc 7×(-17) ≡1 (mod 60) or -17≡43 (mod 60) donc l'inverse modulo 60 de 7 est 43.
Inverse modulo n
Saisir deux nombres a (a∈ℤ) et n (entier naturel non nul) pour déterminer l'inverse de a modulo n.
V. Identité de Bezout
☛ Théorème (Identité de Bezout)
Deux entiers non nuls a et b sont premiers entre eux, si et seulement si, il existe deux entiers u et v tels que au+bv=1
Démonstration
On suppose que a et b sont des entiers naturels non nuls (en effet a∧b=|a|∧|b|)
Si b=1, on peut écrire 0×a+1×b=1
Si b>1, on sait qu'il existe un entier u tel que au≡1 (mod b) c-à-d au-1=kb ou encore au+(-k)b=1 avec k∈ℤ
Réciproquement: Si d est un diviseur commun de a et b alors d divise au+bv donc divise 1 alors d=1 et par suite a∧b=1.
Corollaire
Si a et b sont des entiers non nuls tels que a∧b=d alors il existe deux entiers u et v tels que au+bv=d
Démonstration
d=a∧b alors il existe deux entiers a' et b' tels que a=a'd , b=b'd et a'∧b'=1.
a'∧b'=1 donc d'après l'identité de Bezout il existe deu entiers u et v tels que a'u+b'v=1 et par suite da'u+db'v=d ou encore au+bv=d.
Exercice 8
1) Démontrer que 143 et 100 sont premiers entre eux.
2) Déterminer tous les couples (x,y) d'entiers tels que $143x+100y=1$ (E)
Cliquer ici pour voir les solutions
1) Appliquons l'algorithme d'Euclid
143 = 100 × 1 + 43.
100 = 43 × 2 + 14.
43 = 14 × 3 + 1.
14 = 1 × 14 + 0.
1 est le dernier reste non nul donc 143∧100=1
2) Par des substitutions successives des restes, dans les divisions précédentes, en partant de l'avant dernière égalité on obtient:
1=43-14×3
=43-(100-43×2)×3
=7×43-3×100
=7×(143-100)-3×100
=7×143-10×100
Si on pose x0=7 et y0=-10 alors le couple (x0,y0) est une solution particulière de l'équation (E)
Faisant la différence des deux égalités 143x0+100y0=1 et 143x+100y=1 on obtient 143(x-x0)+100(y-y0)=0 ou encore 143(x-x0)=100(y0-y)
100 divise 143(x-x0) et 143∧100=1 donc 100 divise x-x0 alors x-x0=100k ou encore x=x0+100k avec k∈ℤ
En remplaçant x-x0 dans 143(x-x0)=100(y0-y), on obtient y0-y=143k ou encore y=y0-143k
Réciproquement, tous les couples (x,y) trouvés conviennent.
L'ensemble des solutions dans ℤ×ℤ est {(7+100k,-10-143k); k∈ℤ}
Algorithme d'Euclide (Etendu)
Saisir deux entiers a et b pour trouver les entiers u et v tels que au+bv=a∧b
VI. Exemples d'équations de la forme ax+by=c
☛ Théorème
Soit a, b et c trois entiers et d=a∧b.
L'équation ax+by=c admet des solutions dans
ℤ×ℤ , si et seulement si, d divise c.
Démonstration
S'il existe un couple d'entiers (x,y) tel que ax+by=c et si d=a∧b alors d qui divise a et b divise aussi ax+by donc d divise c.
Réciproquement : si d divis c alors c=dk où k ∈ℤ or d=a∧b donc d'après le corollaire de Bezout il existe un couple (u,v) d'entiers tel que au+bv=d donc a(ku)+b(kv)=dk=c et par suite l'équation ax+by=c admet des solutions.
Exemples✍
L'équation 10x+18y=113 n'admet aucune solution dans ℤ×ℤ car 10∧18=2 ne divise pas 113.
Alors que L'équation 10x+18y=112 admet des solutions dans ℤ×ℤ car 2 divise 112.
10x+18y=112⇔5x+9y=56.
Appliquons l'algorithme d'Euclid pour a=9 et b=5
9=5×1+4
5=4×1+1
4=1×4+0
On a: 1=5-4=5-(9-5)=5×2+9×(-1)
Multiplions les deux membres par 56
5×2+9×(-1)=1⇔5×112+9×(-56)=56 donc (112,-56) est une solution particulière de l'équation.
5x+9y=56⇔5x+9y=5×112+9×(-56)⇔9(y+56)=5(112-x). 9 divise 5(112-x) et 5∧9=1 donc 9 divise 112-x ou encore 112-x=9k , k∈ℤ ce qui donne x=112-9k.
Remplaçons x dans l'égalité 9(y+56)=5(112-x) on trouve y=-56+5k
Réciproquement: les valeurs trouvées x=112-9k et y=-56+5k vérifies bien l'équation 5x+9y=56 en effet 5(112-9k)+9(-56+5k)=560-45k-504+45k=56.
Conclusion: L'ensemble des solutions est {(112-9k,-56+5k);k∈ℤ}
Commentaires