Understanding Prime Factorization
What Is Prime Factorization?
Prime factorization expresses a number as a product of prime numbers. By the Fundamental Theorem of Arithmetic, every integer greater than 1 has a unique prime factorization (up to ordering).
How It Works
Start dividing by the smallest prime (2) and continue until the quotient is 1. For example: 360 = 2³ × 3² × 5¹. The algorithm tries each prime in ascending order and counts how many times it divides.
The Fundamental Theorem
Every integer n > 1 can be uniquely expressed as n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ where each pᵢ is prime and each aᵢ ≥ 1. This uniqueness is why prime numbers are the 'building blocks' of all integers.
Why It Matters
Prime factorization is central to number theory and cryptography. RSA encryption relies on the difficulty of factoring large numbers. It's also used to find GCD, LCM, and simplify fractions.
Applications
Cryptography (RSA, Diffie-Hellman), simplifying fractions, finding GCD and LCM, determining if a number is prime, and solving Diophantine equations.
La décomposition en facteurs premiers
Tout entier > 1 se décompose de manière unique en produit de facteurs premiers (théorème fondamental de l'arithmétique). Exemples : 12 = 2²×3, 60 = 2²×3×5, 100 = 2²×5². Pour décomposer : diviser par 2 tant que possible, puis 3, puis 5, puis les nombres premiers suivants. Optimisation : ne tester que jusqu'à √n. Cette décomposition est la base de l'arithmétique et de nombreux algorithmes cryptographiques modernes.
Les nombres premiers
Un nombre premier n'est divisible que par 1 et lui-même. Les 20 premiers : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71. Le 2 est le seul pair. La densité décroît mais est infinie (Euclide). Le plus grand connu (2024) : 2^82.589.933 - 1 (24,8 millions de chiffres). Les nombres de Mersenne (2^p - 1) sont souvent premiers. Les premiers jumeaux (p, p+2 premiers) : on ne sait pas s'ils sont infinis (conjecture des jumeaux).
Factorisation et cryptographie
La sécurité du RSA repose sur la difficulté de factoriser de grands nombres. Un nombre de 2048 bits (617 chiffres) produit de deux grands premiers est impossible à factoriser avec les ordinateurs actuels. Le meilleur algorithme classique (GNFS) factoriserait un nombre de 2048 bits en temps astronomique. L'ordinateur quantique (algorithme de Shor) pourrait théoriquement le faire, menaçant la cryptographie actuelle. La cryptographie post-quantique se prépare à cette éventualité.
Algorithmes de factorisation
Les algorithmes de factorisation : essai de division (simple, O(√n)), crible d'Ératosthène (pour trouver les premiers), Pollard rho (O(n^1/4)), crible quadratique (QS, pour n < 100 chiffres), crible général de corps de nombres (GNFS, le plus rapide pour grands nombres). Record de factorisation : RSA-250 (250 chiffres, 2020) factorisé en 2.700 ans-cœur de calcul. Les nombres de 300+ chiffres restent hors de portée avec les moyens actuels et la technologie classique.
Les nombres premiers et la musique
En musique, les harmoniques correspondent à des fréquences multiples d'un fondamental : f, 2f, 3f, 5f, 7f... Les harmoniques impaires (3, 5, 7...) donnent le timbre. L'accord parfait correspond aux rapports 1:2:3 (octave, quinte). La gamme naturelle utilise les rapports des petits nombres premiers. Les rapports harmoniques lient les nombres premiers à la perception auditive et à la théorie musicale depuis Pythagore et sa découverte des intervalles consonants.
L'hypothèse de Riemann
L'hypothèse de Riemann (1859, non résolue) concerne la distribution des zéros de la fonction zêta : tous les zéros non triviaux auraient une partie réelle de 1/2. Si vraie, elle donne une estimation précise de la distribution des nombres premiers : π(x) ≈ Li(x) + O(√x×ln(x)). C'est l'un des 7 problèmes du millénaire (prix Clay, 1 million $). La vérification numériques des premiers 10.000.000.000.000 zéros confirme l'hypothèse mais ne constitue pas une preuve mathématique formelle.
La conjecture de Goldbach
La conjecture de Goldbach (1742) : tout nombre pair > 2 est la somme de deux nombres premiers. Exemples : 4 = 2+2, 6 = 3+3, 8 = 3+5, 10 = 5+5 = 3+7. Vérifiée numériquement jusqu'à 4×10¹⁸. La conjecture faible (tout impair > 5 est somme de trois premiers) a été prouvée par Helfgott en 2013. La conjecture forte reste ouverte. Le chiffrement des communications dépend indirectement de la difficulté de ces problèmes arithmétiques fondamentaux.
Applications ludiques
La factorisation amuse les mathématiciens : les nombres de Smith (somme des chiffres = somme des chiffres de leurs facteurs), nombres de Friedman (exprimables avec leurs propres chiffres), nombres vampires (produit de deux nombres « crocs » contenant les mêmes chiffres). Les nombres premiers palindromes (13.831) et les repunits (11, 111...111) sont des curiosités arithmétiques. Les mathématiques récréatives utilisent la factorisation comme terrain de jeu et source de conjectures ouvertes.