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