Arithmétique

On considère ici l’ensemble des entiers relatifs $\mathbb Z$.

Définition :

Soit $\rm a,b\in\mathbb Z$, $\rm a$ est multiple de $\rm b$ s’il existe $\rm k\in\mathbb Z$ tel que $\rm a=kb$. $\rm b$ est appelé diviseur de $\rm a$.

Définition :

Un entier $\rm p\geq 2$ est un nombre premier si ses seuls diviseurs positifs sont $1$ et $\rm p$.

Proposition :
Il existe une infinité de nombres premiers.

Théorème :

Tout entier $\rm n\geq 2$ peut être écrit de façon unique comme produit de facteurs premiers.

Définition : Soit $n\in\mathbb Z$.

La valuation $p$-adique de $n$, notée $v_p(n)$, est l'exposant de $p$ dans la décomposition en produit de facteurs premiers de $n$.

Théorème :

Soit $\rm a\in\mathbb Z$, $\rm b\in\mathbb N^*$. Il existe un unique couple $\rm (q,r)\in \mathbb Z^2$ tel que $\rm a=bq+r$ avec $\rm 0\leq r < b$.
$\rm q$ est appelé lequotien et $\rm r$ lereste de la division euclidienne de $\rm a$ par $\rm b$.

Définition :

Soit $\rm a,b\in\mathbb Z$ deux entiers (non tous les $2$ nuls). Le plus grand commun diviseur de $\rm a$ et $\rm b$ est le plus grand entier qui divise à la fois $\rm a$ et $\rm b$. Il est noté $\rm pgcd(a~ ;b)$.

Définition :

Le plus petit multiple commun de $\rm a$ et $\rm b$ est le plus petit entier positif divisible par $\rm a$ et par $\rm b$. Il est noté $\rm ppcm(a~ ;b)$.

Théorème de Bezout :

Pour tous $\rm a$ et $\rm b$ entiers, il existe deux entiers relatifs $\rm s$ et $\rm t$ tels que $\rm as+bt=pgcd(a,b)$.
$\rm s$ et $\rm t$ sont appelés coefficients de Bezout.

Définition :

On dit que deux entiers $\rm a \geq 1$ et $\rm b \geq 1$ sont premiers entre eux si $\rm pgcd(a,b)=1$.

Corollaire :

Soit $\rm a,b$ deux entiers. $\rm a$ et $\rm b$ sont premiers entre eux s’il existe $\rm s,t\in\mathbb Z$ tel que $\rm as+bt=1$.

Proposition :

Si $\rm a,b$ sont des entiers (non tous les deux nuls), alors $\rm pgcd(a,b)\times ppcm(a,b)=|ab|$.

Propriétés :

• Si $\rm a$ et $\rm b$ sont premiers entre eux et divisent $\rm n$, alors $\rm ab$ divise $\rm n$.
• Si $\rm a$ et $\rm b$ sont premiers à $\rm n$, alors $\rm ab$ est premier à $\rm n$.

Définition : Soient $a,b,n\in\mathbb Z$. $a$ est congru à $b$ modulo $n$ s’il existe $k\in\mathbb Z$ tel que : $a=b+kn$. Cette relation se note : $a \equiv b \quad [n]$.

Propriétés :

• Si $a \equiv b \quad [n]$ et $a’ \equiv b’ \quad [n]$ alors $a+a’ \equiv b+b’ \quad [n]$.
• Si $a \equiv b \quad [n]$ et $a’ \equiv b’ \quad [n]$ alors $aa’ \equiv bb’ \quad [n]$.

« Petit » Théorème de Fermat :

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.