Factorització dels enters
From Wikipedia, the free encyclopedia
En teoria de nombres, la factorització dels enters és el procés de trobar quins nombres primers es multipliquen per fer un nombre compost, doncs els divisors no trivials (diferent de l'1 i del mateix nombre).[1] Aquests nombres primers és diuen «factors».
Si es té un algorisme per factoritzar qualsevol enter llavors el mateix algorisme serveix per factoritzar-lo en factors primers a base d'aplicar el mateix algorisme repetidament fins que tots els factors siguin nombres primers. Aquesta factorització es coneix com a descomposició en producte de factors primers o factorització en nombres primers i és el procés de resolució del problema següent: sigui un enter estrictament positiu, com escriure'l en forma d'un producte de nombres primers; per exemple, si el nombre donat és 45, la factorització en nombres primers és 3² × 5. La factorització entera és única, llevat de l'ordre dels factors i la multiplicitat de les unitats positiva i negativa (1 i -1).
Per definició, un nombre primer no es pot descompondre. També es pot dir que és el resultat de la seva pròpia descomposició. La factorització és sempre única, d'acord amb el teorema fonamental de l'aritmètica. Ja el 1801, el matemàtic Carl Friedrich Gauss a les seves Disquisicions artimètiques el va assenyalar com un dels grans problemes de l'aritmètica.[2] Té una importància considerable en criptografia, en teoria de la complexitat i per als ordinadors quàntics.
- Exemples
-
- 11 = 11
- 25 = 5 × 5 = 5²
- 125 = 5 × 5 × 5 = 53
- 360 = 2 × 2 × 2 × 3 × 3 × 5 = 23 × 3² × 5
- 1.001 = 7 × 11 × 13
- 1.010.021 = 17 × 19 × 53 × 59
- 11 = 11