Arithmétique

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

Exemples : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29...

L'ensemble des nombres premiers est infini.

Propriété : 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.

Division euclidienne

Soit $a \in \mathbb{N}$ et $b \in {\mathbb{N}}^*$. Il existe un unique couple (q , r) d’entiers naturels vérifiant 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

Soit a et b deux nombres entiers naturels non nuls. Le PGCD de a et de b, noté PGCD(a , b), est le plus grand des diviseurs communs à a et à b.

Définition : Si PGCD(a , b) = 1, les nombres a et b sont dits premiers entre eux.

Méthode de calcul du PGCD : on peut calculer le PGCD de deux nombres en utilisant la décomposition en produit de facteurs premiers de ces deux nombres ou en utilisant l'algorithme d'Euclide.

Soit $(a , b) \in {\mathbb{Z}}^2$ et $n \in{ \mathbb{N}}^*$. $a$ est congrus à $b$ modulo $n$ (noté $a \equiv b$ (mod n) $\Leftrightarrow$ $a - b$ multiple de $n$ $\Leftrightarrow$ $n$ divise $a - b \Leftrightarrow$.

Il existe un entier relatif $k$ tel que $a - b = nk$ $\Leftrightarrow$ $a$ et $b$ ont le même reste par la division euclidienne par n

Opérations sur les congruences

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

- On peut additionner et soustraire membre à membre deux congruences de même module : $x$

$\equiv$ $a$ (mod n) et $y$ $\equiv$ $b$ (mod n) $\Rightarrow$ $x + y$ $\equiv$ $a + b$ (mod n)

- On peut multiplier membre à membre deux congruences de même module : $x$ $\equiv$ $a$ (mod n) et $y$ $\equiv$ $b$ (mod n) $\Rightarrow$ $x \times y$ $\equiv$ $a \equiv b$ (mod n)

- On peut multiplier par l’entier relatif $k$ les deux membres d’une congruence : $x \equiv a$ (mod n) $\Rightarrow$ $kx$ $\equiv$ $ka$ (mod n)

- On peut élever à une puissance $p \in {\mathbb{N}}^*$ les deux membres d’une congruence : $x$ $\equiv$ $a$ (mod n) $\Rightarrow$ $x^p \equiv a^p$ (mod n)