Arithmétique

Divisibilité dans Z

Définition et propriétés générales

Définition

Soit $a$ et $b$ deux entiers relatifs.

S'il existe un entier relatif $k$ tel que $a = kb$ , on dit que $a$ est un multiple de $b$ .
Si de plus $b \neq 0$ , on dit que $b$ est un diviseur de $a$ .
Dans ce cas, on dit également que $a$ est divisible par $b$ ou que $b$ divise $a$ .

Définition

Deux entiers sont premiers entre eux si et seulement si leurs seuls diviseurs communs sont $1$ et $-1$ .

Propriété

Soit $a,b$ et $c$ des entiers relatifs tels que $b \neq 0$ et $c \neq 0$ . Si $c$ divise $b$ et $b$ divise $a$ , alors $c$ divise $a$ .

Propriété

Soit $a,b$ et $c$ des entiers relatifs tels que $c \neq 0$ .

Si $c$ est un diviseur commun à $a$ et $b$ , alors $c$ divise $a+b$ et $a-b$ .
Plus généralement, $c$ divise $ma+nb$ pour tous $m$ et $n$ entiers relatifs.

La division euclidienne

Théorème

Soit $a$ et $b$ deux entiers naturels, $b$ étant non nul. Il existe un unique couple $(q,r)$ d'entiers naturels tels que : $a = bq +r$ avec $0 \leq r < b$ . On dit que $a$ est le dividende, $b$ le diviseur, $q$ le quotient et $r$ le reste dans la division euclidienne de $a$ par $b$ .

Propriété

Dans la division de $a$ par $b$ , il n'y a que $b$ restes possibles : 0, 1, ..., b-1.
divise $a$ si et seulement si le reste dans la division euclidienne de $a$ par $b$ est nul.

Les congruences

Définition

Soit $c$ un entier relatif non nul. Deux entiers relatifs $a$ et $b$ ont même reste dans la division par $c$ si et seulement si $a-b$ est multiple de $c$ .

Dans ce cas, on dit que $a$ et $b$ sont congrus modulo $c$ .

Propriété

Soit $a,a',a''$ et $c$ des entiers relatifs avec $c \neq 0$ . Si $a \equiv a'(c)$ et $a' \equiv a''(c)$ alors $a \equiv a''(c)$ .

Propriété

Soit $a,b,a',b'$ et $c$ des entiers relatifs avec $c \neq 0$ . Si $a \equiv b(c)$ et $a' \equiv b'(c),$ alors :

$a + a' \equiv b + b'(c)$ et $a - a' \equiv b - b'(c)$
$aa' \equiv bb'(c)$
$a^n \equiv b^n(c)$ pour tout $n \in \mathbb{N}^*$

Nombres premiers

Définition et propriétés générales

Définition

On dit qu'un entier naturel $p$ est premier s'il possède exactement deux diviseurs positifs : $1$ et lui-même.

Théorèmed'arrêt

Soit $n$ un entier naturel supérieur ou égal à $2$ . Alors :

$n$ admet au moins un diviseur premier.
Si $n$ n'est pas premier, il admet au moins un diviseur premier $p$ tel que p \leq \sqrt{n}.

Propriété

Soit $n$ un entier naturel supérieur ou égal à $2$ . D'après le théorème des diviseurs premiers, si $n$ n'est divisible par aucun des nombres premiers inférieur ou égaux à sa racine carrée, on peut affirmer qu'il est premier.

Une infinité de nombres premiers

Propriété

Il existe une infinité de nombres premiers.

Décomposition

Théorème de décomposition en facteur premier ou théorèmefondamental de l'arithmétique

Soit $n$ un entier naturel supérieur ou égal à $2$ Alors :

$n$ se décompose en un produit de facteurs premiers.
Cette décomposition est unique à l'ordre des facteurs près.

Théorèmede décomposition

Si $n$ est un entier naturel supérieur ou égal à $2$ se décomposant en produit de facteurs premiers sous la forme

n = p_1^{\alpha_1} p_2^{\alpha_2} ... p_k^{\alpha_k},

alors les diviseurs positifs de $n$ sont les entiers de la forme $p_1^{\beta_1} p_2^{\beta_2} ... p_k^{\beta_k}$ avec $0 \leq \beta_i \leq \alpha_i$ , pour tout $i$ tel que $1 \leq i \leq k$ .

Corollaire

Si l'entier $n \geq 2$ admet $p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k}$ comme décomposition en produit de facteurs premiers, alors il a $(\alpha_1 + 1)(\alpha_2 + 1)...(\alpha_k + 1)$ diviseurs positifs.

PGCD et PPCM

PGCD

Propriété

Soit $D(a,b)$ l'ensemble des diviseurs communs à deux entiers $a$ et $b$ . $D(a,b) = D(a-b,b) = D(a-kb,b)$ pour tout $k \in \mathbb{Z}$ .

Corollaire

Si $0 < b \leq a, D(a,b) = D(r,b),$ où $r$ est le reste de la division euclidienne de $a$ par $b$ .
Si $b$ divise $a, D(a,b) = D(b),$ où $D(b)$ désigne l'ensemble des diviseurs de $b$ .

Définition

Si $a$ et $b$ sont deux entiers relatifs non tous les deux nuls, l'ensemble des diviseurs communs à $a$ et $b$ admet un plus grand élément. On l'appelle Plus Grand Commun Diviseur de $a$ et $b$ et on le note $PGCD(a,b)$ .

Propriété

Soit $a$ et $b$ deux entiers relatifs non tous les deux nuls :

PGCD(a,b) = PGCD(a-b,b) = PGCD(a-kb,b)

pour tout $k \in \mathbb{Z}$ . En particulier :

si $0 < b \leq a, PGCD(a,b) = PGCD(r,b),$ où $r$ est le reste de la division euclidienne de $a$ par $b$ .
si $b$ est un diviseur positif de $a, PGCD(a,b) = b$

Propriété

Soit $a$ et $b$ deux entiers tels que $0 < b \leq a$ . L'algorithme suivant appelé algorithme d'Euclide permet en un nombre fini d'étapes de calculer $PGCD(a,b)$ .

Calculer le reste $r$ dans la division euclidienne de $a$ par $b$ .
Si $r = 0, PGCD(a,b) = b$ .
Si $r \neq 0,$ remplacer $a$ par $b$ , $b$ par $r$ et recommencer à partir de $(1)$ .

Corollaire

Soit $a$ et $b$ deux entiers relatifs non tous les deux nuls. Les diviseurs communs à $a$ et $b$ sont les diviseurs de $PGCD(a,b)$ .

Propriété

Soit $a$ et $b$ deux entiers relatifs non tous les deux nuls. Pour tout $\alpha \in \mathbb{N}^*, PGCD(\alpha a, \alpha b) = \alpha PGCD(a,b)$ .

Corollaire

Soit $a$ et $b$ deux entiers relatifs non tous les deux nuls et $d$ un entier naturel : $d = PGCD(a,b)$ si et seulement si $a = da'$ et $b = db'$ avec $a'$ et $b'$ entiers premiers entre eux.

Propriété

Soit $a$ et $b$ deux entiers supérieurs ou égaux à $2$ .

S'ils n'ont aucun facteur premier commun, $PGCD(a,b) = 1$ .
Sinon, $PGCD(a,b)$ est égal au produit des facteurs premiers communs aux deux nombres, chacun étant affecté du plus petit exposant avec lequel il figure dans leurs deux décompositions.

Théorème de Bézout

Propriété

Soit $a$ et $b$ deux entiers relatifs non tous les deux nuls et $d = PGCD(a,b)$ .

Il existe $u$ et $v$ deux entiers relatifs tels que $au + bv = d$ .
L'ensemble des entiers $au + bv$ ( $u$ et $v$ entiers relatifs) est l'ensemble des multiples de $d$ .

Théorèmede Bezout

Deux entiers relatifs $a$ et $b$ sont premiers entre eux si et seulement si il existe des entiers relatifs $u$ et $v$ tels que $au+bv = 1$ .

Théorème de Gauss

Théorèmede Gauss

Soit $a,b$ et $c$ trois entiers non nuls. Si $a$ divise $bc$ et si $a$ est premier avec $b$ alors $a$ divise $c$ .

Corollaire

Soit $a,b$ et $c$ trois entiers non nuls. Si $b$ et $c$ divisent $a$ et $b$ est premier avec $c$ alors $bc$ divise $a$ .

Petit théorèmede Fermat

Si $p$ est un entier premier et $a$ un entier naturel non divisible par $p$ alors $a^{p-1}-1$ est divisible par $p$ (ou encore $a^{p-1} \equiv 1(p)$ )

Corollaire

Si $p$ est un entier premier et $a$ un entier naturel alors $a^p-a$ est divisible par $p$ (ou encore $a^p \equiv a(p)$ ).

PPCM

Définition

Soit $a$ et $b$ deux entiers relatifs non nuls. L'ensemble des multiples commun strictement positifs de $a$ et $b$ admet un plus petit élément $m$ , noté $m = PPCM(a,b)$ et appelé Plus Petit Commun Multiple de $a$ et $b$ .

Propriété

On obtient le $PPCM$ de deux entiers supérieurs ou égaux à $2$ en effectuant le produit des facteurs premiers figurant dans l'une ou l'autre de leurs décompositions, chacun étant affecté de son exposant s'il n'apparaît que dans l'une des deux décompositions ou du plus grand des deux exposants s'il apparaît dans les deux.

Propriété

Si $a$ et $b$ sont deux entiers naturel non nuls, alors $PGCD(a,b) \times PPCM(a,b) = ab$ .

Corollaire

Si $a$ et $b$ sont deux entiers relatifs non nuls, pour tout $\alpha \in \mathbb{N}^*,$ $PPCM(\alpha a, \alpha b) = \alpha \times PPCM(a,b)$ .

Mots clés à retenir : PGCD, Nombre premier, Gauss, Bézout, PPCM.

Arithmétique

Divisibilité dans Z

Définition et propriétés générales

Définition

Définition

Propriété

Propriété

La division euclidienne

Théorème

Propriété

Les congruences

Définition

Propriété

Propriété

Nombres premiers

Définition et propriétés générales

Définition

Théorèmed'arrêt

Propriété

Une infinité de nombres premiers

Propriété

Décomposition

Théorème de décomposition en facteur premier ou théorèmefondamental de l'arithmétique

Théorèmede décomposition

Corollaire

PGCD et PPCM

PGCD

Propriété

Corollaire

Définition

Propriété

Propriété

Corollaire

Propriété

Corollaire

Propriété

Théorème de Bézout

Propriété

Théorèmede Bezout

Théorème de Gauss

Théorèmede Gauss

Corollaire

Petit théorèmede Fermat

Corollaire

PPCM

Définition

Propriété

Propriété

Corollaire

Jathu

Jathu

ems33

mahadi5

Attre

Classes

Entreprise

Réseaux sociaux