Fiche de mathématiques
> >

Arithmétique dans Z

Partager :

I. Divisibilité

Proposition :

L'ensemble \mathbb{Z} des entiers relatifs muni des lois addition + et multiplication . est un anneau intègre.

Définition :

Soit (a,b) \in \mathbb{Z}^2.
On dit que a divise b et on note a \, / \,b si et seulement s'il existe c \in \mathbb{Z} tel que : b \, = \, ac.



Au lieu de a divise b, on dit aussi : a est un diviseur de b, ou encore b est un multiple de a.

Remarques :
\forall a \in \mathbb{Z} \: : \: a / 0.
\forall a \in \mathbb{Z} \: : \: 0 / a \Leftrightarrow  a = 0.
Proposition :
  1. \forall a \in \mathbb{Z} \: : \: a / a.
  2. \forall (a \, , \,b) \in \mathbb{Z}^2 \: : \: (a/b \text{ et } b/a )  \Leftrightarrow  |a| = |b|.
  3. \forall (a,b,c) \in \mathbb{Z}^3 \: : \: (a/b \text{ et } b/c) \Rightarrow  a/c.
  4. \forall (a,b,c) \in \mathbb{Z}^3 \: : \: a / b  \Rightarrow a/bc.
  5. \forall (a,b,c,d) \in \mathbb{Z}^4 \: : \: (a/b \text{ et } c/d) \Rightarrow  ac/bd.
  6. \forall (a,b,c) \in \mathbb{Z}^3 \: : \: (a/b \text{ et } a/c) \Rightarrow  a/b+c.
  7. \forall (a,b) \in \mathbb{Z}^2 \: , \: \forall n \in \mathbb{N}^* \: : \: a/b  \Rightarrow  a^n / b^n.


Remarque :
La relation / de divisibilité n'est pas une relation d'ordre sur \mathbb{Z}.
Pour a \in \mathbb{Z}, on pose a \mathbb{Z} = \lbrace am / m \in \mathbb{Z} \rbrace et on a : \forall (a,b) \in \mathbb{Z}^2 \: : \: a/b  \Leftrightarrow  b \mathbb{Z}  \subset a \mathbb{Z} et |a| = |b| \Leftrightarrow b \mathbb{Z} = a \mathbb{Z}.
Théorème - Définition : Division Euclidienne

Soit (a,b) \in \mathbb{Z} \times \mathbb{N}^*.
Il existe alors un couple unique (q,r) \in \mathbb{Z}^2 tel que : (a = bq + r \text{ et } 0 \leq r < b ).
On dit que q (resp. r ) est le quotient (resp. reste ) de la division euclidienne de a par b.



II. Plus grand commun diviseur (pgcd) - Plus petit commun multiple (ppcm)

1. Généralités

Proposition - Définition :

Soient n \in \mathbb{N}^*, (x_1 , \cdots , x_n) \in (\mathbb{Z}^*)^n.
  • L'ensemble des diviseurs communs à x_1, \cdots , x_n est fini et admet un plus grand élément (pour l'ordre \leq) appelé plus grand commun diviseur de x_1, \cdots , x_n noté \text{pgcd} (x_1 , \cdots , x_n ) \text{ ou } \text{pgcd}((x_i)_{1 \leq i \leq n }).
  • L'ensemble des éléments de \mathbb{N}^* multiples communs de x_1, \cdots , x_n admet un plus petit élément (pour l'ordre \leq) appelé plus petit commun multiple de x_1, \cdots , x_n et noté \text{ppcm}( x_1 , \cdots , x_n ) \text{ ou } \text{ppcm}((x_i)_{1 \leq i \leq n }).

Notation :
Pour (a,b) \in ( \mathbb{Z}^*)^n on note : a \vee b = \text{ppcm}(a,b) \text{ et } a \wedge b = \text{pgcd}(a,b).

Exemples :
1. \text{pgcd}(12 \: , \: 18 \: , \: 24) = 6.
2. \text{ppcm}(10 \: , \: 16 \: , \: 20) = 80.

Remarque :
\forall ( x_1 , \cdots x_n ) \in (\mathbb{Z}^*)^n :
1. \text{pgcd}(x_1 , \cdots , x_n ) = \text{pgcd}(|x_1| , \cdots , |x_n| )
2. \text{ppcm}( x_1 , \cdots , x_n ) =  \text{ppcm}(|x_1| , \cdots , |x_n| )
Proposition

Soient n \in \mathbb{N}^* \: , \: (x_1 , \cdots , x_n) \in (\mathbb{Z}^*)^n \: , \: \rho = \text{pgcd}(x_1 , \cdots , x_n ) \: , \: \mu = \text{ppcm}( x_1 , \cdots , x_n ) \: , \: (a \, , \, b) \in (\mathbb{Z}^*)^n.
  1. \rho \mathbb{Z}  = \displaystyle \sum_{k=1}^n x_k \mathbb{Z} et \mu \mathbb{Z} = \displaystyle \cap_{k=1}^n x_k \mathbb{Z}.
  2. ( \forall k \in \lbrace 1, \cdots , n \rbrace  \: , \: a/x_k ) \Longleftrightarrow a/\rho.
  3. ( \forall k \in \lbrace 1, \cdots , n \rbrace  \: , \: x_k/b ) \Longleftrightarrow \mu / b.

Proposition

\forall n \in \mathbb{N}^* \: , \: \forall \lambda \in \mathbb{Z}^* \, , \, \forall (x_1 , \cdots , x_n) \in (\mathbb{Z}^*)^n.
  1. \text{pgcd}(\lambda x_1 , \cdots , \lambda x_n ) = | \lambda | pgcd (x_1 , \cdots , x_n ).
  2. \text{ppcm}(\lambda x_1 , \cdots , \lambda x_n ) = | \lambda | ppcm (x_1 , \cdots , x_n ).



2. Algorithme d'Euclide

Proposition

Soit (a,b) \in \mathbb{N}^2 avec b \not = 0, d'après la division euclidienne de a par b il existe (q,r) \in \mathbb{N}^2 tel que : a=bq+r et 0<r<b .
Dans ce cas, on a : a \wedge b = b \wedge r .



L'algorithme :
Soit (a,b) \in \mathbb{N}^2 avec b \not = 0 tel que a \geq b.
Construisons un algorithme permettant de calculer a \wedge b.
  • Si b/a alors : a \wedge b = b.
  • Si b \not \backslash a. Par division enclidienne de a par b, il existe (q_1 , r_1 ) \in \mathbb{N}^2 avec r_1 \not = 0 tel que : a=bq_1+r_1 et 0<r_1<b. Alors : a \wedge b = b \wedge r_1.
1. Si r_1 / b alors : a \wedge b = b \wedge r_1 = r_1.
2. Si r_1 \not \backslash b alors on réitère.
Ainsi, on construit les couples (q_1,r_1) \: , \: (q_2,r_2) \: , \: \cdots tels que :
a = bq_1+r_1 \: , \: 0 < r_1 < b  \\ b = r_1q_2 + r_2 \: , \: 0 < r_2 < r_1 \\ \vdots
Comme b > r_1 > r_2 > \cdots et que b , r_1 , r_2 , \cdots sont non nuls, le procédé s'arrête au bout d'un nombre fini d'étapes. Il existe donc k \in \mathbb{N}^* \: , \: (q_1 , r_1) \: , \: \cdots \: , \: (q_k, r_k ) dans \mathbb{N} \times \mathbb{N}^* tels que :
a = bq_1 + r_1 \text{ et } 0 < r_1 < b \\ b = r_1q_2 + r_2 \text{ et } 0 < r_2 < r_1 \\ \vdots \\ r_{k-2} = r_{k-1} q_k +r_k \text{ et } 0 <r_k < r_{k-1} \\ r_k / r_{k-1}
On a alors : a \wedge b = b \wedge r_1 = r_1 \wedge r_2 = \cdots = r_{k-1} \wedge r_k = r_k.
Le \text{pgcd} de a et b est le denier reste non nul dans la succession des diviseurs euclidiennes de a par b .

Exemples :
a = 2005 \text{ et } b = -2006.
a \wedge b = |a| \wedge |b| = 2005 \wedge 2006
2006 = 1 × 2005 + 1
2005 = 2005 × 1 + 0
Alors : 2005 \wedge 2006 = 1

a = 1998 \text{ et } b = 2006.
2006 = 1 × 1998 + 8
1998 = 249 × 8 + 6
8 = 1 × 6 + 2
6 = 3 × 2 + 0
Alors : 2006 \wedge 1998 = 2.

III. Nombres Premiers entre eux

Définition :

Soient n_1 , \cdots , n_p \in \mathbb{Z}^* \: (p \geq 2 ).
On dit que n_1 , \cdots , n_p sont premiers entre eux si \text{pgcd}(n_1, \cdots , n_p ) = 1.

Remarque :
n_1 , \cdots , n_p \in \mathbb{Z}^* \: (p \geq 2 ) sont dits premiers entre eux deux à deux si : n_i \wedge n_j = 1 \hspace{10pt} \forall i,j \in \lbrace 1 , \cdots , p \rbrace et i \not = j.

Exemple :
Soient a = 1001 \: , \: b = -101 \text{ et } c = 1903.
\text{pgcd} (a,b,c) = \text{pgcd}(1001 \, , \, -101 \, , \, 1903) = \text{pgcd}(1001 \, , \, -101) \wedge 1903 = 1 \wedge 1903 = 1
Donc a,b,c sont premiers entre eux.
Théorème de Bezout :

Soit (a \, , \, b) \in (\mathbb{Z}^*)^2, alors on a : a \wedge b = 1  \, \Longleftrightarrow \, \exists (u \, , \, v) \in \mathbb{Z}^2 tel que ua + vb = 1.

Théorème de Bezout généralisé :

Soient n \in \mathbb{N}^* , (x_1, \cdots , x_n ) \in (\mathbb{Z}^*)^2.
Pour que x_1, \cdots , x_n soient premiers entre eux dans leur ensemble, il faut et il suffit qu'il existe (u_1 \, , \cdots \, , u_n ) \in \mathbb{Z}^n tel que : \displaystyle \sum_{i=1}^n  x_i u_i  = 1.

Théorème de Gauss :

\forall (a \, , \, b \, , \,c) \in (\mathbb{Z}^*)^3 \: : \: \lbrace a/bc \\ a \wedge b = 1 \. \Longrightarrow \: a/c

Proposition :

Soient n \in \mathbb{N}^* \, , \, a \, , \,x_1 \, , \, \cdots \, , \, x_n \in \mathbb{Z}^*, on a :
( \forall i \in \lbrace 1 \, , \, \cdots \, , \, n \rbrace  \: , \: a \wedge x_i = 1 ) \: \Longleftrightarrow \: a \wedge (\displaystyle \prod_{i=1}^n x_i) = 1.

Proposition :

\forall (a \, , \, b) \in (\mathbb{Z}^*)^2  \, , \, \forall (k \, , \, l) \in (\mathbb{N}^*)^2 \: : \\ a \wedge b = 1 \: \Longleftrightarrow \: a^k \wedge b^l = 1

Corollaire :

\forall (a \, , \,b) \in (\mathbb{Z}^*)^2  \: , \: \forall k \in \mathbb{N}^* \: : \\ a^k \wedge b^k = (a \wedge b ) ^k

Corollaire :

Soient n \in \mathbb{N}^* \text{ et } ( x_1 \, , \, \cdots \, , \, x_n) \in (\mathbb{Z}^*)^n.
Si x_1 \, , \, \cdots \, , \, x_n sont premiers entre eux deux à deux, alors : \text{ppcm}(x_1 \, , \, \cdots \, , \, x_n ) = \| \displaystyle \prod_{i=1}^n x_i \|

Théorème :

Soit (a \, , \, b) \in (\mathbb{Z}^* ) ^2, on a alors : (a \wedge b ) (a \vee b ) = |ab|.



IV. Nombres Premiers

Définition :

Soit p \in \mathbb{Z}.
On dit que p est premier si p \not \in \lbrace -1,1\rbrace et les seuls diviseurs de p dans \mathbb{N} sont 1 et |p|.

Proposition :

Soient n \, , \, p \in \mathbb{Z} avec p premier, alors :
Si p \not \backslash a, alors a \wedge p = 1.

Proposition :

Soit p \in \mathbb{Z}.
p premier \Longleftrightarrow \: (\forall (a \, , \, b) \in \mathbb{Z}^2 \: : \: p/ab \: \Longrightarrow \: (p/a \text{ ou } p/b))

Propositions :

1. Tout nombre entier relatif différent de -1 et 1 admet au moins un diviseur premier.
2. L'ensemble des nombres premiers noté \mathfrak{P} est infini.

Théorème de décomposition en facteurs premiers :

Soit n \in \mathbb{Z}^*, alors il existe (P_1 \, , \, \cdots \, , \, P_m) \in \mathfrak{P}^m \text{ et } \mu_1 \, , \, \cdots \, , \, \mu_m ) \in (\mathbb{N}^*)^m \hspace{10pt} (m \in \mathbb{N}^*) uniques tels que :
n = \epsilon \displaystyle \prod_{i=1}^m P_i ^{\mu_i} avec \epsilon \in \lbrace -1,1\rbrace


Publié le
ceci n'est qu'un extrait
Pour visualiser la totalité des cours vous devez vous inscrire / connecter (GRATUIT)
Inscription Gratuite se connecter
Merci à
Panter Correcteur
pour avoir contribué à l'élaboration de cette fiche


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1348 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !