Multiplicador simple

En teoría de números , los factores primos ( divisores primos ) de un entero positivo son números primos que dividen ese número por un factor ( sin resto ) [1] . Extraer los factores primos de un entero positivo significa enumerar estos factores primos junto con sus multiplicidades. El proceso de determinación de factores primos se llama factorización de enteros . El teorema fundamental de la aritmética establece que cualquier número natural puede representarse como un solo producto (del orden) de factores primos [2] .

Para abreviar la expresión, los factores primos a menudo se representan como potencias de números primos (multiplicidad). Por ejemplo,

360=2\times 2\times 2\times 3\times 3\times 5=2^{3}\times 3^{2}\times 5

donde los factores 2, 3 y 5 tienen multiplicidad 3, 2 y 1, respectivamente.

Para un factor primo p de n , la multiplicidad de p es el mayor de los exponentes a para los cuales padivide n uniformemente.

Para un entero positivo n , el número de factores primos n y la suma de factores primos n (sin multiplicidad) son ejemplos de funciones aritméticas de n ( funciones aritméticas aditivas [3] ).

Cuadrado completo

El cuadrado de un número tiene la propiedad de que todos sus factores primos tienen multiplicidad par. Por ejemplo, el número 144 (cuadrado 12) tiene factores primos

144=2\times 2\times 2\times 2\times 3\times 3=2^{4}\times 3^{2}.

En una forma más comprensible:

144=2\times 2\times 2\times 2\times 3\times 3=(2\times 2\times 3)\times (2\times 2\times 3)=(2\times 2\times 3)^{2}=(12)^{2}.

Dado que cada factor primo está presente aquí un número par de veces, el número original se puede representar como el cuadrado de algún número. Del mismo modo, el cubo de un número es un número cuyos factores primos son divisibles por tres, y así sucesivamente.

Números coprimos

Los números enteros positivos que no tienen factores primos comunes se llaman coprimos . Se puede decir que dos números enteros a y b son coprimos si su máximo común divisor mcd( a , b ) = 1. Si dos números enteros no tienen sus factores primos, entonces se usa el algoritmo de Euclides para determinar si son coprimos ; el algoritmo se ejecuta en tiempo polinomial sobre el número de dígitos.

El entero 1 es coprimo para cualquier entero positivo, incluido él mismo. En otras palabras, el número 1 no tiene factores primos, es un producto vacío . Esto significa que mcd(1, b ) = 1 para cualquier b ≥ 1.

Aplicaciones criptográficas

La determinación de los factores primos de un número es un ejemplo de un problema que se utiliza a menudo para proporcionar seguridad criptográfica en los sistemas de cifrado [4] . Se supone que este problema requiere un tiempo superpolinomial en el número de dígitos. Esto significa que es relativamente fácil construir un problema que llevaría más tiempo resolver que la edad conocida del universo con el desarrollo actual de las computadoras y con la ayuda de los algoritmos modernos.

Funciones Omega

La función ω ( n ) (omega) es el número de factores primos diferentes n , mientras que la función Ω( n ) (Omega grande) es el número de factores primos n recalculado con multiplicidad [2] . si un

n=\prod_{i=1}^{\omega (n)}p_{i}^{\alpha_{i)),

después

\Omega (n)=\sum _{i=1}^{\omega (n)}\alpha _{i}.

Por ejemplo, 24 = 2 3 × 3 1. Entonces, ω (24) = 2 y Ω(24) = 3 + 1 = 4 .

ω ( n ) para n = 1, 2, 3, … respectivamente 0, 1, 1, 1, 1, 2, 1, 1, 1, … es la secuencia A001221 en OEIS .
Ω( n ) para n = 1, 2, 3, … respectivamente 0, 1, 1, 2, 1, 2, 1, 3, 2, … es la secuencia A001222 en OEIS .

Véase también

Número compuesto
Factorización de enteros : el problema algorítmico de encontrar factores primos de un número dado
Divisibilidad
Tabla de multiplicadores primos
Tamiz de Eratóstenes
Teorema de Erdős-Kac
Fuerza criptográfica

Enlaces

↑ Jensen, Gary R. Aritmética para profesores: con aplicaciones y temas de geometría . — Sociedad Matemática Estadounidense, 2004.
↑ 1 2 Riesel, Hans (1994), Números primos y métodos informáticos para la factorización , Basilea, Suiza: Birkhäuser, ISBN 978-0-8176-3743-9
↑ Melvyn B. Nathanson. Teoría de Números Aditivos: las Bases Clásicas . - Springer-Verlag , 1996. - vol. 234.- (Textos de Posgrado en Matemáticas). — ISBN 0-387-94656-X .
↑ Menezes, Alfredo; van Oorschot, Paul C.; Vanstone, Scott A. Manual de criptografía aplicada (indefinido) . - CRC Press , 1996. - ISBN 0-8493-8523-7 .