Arithmétique dans ℕ

Divisibilité dans ℕ

Soit a et b deux entiers naturels, avec b≠0. On dit que b divise a (ou que a est un multiple de b) s'il existe un entier naturel k tel que a = b×k. On note alors b | a.

Nombres pairs et impairs

Un entier naturel n est pair s'il est divisible par 2, c'est-à-dire s'il peut s'écrire n=2k pour un entier k. Il est impair sinon, et s'écrit alors n=2k+1.

Nombres premiers

Un entier naturel p ≥ 2 est un nombre premier s'il n'admet que deux diviseurs distincts : 1 et lui-même. Les premiers nombres premiers sont 2, 3, 5, 7, 11, 13, 17, 19, 23… Le nombre 2 est le seul nombre premier pair.

Décomposition en produit de facteurs premiers

Tout entier naturel n ≥ 2 se décompose de façon unique en un produit de facteurs premiers (théorème fondamental de l'arithmétique). Exemple : 60 = 2² × 3 × 5.

PGCD (plus grand diviseur commun)

Le PGCD de deux entiers naturels a et b (non tous deux nuls) est le plus grand entier qui divise à la fois a et b. Il peut se calculer par l'algorithme d'Euclide, fondé sur la propriété : PGCD(a ; b) = PGCD(b ; r), où r est le reste de la division euclidienne de a par b (méthode itérée jusqu'à obtenir un reste nul).

Nombres premiers entre eux

Deux entiers naturels a et b sont dits premiers entre eux si leur PGCD vaut 1, c'est-à-dire s'ils n'ont aucun diviseur commun autre que 1.