divisibilité

En arithmétique, on dit qu’un entier a est un diviseur de b s’il existe un entier k tel que b = a k. On note couramment a | b et l’on préfère souvent considérer les entiers positifs non nuls pour éviter les ambiguïtés liées aux signes. Les nombres qui s’écrivent sous la forme a k sont appelés multiples de a, et réciproquement, a est un diviseur de b.

La relation de divisibilité est une relation d’ordre partiel sur l’ensemble des entiers positifs: si a | b et b | c alors a | c. Pour les entiers positifs, si a | b et b | a alors a = b (antisymétrie). Cette propriété permet de comparer les nombres par leur ensemble de diviseurs et d’étudier leurs structures arithmétiques.

Tout entier positif peut se décomposer en produit de facteurs premiers; on parle de factorisation en nombres premiers. Un nombre premier p ne peut être décomposé au-delà de lui-même et 1. Un entier n est divisible par p si et seulement si p apparaît dans sa décomposition en facteurs premiers. Le concept conduit aux notions de plus grand commun diviseur gcd(a,b) et de plus petit commun multiple lcm(a,b), qui décrivent les rapports de divisibilité entre plusieurs nombres.

Des tests de divisibilité simples permettent de vérifier rapidement certains cas: 2 si le nombre est pair; 3 si la somme de ses chiffres est multiple de 3; 4 si les deux derniers chiffres forment un múltiple de 4; 5 si le dernier chiffre est 0 ou 5; 11 si la différence entre les sommes des chiffres des positions alternées est multiple de 11. L’algorithme d’Euclide sert aussi à calculer gcd(a,b) et à tester les divisibilités via le reste de la division.