Nombres premiers et congruences

Reconnaître un nombre premier

Un entier supérieur ou égal à 2 est premier s’il a exactement deux diviseurs positifs : 1 et lui-même. Pour tester n, il suffit de chercher un diviseur premier inférieur ou égal à √n.

Le crible d’Ératosthène élimine les multiples des premiers successifs. Tout entier au moins égal à 2 possède une décomposition en facteurs premiers unique à l’ordre près.

860 = 2² × 5 × 43

Lire une congruence

a ≡ b [n] signifie que a et b ont le même reste dans la division par n. Cela équivaut à dire que n divise a − b.

25 ≡ 4 [7], car 25 − 4 = 3 × 7
18 ≡ 3 [5], car 18 = 3 × 5 + 3

Calculer avec les restes

• On peut additionner, soustraire et multiplier des congruences de même module.
• On peut élever à une puissance entière positive ou nulle.
• Réduire les nombres modulo n à chaque étape simplifie les calculs.
• La division n’est pas librement permise dans une congruence.

12 ≡ 2 [5]
12² ≡ 2² ≡ 4 [5]