Arithmétique des entiers

PGCD,PPCM et ALGORITHME D'EUCLIDE

انتباه

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

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

انتباه

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

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

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

La résolution des équations diophantiennes

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

Congruence dans Z