Arithmétique 2

Définition

Soit a et d deux nombres entiers relatifs.

• $d$ est un diviseur de $a \Leftrightarrow$ Il existe un entier relatif $k$ tel que $a = kd$
• $d$ est un diviseur de $a \Leftrightarrow a$ est un multiple de $d$
• $d$ est un diviseur de $a \Leftrightarrow d$ divise $a$ (noté $d / a$)
• $d$ est un diviseur de $a \Leftrightarrow a$ est divisible par $d$

Nombres particuliers

Un nombre entier naturel est dit parfait s'il est égal à la moitié de la somme de ses diviseurs.

Deux nombres entiers naturels sont dits amicaux si chacun d'eux est égal à la somme des diviseurs (autres que lui-même) de l'autre.

Propriété

Pour $a$, $b$ et $c$ trois entiers relatifs, si $a$ divise $b$ et $c$, alors $a$ divise $b + c$, $b - c$ et $bu + cv$ avec $u$ et $v$ des entiers relatifs.

Définition des nombres premiers

Un nombre entier naturel $p$ est un nombre premier si et seulement il admet exactement $2$ diviseurs : $1$ et lui-même.

Les premiers nombres premiers sont $2$, $3$, $5$, $7$, $11$, $13$, $17$, $19$...

Théorème fondamental

Tout nombre entier naturel $n \geq 2$ admet un diviseur premier. Si $n$ n'est pas un nombre premier, il admet au moins un diviseur $d$ premier tel que $d^2 \leq n$.

Propriétés des nombres premiers

• Il existe une infinité de nombres premiers.
• Un nombre entier naturel $n \geq 2$ se décompose de façon unique (à l'ordre des termes près) en un produit de facteurs premiers de la forme : $$n = p_1^{a_1}\times p_2^{a_2}\times \ldots \times p_k^{a_k}$$ où les $p_i$ et $a_i$ ($i = 1$ à $k$) sont des entiers naturels non nuls.

Division euclidienne

Pour $a$ un entier relatif et $b$ un entier naturel non nul, il existe un unique couple $(q, r)$ d'entiers respectivement relatif et naturel qui vérifient :

$a = bq + r$ et $0 \leq r < b$

$q$ est le quotient et $r$ le reste de la division euclidienne de $a$ par $b$.

PGCD de deux nombres

Pour $a$ et $b$ deux entiers relatifs non nuls, le PGCD de $a$ et de $b$ qui est noté $\mathrm{PGCD}(a, b)$, est le plus grand des diviseurs communs à $a$ et à $b$. On peut le calculer avec l'algorithme d'Euclide ou la décomposition en produit de facteurs premiers de $a$ et de $b$.

Algorithme d'Euclide

Si la division euclidienne de $a$ par $b$ ($a$ et $b$ deux entiers naturels) est $a = b \times q + r$ avec $0 \leq r < b$, on a $\mathrm{PGCD}(a; b) = \mathrm{PGCD}(b; r)$.

On détermine le $\mathrm{PGCD}$ de deux nombres à l'aide de divisions euclidiennes successives.

Calcul du $\mathrm{PGCD}$ de $252$ et $144$ :

• $252 = 1 \times 144 + 108$ donc $\mathrm{PGCD}(252; 144) = \mathrm{PGCD}(144; 108)$
• $144 = 1 \times 108 + 36$ donc $\mathrm{PGCD}(144; 108) = \mathrm{PGCD}(108; 36)$
• $108 = 3 \times 36 + 0$ donc $\mathrm{PGCD}(108; 36) = 36$ car $36$ divise $108$

$\mathrm{PGCD}(252; 108) = 36$ qui est le dernier reste non nul.

Nombres premiers entre eux

Deux nombres sont dits premiers entre eux si leur $\mathrm{PGCD}$ est égal à $1$. Pour $a$ et $b$ deux entiers relatifs non nuls, $a$ et $b$ sont premiers entre eux est équivalent à $\displaystyle\frac{a}{b}$ est une fraction irréductible.

Nombres entiers congrus modulo $n$

Soit $a$ et $b$ deux entiers relatifs et $n$ un entier naturel non nul.

Définitions équivalentes de la congruence

$a$ est congru à $b$ modulo $n$ si et seulement si l'une des conditions équivalentes suivantes est vérifiée :

• $a - b$ est un multiple de $n$
• $n$ divise $a - b$
• Il existe un entier relatif $k$ tel que $a - b = nk$

La propriété "$a$ est congru à $b$ modulo $n$" est notée $a \equiv b ~[n]$.

Opérations sur les congruences

Soit $a$, $b$, $x$, $y$, $k$ cinq entiers relatifs et $n$ et $p$ deux entiers naturels non nuls.

Propriétés d'addition et de multiplication

Si $x \equiv a ~[n]$ et $y \equiv b~ [n]$, alors :

• $x + y \equiv a + b~ [n]$
• $x-y \equiv a-b~ [n]$
• $x\times y \equiv a\times b ~[n]$

Propriétés de multiplication par un scalaire et de puissance

Si $x \equiv a ~[n]$, alors :

• $kx \equiv ka ~[n]$
• $x^p \equiv a^p~[n]$

Égalité de Bézout

Pour $a$ et $b$ avec $d = \mathrm{PGCD} (a , b) \Leftrightarrow$ Il existe deux entiers relatifs $u$ et $v$ tels que $au + bv = d$.

Théorème de Bézout

Pour $a$ et $b$ deux entiers relatifs non nuls :

$a$ et $b$ premiers entre eux $\Leftrightarrow$ Il existe deux entiers $u$ et $v$ tels que $au + bv = 1$.

Équation diophantienne

Pour $a$, $b$ et $c$ trois entiers relatifs non nuls et $d = \mathrm{PGCD}(a~ ; ~b)$, on a :

$ax + by = c$ admet des solutions entières $\Leftrightarrow$ $c$ est un multiple de $d$.

Théorème de Gauss

Pour $a$, $b$ et $c$ trois entiers relatifs non nuls, si $a$ divise $bc$, et si $a$ et $b$ sont premiers entre eux, alors $a$ divise $c$.

Corollaire du théorème de Gauss

Pour $a$, $b$ et $c$ trois entiers relatifs non nuls, si $a$ et $b$ divisent $c$, et si $a$ et $b$ sont premiers entre eux, alors $ab$ divise $c$.

Théorème de Fermat

Première formulation

Soit $p$ un nombre premier, et $a$ un nombre entier premier avec $p$. Alors $a^{p-1}$ a pour reste 1 dans la division euclidienne par $p$ (c'est-à-dire $a^{p-1}-1$ est multiple de $p$) :

$$a^{p-1}\equiv 1 \quad [p]$$

Formulation équivalente

Soit $p$ un nombre premier, et $a$ un nombre entier quelconque. Alors $a^{p}\equiv a \quad [p]$, ce qui peut se lire : $a^p-a$ est un multiple de $p$.

Application pratique

$2^3-2$ est un multiple de 3. En effet $2^3-2=8-2=6$ est un multiple de 3.

La réciproque du théorème est fausse.