-
-
Maths
Arithmétique des entiers
2ème année bac Sciences Math A Mathématiques Arithmétique des entiers fiche de cours
PGCD, PPCM et ALGORITHME D'EUCLIDE
تعريف
Soient $$a$$ et $$b$$ deux entiers relatifs non nuls.
Le Plus Grand Commun Diviseur de $$a$$ et $$b$$, est le plus grand des diviseurs positifs communs à $a$ et $b$.
- Noté: $$~a \wedge b~$$ ou $~\operatorname{PGCD}(a,b)$
Le Plus Petit Commun Multiple de $$a$$ et $$b$$, est le plus petit des multiples strictement positifs communs à $a$ et $b$.
- Noté: $$~a \vee b~$$ ou $~\operatorname{PPCM}(a,b)$
Remarque
On dit que $$a$$ et $$b$$ sont premiers entre eux, si leur $\operatorname{PGCD}$ est égale à $$ 1$$
"$$a \wedge b =1$$".
Propriétés du PGCD et PPCM
Propriétés du PGCD :
- $$a \wedge b = b \wedge a \\[0.2cm]$$
- $$a/b \Leftrightarrow a \wedge b = |a| \\[0.2cm]$$
- $$a \wedge (b\wedge c) = (a\wedge b) \wedge c \\[0.2cm]$$
- $$(c a)\wedge (c b) =c (a \wedge b ) \\[0.2cm]$$
- $$(d/a~\text{et}~ d/b) \Rightarrow d/ a\wedge b $$
Propriétés du PPCM :
- $$a \vee b = b \vee a \\[0.2cm]$$
- $$a/b \Leftrightarrow a \vee b = |b| \\[0.2cm]$$
- $$a \vee (b\vee c) = (a\vee b) \vee c \\[0.2cm]$$
- $$(c a)\vee (c b) =c (a \vee b ) \\[0.2cm]$$
- $$(a/m~\text{et}~ b/m) \Rightarrow a\vee b / m \\[0.2cm]$$
- $$(a \wedge b) (a \vee b) = |ab|~$$ ($\operatorname{PPCM}~$ et $~\operatorname{PGCD}$)
Algorithme D'EUCLIDE :
L'Algorithme d'Euclide est un Algorithme qui permet de déterminer le $\operatorname{PGCD}$ de deux nombres.
- Soient $a \in \mathbb{Z^*}~$ et $~b \in \mathbb{N^*}$ tels que la division euclidienne de $$a$$ par $$b$$ se traduit par $$a=bq+r~$$, avec $$0 \le r<b.\\$$ Alors l'ensemble des diviseurs communs à $$a$$ et $$b$$ est identique à ceux communs à $$b$$ et $$r$$, car $$r=a-bq$$
- C'est à dire: $$~a \wedge b = b \wedge r$$
تطبيق
Soient $$x$$ et $$y$$ deux éléments de $$\mathbb{N^*}$$
- $$a=9x+4y~$$ et $$~b=2x+y$$
- Montrons que $$a \wedge b = x \wedge y$$
Méthode 1 : "Sans utiliser l'Algorithme d'Euclide"
- Posons: $$a \wedge b =d ~$$ et $$~x \wedge y = \triangle$$ :
- $$x \wedge y = \triangle \\[0.2cm] $$ $$\Rightarrow \left\{ \begin{array}{lcl} \triangle / x \\ \triangle / y \\ \end{array} \right. \Rightarrow \left\{ \begin{array}{lcl} \triangle /9x+4y\\ \triangle /2x+y \\ \end{array} \right.\Rightarrow \left\{ \begin{array}{lcl} \triangle /a\\ \triangle /b \\ \end{array} \right.\Rightarrow \triangle /a \wedge b \Rightarrow \triangle /d \\[0.2cm]$$
- $$a \wedge b = d \\[0.2cm] $$ $$\Rightarrow \left\{ \begin{array}{lcl} d/a \\ d/b \\ \end{array} \right. \Rightarrow \left\{ \begin{array}{lcl} d/a-4b\\ d/2a-9b \\ \end{array} \right.\Rightarrow \left\{ \begin{array}{lcl} d/x\\ d/-y \\ \end{array} \right. \left\{ \begin{array}{lcl} d/x\\ d/y \\ \end{array} \right. \Rightarrow d/(x\wedge y) \Rightarrow d / \triangle \\[0.2cm]$$ Comme: $$d/ \triangle~$$ et $$~\triangle /d~$$ Alors $$d= \triangle \\ $$ D'où: $$~a \wedge b = x \wedge y$$
Méthode 2 : En utilisant l'Algorithme d'EUCLIDE On a:
- 1) $$ a=9x+4y=4(2x+y) +x= 4b+x \Rightarrow a \wedge b = b \wedge x ~$$ (d'après l'Algorithme d'Euclide) $\\[0.2cm]$
- 2) $$ b=2x+y \Rightarrow b \wedge x = x \wedge y ~$$ (d'après l'Algorithme d'Euclide)
De 1 et 2 on conclut que: $$~a \wedge b = x \wedge y$$
خاصية
Soient $$a$$ et $$b$$ deux éléments de $$\mathbb{Z^*}$$
$$a \wedge b$$ = $$d \Leftrightarrow \exists (\alpha, \beta) \in \mathbb{Z}^2\quad a=d \alpha~$$ et $$~b=d \beta~$$ et $$~\alpha \wedge \beta =1$$
Théorème de Bezout
Égalité de Bezout
خاصية
Soient $$a$$ et $$b$$ deux éléments de $$\mathbb{Z}^*$$
$$a \wedge b = d \Rightarrow \exists (u,v) \in \mathbb{Z}^2 /~~ d=au+bv$$
مثال
$$6 \wedge 8=2$$ avec $$2=6.3+8.(-2)$$ et $$2=6.(-1)+8.1$$
مثال
$$6.5+8.(-3)=6$$ n'implique pas que $$6 \wedge 8=6$$
نظرية
Théorème de Bezout Soient $$a$$ et $$b$$ deux éléments de $$\mathbb{Z^*}\\[0.2cm]$$ $$a \wedge b =1 \Leftrightarrow \exists (u,v) \in \mathbb{Z} \quad au+bv=1$$
برهان
1-$$a \wedge b =1 \Rightarrow \exists (u,v)\in \mathbb{Z}^2 \quad au+bv=1\\[0.2cm]$$ 2-Supposons que: $$\exists (u,v) \in \mathbb{Z}^2 / au+bv=1 \\$$ On pose: $$a \wedge b =d\\$$ On a: $$a \wedge b =d \Rightarrow$$ $$\left\{ \begin{array}{lcl} d/a\\ d/b \\ \end{array} \Rightarrow d/ (au+bv) \\ \Rightarrow d /1\\ \Rightarrow d=1 \right.\\$$ D'où $$a \wedge b =1$$
تطبيق
1-Montrer que: $$~\forall n \in \mathbb{Z} ~~n \wedge (n+1)=1\\[0.2cm]$$ 2-Montrer que: $$~\forall n \in \mathbb{Z} ~~(5n+3) \wedge (2n+1)=1$$
Solution:
1-On a: $$n(-1) + (n+1).1=1 $$
Donc d'après le théorème de Bezout on a:
$$n \wedge (n+1) =1$$
2-On a: $$2(5n+3)-5(2n+1)=1$$
Alors d'après le Théorème de Bezout $$~(5n+3) \wedge (2n+1) =1$$
Théorème de Gauss et équation Diophantienne
Théorème de Gauss
نظرية
Soient $$a$$, $$b$$ et $$c$$ des éléments de $$\mathbb{Z^*}$$ On a: $$\left\{ \begin{array}{lcl} a /bc \\ a \wedge b =1 \\ \end{array} \right. \Rightarrow a/c $$
برهان
On a:
$$ a \wedge b=1 \Rightarrow \exists (u,v) \in \mathbb{Z}~~ a u+b v=1 \Rightarrow c a u+c b v=c $$
Puisque: $$~ a/b c ~$$ alors: $$~\exists k \in \mathbb{Z}~ a k=b c $$
en remplaçant $$b c$$ par $$a k$$ dans l'équation: $$~c a u+c b v=c$$
Nous obtenons: $$~a c u+a k v=c \Rightarrow a(cu+kv)=c $$
D'où: $$a/c$$
Corollaire du théorème de Gauss
Soient $$a$$, $$b$$ et $$c$$ des éléments de $$\mathbb{Z^*}$$.
On a: $$~ \left\{ \begin{array}{lcl} a/c \\ b/c \\ a \wedge b=1\\ \end{array} \right. \Rightarrow ab/c $$
خاصية
Soient $$a$$, $$b$$ et $$c$$ des éléments de $$\mathbb{Z^*}$$, et $$m$$ et $$n$$ des éléments de $$\mathbb{N^*}$$ On a: $\\[0.2cm]$ 1.$$~\left\{ \begin{array}{lcl} a \wedge b =1 \\ a \wedge c =1 \\ \end{array} \right. \Leftrightarrow a \wedge bc =1 \\[0.2cm] $$ 2.$$~a \wedge b =1 \Leftrightarrow a \wedge b^n =1 \\[0.2cm]$$ 3.$$~a \wedge b=1 \Leftrightarrow a^n \wedge b^n =1$$
Équation Diophantienne $~ax+by=c$
تعريف
Une équation diophantienne est une équation de la forme $$ax+by=c $$ où les coefficients $$a,b$$ et $$c$$ sont des nombres entiers relatifs et dont les solutions recherchées $$x$$ et $$y$$ sont également des entiers relatifs.
La résolution des équations diophantiennes
خاصية
Soient $$a$$, $$b$$ et $$c$$ des entiers relatifs. $\\$ L'équation $$ax+by=c$$ admet une solution sur $$\mathbb{Z}^2$$ si et seulement $\\$ si $$(a \wedge b)/c$$
خاصية
Soient $$a,b$$ et $$c$$ des entiers relatifs tels que :$$~(a \wedge b)/c $$
Si le couple $$(x_0;y_0)$$ est une solution de l'équation $$(E):ax+by=c$$, alors l'ensemble des solutions de l'équation $$(E)$$ s'écrit sous la forme:
$$S= \{(x_0+k\frac{b}{a \wedge b};y_0-k\frac{a}{a\wedge b})/~~k \in \mathbb{Z} \}$$
تطبيق
Résoudre dans $$\mathbb{Z}^2$$ les équations suivantes: $\\[0.2cm]$ 1-$$5x+20y=7\\[0.2cm]$$ 2-$$54x+21y=906$$
Solution :
On a $$~5 \wedge 20= 5~$$ et puisque $$5$$ ne divise pas $$7$$ alors $$ ~S=\emptyset $$
Congruence dans Z
لمواصلة هذا الملخص، قم بالتسجيل بالمجان في كيزاكو
- ملخصات الدروس غير محدودة
- فيديو مجاني في كل درس
- تمرين مصحح مجاني
- اختبار تفاعلي
Signaler une erreur