Nombres premiers

Un entier p > 1 est premier s'il admet exactement deux diviseurs positifs : 1 et lui-même. Les nombres premiers : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, … Tout entier n > 1 est soit premier, soit composé (a au moins un facteur premier ≤ √n).

Tout entier n > 1 s'écrit de manière unique (à l'ordre des facteurs près) comme produit de nombres premiers : n = p₁^α₁ × p₂^α₂ × … × pₖ^αₖ Conséquence pour le PGCD et PPCM : GCPD prend le min des exposants, PPCM prend le max. Exemple : 360 = 2³×3²×5 ; 84 = 2²×3×7 → PGCD=2²×3=12 ; PPCM=2³×3²×5×7=2520.

Si p est premier et si PGCD(a,p) = 1 (a non divisible par p), alors : aᵖ⁻¹ ≡ 1 (mod p) Équivalent : aᵖ ≡ a (mod p) pour tout entier a. Application : calculer aⁿ mod p en réduisant n modulo (p−1). Exemple : 2¹⁰⁰ mod 7. p−1=6 ; 100=6×16+4 → 2¹⁰⁰≡2⁴=16≡2 [7].