PGCD, PPCM et ALGORITHME D'EUCLIDE

تعريف

Soient aa et bb deux entiers relatifs non nuls.

Le Plus Grand Commun Diviseur de aa et bb, est le plus grand des diviseurs positifs communs à aa et bb.

  • Noté:  ab ~a \wedge b~ ou  PGCD(a,b)~\operatorname{PGCD}(a,b)

Le Plus Petit Commun Multiple de aa et bb, est le plus petit des multiples strictement positifs communs à aa et bb.

  • Noté:  ab ~a \vee b~ ou  PPCM(a,b)~\operatorname{PPCM}(a,b)

image/svg+xml Remarque

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

"ab=1a \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 :

  • ab=baa \wedge b = b \wedge a \\[0.2cm]
  • a/bab=aa/b \Leftrightarrow a \wedge b = |a| \\[0.2cm]
  • a(bc)=(ab)ca \wedge (b\wedge c) = (a\wedge b) \wedge c \\[0.2cm]
  • (ca)(cb)=c(ab)(c a)\wedge (c b) =c (a \wedge b ) \\[0.2cm]
  • (d/a et d/b)d/ab(d/a~\text{et}~ d/b) \Rightarrow d/ a\wedge b

Propriétés du PPCM :

  • ab=baa \vee b = b \vee a \\[0.2cm]
  • a/bab=ba/b \Leftrightarrow a \vee b = |b| \\[0.2cm]
  • a(bc)=(ab)ca \vee (b\vee c) = (a\vee b) \vee c \\[0.2cm]
  • (ca)(cb)=c(ab)(c a)\vee (c b) =c (a \vee b ) \\[0.2cm]
  • (a/m et b/m)ab/m(a/m~\text{et}~ b/m) \Rightarrow a\vee b / m \\[0.2cm]
  • (ab)(ab)=ab (a \wedge b) (a \vee b) = |ab|~ (PPCM \operatorname{PPCM}~ et  PGCD~\operatorname{PGCD})

Algorithme D'EUCLIDE :

L'Algorithme d'Euclide est un Algorithme qui permet de déterminer le PGCD\operatorname{PGCD} de deux nombres.

  • Soient aZ a \in \mathbb{Z^*}~  et  bN~b \in \mathbb{N^*} tels que la division euclidienne de aa par bb se traduit par a=bq+r a=bq+r~, avec 0r<b.0 \le r<b.\\ Alors l'ensemble des diviseurs communs à aa et bb est identique à ceux communs à bb et rr, car r=abqr=a-bq
  • C'est à dire:  ab=br~a \wedge b = b \wedge r

تطبيق

Soient xx et yy deux éléments de N\mathbb{N^*}

  • a=9x+4y a=9x+4y~ et  b=2x+y~b=2x+y
  • Montrons que ab=xya \wedge b = x \wedge y

Méthode 1 : "Sans utiliser l'Algorithme d'Euclide"

  • Posons: ab=d a \wedge b =d ~ et  xy=~x \wedge y = \triangle :
  • xy=x \wedge y = \triangle \\[0.2cm] {/x/y{/9x+4y/2x+y{/a/b/ab/d\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]
  • ab=da \wedge b = d \\[0.2cm] {d/ad/b{d/a4bd/2a9b{d/xd/y{d/xd/yd/(xy)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/ d/ \triangle~ et  /d ~\triangle /d~ Alors d=d= \triangle \\ D'où:  ab=xy~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+xab=bx  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+ybx=xy  b=2x+y \Rightarrow b \wedge x = x \wedge y ~ (d'après l'Algorithme d'Euclide)

De 1 et 2 on conclut que:  ab=xy~a \wedge b = x \wedge y

خاصية

Soient aa et bb deux éléments de Z\mathbb{Z^*}

aba \wedge b = d(α,β)Z2 a=dα d \Leftrightarrow \exists (\alpha, \beta) \in \mathbb{Z}^2\quad a=d \alpha~ et  b=dβ ~b=d \beta~ et  αβ=1~\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 aa et bb deux éléments de Z\mathbb{Z}^*

ab=d(u,v)Z2/  d=au+bva \wedge b = d \Rightarrow \exists (u,v) \in \mathbb{Z}^2 /~~ d=au+bv

انتباه

Les coefficients uu et vv de Z\mathbb{Z} tels que: d=au+bvd=au+bv ne sont pas uniques.

d=au+bv \\ d=au+bv n'implique pas que ab=da \wedge b =d

مثال

68=26 \wedge 8=2 avec 2=6.3+8.(2)2=6.3+8.(-2) et 2=6.(1)+8.12=6.(-1)+8.1

مثال

6.5+8.(3)=66.5+8.(-3)=6 n'implique pas que 68=66 \wedge 8=6

نظرية

Théorème de Bezout Soient aa et bb deux éléments de Z\mathbb{Z^*}\\[0.2cm] ab=1(u,v)Zau+bv=1a \wedge b =1 \Leftrightarrow \exists (u,v) \in \mathbb{Z} \quad au+bv=1

برهان

1-ab=1(u,v)Z2au+bv=1a \wedge b =1 \Rightarrow \exists (u,v)\in \mathbb{Z}^2 \quad au+bv=1\\[0.2cm] 2-Supposons que: (u,v)Z2/au+bv=1\exists (u,v) \in \mathbb{Z}^2 / au+bv=1 \\ On pose: ab=da \wedge b =d\\ On a: ab=da \wedge b =d \Rightarrow {d/ad/bd/(au+bv)d/1d=1\left\{ \begin{array}{lcl} d/a\\ d/b \\ \end{array} \Rightarrow d/ (au+bv) \\ \Rightarrow d /1\\ \Rightarrow d=1 \right.\\ D'où ab=1a \wedge b =1

تطبيق

1-Montrer que:  nZ  n(n+1)=1~\forall n \in \mathbb{Z} ~~n \wedge (n+1)=1\\[0.2cm] 2-Montrer que:  nZ  (5n+3)(2n+1)=1~\forall n \in \mathbb{Z} ~~(5n+3) \wedge (2n+1)=1 

Solution:

1-On a: n(1)+(n+1).1=1n(-1) + (n+1).1=1

Donc d'après le théorème de Bezout  on a:

n(n+1)=1n \wedge (n+1) =1

2-On a: 2(5n+3)5(2n+1)=12(5n+3)-5(2n+1)=1

Alors d'après le Théorème de Bezout  (5n+3)(2n+1)=1~(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 aa, bb et cc des éléments de Z\mathbb{Z^*} On a: {a/bcab=1a/c\left\{ \begin{array}{lcl} a /bc \\ a \wedge b =1 \\ \end{array} \right. \Rightarrow a/c

برهان

On a:

ab=1(u,v)Z  au+bv=1cau+cbv=c 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/bc ~ a/b c ~ alors:  kZ  ak=bc~\exists k \in \mathbb{Z}~  a k=b c

en remplaçant bcb c par aka k dans l'équation:  cau+cbv=c~c a u+c b v=c

Nous obtenons:  acu+akv=ca(cu+kv)=c~a c u+a k v=c \Rightarrow a(cu+kv)=c

D'où: a/ca/c

Corollaire du théorème de Gauss

Soient aa, bb et cc des éléments de Z\mathbb{Z^*}.

On a:  {a/cb/cab=1ab/c~ \left\{ \begin{array}{lcl} a/c \\ b/c \\ a \wedge b=1\\ \end{array} \right. \Rightarrow ab/c

خاصية

Soient aa, bb et cc des éléments de Z\mathbb{Z^*}, et mm et nn des éléments de N\mathbb{N^*} On a: \\[0.2cm] 1. {ab=1ac=1abc=1~\left\{ \begin{array}{lcl} a \wedge b =1 \\ a \wedge c =1 \\ \end{array} \right. \Leftrightarrow a \wedge bc =1 \\[0.2cm] 2. ab=1abn=1~a \wedge b =1 \Leftrightarrow a \wedge b^n =1 \\[0.2cm] 3. ab=1anbn=1~a \wedge b=1 \Leftrightarrow a^n \wedge b^n =1

Équation Diophantienne  ax+by=c~ax+by=c

تعريف

Une équation diophantienne est une équation de la forme ax+by=cax+by=c   où les coefficients a,ba,b et cc sont des nombres entiers relatifs et dont les solutions recherchées xx et yy sont également des entiers relatifs.

La résolution des équations diophantiennes

خاصية

Soient aa, bb et cc des entiers relatifs. \\ L'équation ax+by=cax+by=c admet une solution sur Z2\mathbb{Z}^2 si et seulement \\ si (ab)/c(a \wedge b)/c

خاصية

Soient a,ba,b et cc des entiers relatifs tels que : (ab)/c~(a \wedge b)/c

Si le couple (x0;y0)(x_0;y_0) est une solution de l'équation (E):ax+by=c(E):ax+by=c, alors l'ensemble des solutions de l'équation (E)(E) s'écrit sous la forme:

S={(x0+kbab;y0kaab)/  kZ}S= \{(x_0+k\frac{b}{a \wedge b};y_0-k\frac{a}{a\wedge b})/~~k \in \mathbb{Z} \}

تطبيق

  Résoudre dans Z2\mathbb{Z}^2 les équations suivantes: \\[0.2cm] 1-5x+20y=75x+20y=7\\[0.2cm] 2-54x+21y=90654x+21y=906

Solution :

On a  520=5 ~5 \wedge 20= 5~ et puisque 55 ne divise pas 77 alors  S= ~S=\emptyset

Congruence dans Z

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

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