Arithmétique des entiers 2BAC

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

انتباه

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$