PGCD,PPCM et ALGORITHME D'EUCLIDE

تعريف

Soient $$a$$ et $$b$$ deux entiers relatifs non nuls. $$\textbf{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 PGCD($$a,b)$$

$$\textbf{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 PPCM($$a,b)$$

image/svg+xml Remarque

On dit que $$a$$ et $$b$$ sont premiers entre eux, si leur 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)

Propriétés du PGCD et PPCM

Propriétés du PGCD :

  • 1-$$a \wedge b = b \wedge a$$
  • 2-$$a/b \Leftrightarrow a \wedge b = |a|$$
  • 3-$$a \wedge (b\wedge c) = (a\wedge b) \wedge c$$
  • 4-$$(c a)\wedge (c b) =c (a \wedge b )$$
  • 5-$$(d/a~et~ d/b) \Rightarrow d/ a\wedge b $$

Propriétés du PPCM :

  • 1-$$a \vee b = b \vee a$$
  • 2-$$a/b \Leftrightarrow a \vee b = |b|$$
  • 3-$$a \vee (b\vee c) = (a\vee b) \vee c$$
  • 4-$$(c a)\vee (c b) =c (a \vee b )$$
  • 5-$$(a/m~et~ b/m) \Rightarrow a\vee b / m $$
  • 6-$$(a \wedge b) (a \vee b) = |ab|$$ (PPCM et PGCD)

Algorithme D'EUCLIDE :

éL'Algorithme d'Euclide est un Algorithme qui permet de déterminer le 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$$

$$\textbf{Méthode 1}$$ "Sans utiliser l'Algorithme d'Euclide"

  • Posons: $$a \wedge b =d $$ et $$x \wedge y = \triangle$$ :
  • 1-$$x \wedge y = \triangle \\ $$ $$\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]$$
  • 2: $$a \wedge b = d \\ $$ $$\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$$

$$\textbf{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)
  • 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$$

Propriété

Soient $$a$$ et $$b$$ deux éléments de $$\mathbb{Z^*}$$

$$a \wedge b$$ = $$d \Leftrightarrow \exists (\alpha, \beta) \in \mathbb{Z}^2 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$$

انتباه

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

$$\textbf{Solution:}$$ 1-On a: $$n(-1) + (n+1).1=1 \\ $$ Donc d'après le $$\textbf{théorème de Bezout }$$ on a: $$n \wedge (n+1) =1\\[0.2cm]$$ 2-On a: $$2(5n+3)-5(2n+1)=1\\$$ Alors d'après le $$\textbf{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 $$

Propriétés

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

[kezakoo section ="propriete"]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: $$\\[0.2cm] 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$$

$$\textbf{Solution}$$ On a $$5 \wedge 20= 5$$ et puisque $$5$$ ne divise pas $$7$$ alors $$ S=\emptyset $$

Congruence dans Z

لمواصلة هذا الملخص، قم بالتسجيل بالمجان في كيزاكو

النسخة المجانية لكيزاكو:
  • ملخصات الدروس غير محدودة
  • فيديو مجاني في كل درس
  • تمرين مصحح مجاني
  • اختبار تفاعلي
إنشاء حساب مجاني