$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.
EN RÉSUMÉ
Nombres premiers
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.
Exemple
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.
EN RÉSUMÉ
PGCD
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.
$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.
EN RÉSUMÉ
Congruences
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]$
EN RÉSUMÉ
Théorème de Bézout et de Gauss
É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$.
EN RÉSUMÉ
Petit théorème de Fermat
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
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.
EN RÉSUMÉ
Caractériser la divisibilité
En partenariat avec
Caractériser la divisibilité: Utiliser une combinaison linéaire - Divisibilité dans Z
En partenariat avec
Déterminer le reste d'une division euclidienne à l'aide de la congruence
