Un nombre entier est premier si il n’admet que deux diviseurs distincts : 1 et lui-même. Il est composé si il en admet davantage. Par exemple, 17 n’est divisible que par 1 et lui-même : il est donc premier alors que 18 qui admet six diviseurs (1, 2, 3, 6, 9 et 18) est composé. Par contre, rappelons que 0 et 1 ont un statut à part : ils ne sont ni premiers, ni composés.
Affirmer qu’un nombre est premier ne peut pas se faire a priori uniquement en le regardant, c’est-à-dire à partir de son écriture : des calculs conséquents sont même souvent nécessaires pour les grands nombres. Par contre, cela n’est plus vrai en général pour montrer qu’un nombre est composé. Si son écriture habituelle (c’est-à-dire en base 10) posséde certaines propriétés, on peut savoir facilement que le nombre est composé : par exemple si son dernier chiffre est égal à 0, 2, 4, 6 ou 8, le nombre est divisible par 2, si son dernier chiffre est égal à 0 ou 5, il est divisible par 5, si la somme de ses chiffres est divisible par 3, il est divisible par 3, etc. Et il existe d’autres critères de divisibilité basés eux aussi sur l’écriture ... Lire la suite