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)$

image/svg+xml Remarque

On dit que $$a$$ et $$b$$ sont premiers entre eux, si leur $\operatorname{PGCD}$ est égale à $$ 1$$

"$$a \wedge b =1$$".

انتباه

Ne pas confondre "Nombres premiers entre eux" et "Nombres premiers" (Dans les prochains chapitres on vas découvrir que signifie t-il: Nombre premier)

Vidéo Les Définitions "Diviseur - PGCD - PPCM - Congruence"
15 min
Voir la vidéo

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$$

Vidéo d/a : d divise a !?
15 min
Voir la vidéo

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$$

انتباه

Les coefficients $$u$$ et $$v$$ de $$\mathbb{Z}$$ tels que: $$d=au+bv$$ ne sont pas uniques.

$$ \\ d=au+bv$$ n'implique pas que $$a \wedge b =d$$

مثال

$$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$$

Vidéo PGCD : Plus grand commun diviseur
15 min
Voir la vidéo

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
Signaler une erreur