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

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

Exemple : 

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

Théorème

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

• 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 × q + r$ avec $0 \leq r < b$, on a $\mathrm{PGCD}(a~ ;~ b) = \mathrm{PGCD}(b~ ;~ r)$.

On détermine le $\rm PGCD$ de deux nombres à l’aide de divisions euclidiennes successives.
Exemple : Calcul du $\rm PGCD$ de $252$ et $144$
$252 = 1 \times 144 + 108$ $\rm PGCD(252~ ;~ 144) = PGCD(144~ ; ~108)$
$144 = 1 \times 108 + 36$ $\rm PGCD(144~ ; ~108) = PGCD(108~ ; ~36)$
$108 = 3 \times 36 + 0$ $\rm PGCD(108~ ;~ 36) = 36$ car $36$ divise $108$
$\rm PGCD(252~ ; ~108) = 36$ qui est le dernier reste non nul.

Nombres premiers entre eux

Deux nombres sont dits premiers entre eux si leur $\rm 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.

• $a$ est congru à $b$ modulo $n \Leftrightarrow a - b$ multiple de $n$
• $a$ est congru à $b$ modulo $n \Leftrightarrow n$ divise $a - b$
• $a$ est congru à $b$ modulo $n \Leftrightarrow$ 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.

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

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

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

De façon é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$.

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

Attention : la réciproque du théorème est fausse.