Fiche de mathématiques

Arithmétique dans Z

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 :

$\forall a \in \mathbb{Z} \: : \: a / a$ .
$\forall (a \, , \,b) \in \mathbb{Z}^2 \: : \: (a/b \text{ et } b/a ) \Leftrightarrow |a| = |b|$ .
$\forall (a,b,c) \in \mathbb{Z}^3 \: : \: (a/b \text{ et } b/c) \Rightarrow a/c$ .
$\forall (a,b,c) \in \mathbb{Z}^3 \: : \: a / b \Rightarrow a/bc$ .
$\forall (a,b,c,d) \in \mathbb{Z}^4 \: : \: (a/b \text{ et } c/d) \Rightarrow ac/bd$ .
$\forall (a,b,c) \in \mathbb{Z}^3 \: : \: (a/b \text{ et } a/c) \Rightarrow a/b+c$ .
$\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$ .

$\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}$ .
$( \forall k \in \lbrace 1, \cdots , n \rbrace \: , \: a/x_k ) \Longleftrightarrow a/\rho$ .
$( \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$ .

$\text{pgcd}(\lambda x_1 , \cdots , \lambda x_n ) = | \lambda | pgcd (x_1 , \cdots , x_n )$ .
$\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$

Merci à Panter

pour avoir contribué à l'élaboration de cette fiche

Cette fiche

Télécharger (130 ko)
Imprimer
Réduire / Agrandir
Pour plus d'options, connectez vous !
Forum de maths

arithmétique en post-bac
Plus de 1 019 topics de mathématiques sur "arithmétique" en post-bac sur le forum.