Le petit théorème de Fermat affirme que si p est un nombre premier (comme 2, 3, 5, 7, 11 ou 5 273) et si a est un entier non divisible par p alors a p–1 – 1 est divisible par p. Pour des petites valeurs de a et de p, le résultat n'est peut-être pas spectaculaire et le théorème ne semble pas si utile. Mais pour des valeurs assez grandes, les calculs deviennent vite inaccessibles et le théorème peut nous sauver la mise.
Les démonstrations de ce théorème sont nombreuses et parfois très originales. Une des plus classiques consiste à considérer la liste des multiples de a suivante : a, 2a, 3a, 4a… (p – 1) a. Notons r1, r2… rp–1 les restes respectifs dans la division euclidienne de ces nombres par p. Aucun de ces restes n'est égal à 0 car aucun des multiples de a de notre liste n'est divisible par p (voir l'encadré sur le théorème de Gauss). En outre, ces restes sont tous différents. En effet, supposons que rk et rk' sont égaux, avec k ≤ k'. On peut alors écrire que k'a – ka, soit (k' – k) a, est un multiple de p. Le même argument que précédemment impose que p divise k' – k, et comme k' – k est un entier naturel strictement ...
Lire la suite