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.
Conséquences
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.
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|.
Pour tous entiers a et b non tous nuls, a∧b=|a|∧|b|.
➽ 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 \;\;\; \\ $ |
$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 rn+1 et par suite rn 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$
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
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.
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
☛ 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.
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.
Déterminer a∧b , suivant les valeurs de n.
Cliquer ici pour voir les solutions
☛ 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.
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
☛ 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)$
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
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.
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éfinitionMontrons 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.$
$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
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.
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
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)
2) Déterminer tous les couples (x,y) d'entiers tels que $143x+100y=1$ (E)
Cliquer ici pour voir les solutions
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.
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∈ℤ}
Autres articles
Cryptographie
Probabilité conditionnelle
Identité de Bezout
Divisibilité dans ℤ
Le triangle de Pascal
Les nombres de Mersenne
Théorie des situations
Evaluation du travail de l'élève
Les théories de l'apprentissage
Eléments de logique mathématiques
Fractales (Partie I) - Arbres fractales
Fractales (Partie II) - Plantes fractales
Fractales (Partie III) - Courbes et formes fractales
Fractales (Partie IV) - Ensemble de Mandelbrot
MathJax - Beautiful math in all browsers
Dénombrement
Droite dans le plan
Probabilité conditionnelle
Identité de Bezout
Divisibilité dans ℤ
Le triangle de Pascal
Les nombres de Mersenne
Théorie des situations
Evaluation du travail de l'élève
Les théories de l'apprentissage
Eléments de logique mathématiques
Fractales (Partie I) - Arbres fractales
Fractales (Partie II) - Plantes fractales
Fractales (Partie III) - Courbes et formes fractales
Fractales (Partie IV) - Ensemble de Mandelbrot
MathJax - Beautiful math in all browsers
Dénombrement
Droite dans le plan
Commentaires
Malek Bellasfar05-05-2021 21:08:11
on veut plus
Connectez vous pour ajouter des commentaires.