Divisibilité, PGCD et fractions irréductibles

Dire que 36 est divisible par 4, c'est dire que la division tombe juste : 36 = 4 × 9, reste zéro. On dit aussi que 4 est un diviseur de 36, ou que 36 est un multiple de 4. Chaque nombre cache ainsi une collection de diviseurs : ceux de 36 sont 1, 2, 3, 4, 6, 9, 12, 18 et 36.

Pour repérer les diviseurs sans poser de division, des critères express existent. Divisible par 2 : le nombre finit par 0, 2, 4, 6 ou 8. Par 5 : il finit par 0 ou 5. Par 3 : la somme de ses chiffres est divisible par 3 (pour 741 : 7 + 4 + 1 = 12, gagné !). Par 9 : la somme de ses chiffres est divisible par 9.

Quand deux nombres ont des diviseurs communs, le plus grand d'entre eux s'appelle le PGCD (plus grand commun diviseur). Pour le trouver, l'algorithme d'Euclide est imbattable : on divise le grand nombre par le petit, puis le diviseur par le reste, et on recommence jusqu'à un reste nul. Le dernier reste non nul est le PGCD. C'est l'un des plus vieux algorithmes du monde, et il tourne encore dans nos ordinateurs !

À quoi sert le PGCD ? À simplifier les fractions d'un seul coup. En divisant le numérateur et le dénominateur de 84/30 par leur PGCD 6, on obtient 14/5 : une fraction irréductible, impossible à simplifier davantage. Une fraction est irréductible exactement quand le PGCD de son numérateur et de son dénominateur vaut 1.