Calculatrice de factorisation en nombres premiers

La factorisation première (décomposition première) exprime un entier positif comme un produit de nombres premiers. Chaque entier > 1 a une factorisation première unique (Théorème Fondamental de l'Arithmétique). Exemple : 360 = 2³ × 3² × 5. Étapes : trouver le plus petit facteur premier, diviser, répéter jusqu'à ce que le quotient soit 1. Algorithme : division par essai avec les nombres premiers jusqu'à √n. Efficace pour les nombres jusqu'à ~10^12 ; les nombres plus grands nécessitent des algorithmes avancés (Pollard rho, number field sieve). La factorisation première est calculatoirement difficile pour très grands nombres — cette difficulté sous-tend la cryptographie RSA.

Cryptographie : RSA et autres systèmes à clé publique reposent sur la difficulté de factoriser les grands nombres. Calcul du PGCD/PPCM : PGCD(a,b) = produit des facteurs premiers communs avec les exposants minimums. PPCM(a,b) = produit de tous les facteurs premiers avec les exposants maximums. Simplification de fractions : diviser le numérateur et le dénominateur par PGCD. Fonction totiente d'Euler : φ(n) = n × ∏(1 - 1/p) pour chaque facteur premier distinct p. Déterminer les carrés parfaits : n est un carré parfait si tous les exposants des facteurs premiers sont pairs. Nombre de diviseurs : (e₁+1)(e₂+1)...(eₖ+1) où eᵢ sont les exposants.

Le Crible d'Ératosthène trouve efficacement tous les nombres premiers jusqu'à N. Algorithme : créer un tableau booléen [2..N], marquer tous true. Pour chaque nombre non marqué p commençant par 2 : marquer tous les multiples de p (p², p²+p, ...) comme composés. Les nombres non marqués restants sont premiers. Temps : O(n log log n), Espace : O(n). Optimisations : commencer le marquage à p² (les multiples plus petits sont déjà marqués), vérifier seulement les nombres impairs après 2. Pour N = 10^6 : ~78 498 nombres premiers. Pour N = 10^9 : nécessite un crible segmenté pour réduire la mémoire. Utilisé dans la programmation compétitive et la recherche en théorie des nombres.

La fonction totiente d'Euler φ(n) compte les entiers de 1 à n qui sont premiers entre eux (ne partagent aucun facteur commun) avec n. Propriétés clés : φ(1) = 1. Pour un nombre premier p : φ(p) = p − 1. Pour une puissance première : φ(p^k) = p^k − p^(k-1). Pour a, b premiers entre eux : φ(a×b) = φ(a)×φ(b) (multiplicative). En général : φ(n) = n × ∏(1 − 1/p) pour chaque facteur premier distinct p divisant n. Exemple : φ(12) = 12 × (1−1/2) × (1−1/3) = 12 × 1/2 × 2/3 = 4. Entiers premiers avec 12 : {1, 5, 7, 11}. Utilisé dans : RSA (théorème d'Euler : a^φ(n) ≡ 1 mod n), théorie des groupes.

Un nombre parfait est égal à la somme de ses diviseurs propres (diviseurs sauf lui-même). Exemples : 6 = 1+2+3. 28 = 1+2+4+7+14. 496. 8128. Seulement 51 nombres parfaits sont connus ; tous les nombres parfaits connus sont pairs. Nombres premiers de Mersenne : n = 2^(p-1) × (2^p - 1) est parfait quand (2^p - 1) est un nombre premier de Mersenne. Concepts connexes : Nombre abondant : σ(n) > 2n (somme de tous les diviseurs > 2×nombre). Nombre déficient : σ(n) < 2n. Nombres amicaux : paire où σ(a) = b+a et σ(b) = a+b. Exemple : 220 et 284.