6 votos

Descomposición de un número entero en números primos elevadas a diferentes potencias

Puede escribirse el número $711000000$ $79^1 \times 2^6 \times 3^2 \times 5^6$. ¿Cómo se encuentran estos números?

Supongo que es la pregunta más general - dado $n \in \mathbb Z $, ¿cómo puede usted 'descomponer' lo en el producto de números primos elevada a diferentes potencias?

4voto

Evan Trimboli Puntos 15857

Se encuentran invirtiendo el proceso que se utilizó para venir para arriba con el número en el primer lugar: se divide a la inversa de la multiplicación. Es de suponer que usted eligió estos primos y las potencias de los números primos y los multiplicó para obtener este número. Así que usted acaba de dividir los números primos o potencias de números primos.

Por supuesto, en algunos casos esto es más fácil de decir que de hacer. Si usted elige dos números primos suficientemente grande, puede multiplicar fácilmente suficiente, pero para alguien más para dividir los dos números primos puede tomar demasiado tiempo para ser práctico (un concepto de gran uso práctico en la criptografía).

La mayoría de las respuestas hasta el momento de mencionar a juicio de la división, un humilde y sencillo método que funciona muy bien cuando los factores primos son en su mayoría pequeñas y consecutivos. Esto es importante para recordar: si $n = p_1 p_2 \ldots p_{\Omega(n)}$ es un número compuesto, tales que $p_1 \leq p_2 \leq \ldots \leq p_{\Omega(n)}$ ($\Omega(n)$ es una función que cuenta cómo muchos factores primos $n$), a continuación,$p_1 \leq \sqrt{n}$. Si usted ha tratado de dividir a $n$ por cada primer hasta el $\sqrt{n}$ y no se encontró el primer factor, a continuación, $n$ es de por sí privilegiada.

Como un par de las respuestas anteriores han sugerido, usted no tiene que ir a través de los números primos por debajo de $\sqrt{n}$ en orden. En el ejemplo de 711000000 podría tener más sentido para dividir a cabo el 2 y 5 de la primera y, a continuación, 3. Pero asegúrese de mantener un seguimiento de cómo a menudo se divide por cada uno de los prime: 711000000 dividido por 2 es 355500000, y que dividido por 2 es 177750000, entonces 88875000, 44437500, 22218750, 11109375 (seis divisiones por 2, por lo tanto el primer exponente 6 $2^6 \times 3^2 \times 5^6 \times 79$. En este punto prefiero dividir por 5 que por 3. Yada, yada, yada, yada, yada, 395 dividido por 5 es de 79, que es primo.

Incluso aparentemente desalentadora número como 738629049682427904000000 es muy rápidamente con la prueba de la división. Un número como 738629049687284810748997 toma demasiado tiempo con la prueba de la división. Fermat diferencia de dos cuadrados método podría funcionar mejor en este caso. O incluso puede ser que necesite algo más sofisticado, como Pollard $\rho$ o el método de Pollard $p - 1$ método.

3voto

James47 Puntos 330

Hay algunas maneras diferentes para factorizar números enteros, pero la más sencilla para entender (aunque no siempre la más eficiente) es la división de ensayo. Si el número es par, dividen por $2$, que le da $355500000$. Seguir dividiendo $2$ hasta obtener un número impar, en este caso $11109375$. Luego puede ir a hacer lo mismo con el siguiente % primer $3$y así sucesivamente y así sucesivamente. Por supuesto si el número es primo con, esto no es una buena manera para hacer las cosas.

3voto

Lanier Freeman Puntos 958

I en este caso, trate de dividir a $711,000,000$$1,000,000$.

Consigue $711$$1,000,000$. Vamos a tratar de $711$ primera.

$711 = 79 * 9$ Aquí podemos ver que $79$ es un número primo, así que lo mantenga como un factor. $9$ no es, así que vamos a dividir en dos números primos.

$9 = 3 * 3$. Ahora usted tiene $79*3^2*1,000,000$. Todo lo que tenemos que hacer ahora es factor de $1,000,000$.

$1,000,000 = 2 * 500,000$. $2$ es un nuevo factor.

$200,000 = 2 * 250,000$. $2$ es un nuevo factor.

Ahora tenemos $79*3^2*2^2*250,000$. Mantener el factoring $250,000$.

$100,000 = 2 * 125,000$. $2$ es un nuevo factor.

$50,000 = 2 * 62,500$. $2$ es un nuevo factor.

Ahora tenemos $79*3^2*2^4*62,500$. Mantener el factoring $62,500$.

$62,500 = 31,250 * 2$. $2$ es un nuevo factor.

$31,250 = 15,125 * 2$. $2 es un nuevo factor.

$79*3^2*2^6*15,125$ es lo que tenemos ahora. Mantener el factoring $15,125.$

$15,125 = 5^6$. Ahora tenemos $711,000,000$ en términos de números primos, y es la siguiente:

$79*3^2*2^6*5^6$

2voto

Joonas Puntos 216

Aparte de la obvia de los criterios de divisibilidad por una potencia de $10$, la divisibilidad por $5$), aquí están algunos hechos elementales que se pueden usar para acelerar el juicio de la división de enfoque relativamente pequeño $n$:

  • El menor factor primo de un entero $n$ no es mayor que $\sqrt{n}$.(prueba de )
  • Si el (base diez) suma de dígitos de $n$ es divisible por $3$ (resp. $9$ ), a continuación, $n$ es divisible por $3$ (resp. $9$).
  • Si la última $k$ dígitos de $n$ forma un entero que es divisible por $2^k$ (resp. $5^k$ ), a continuación, $n$ es divisible por $2^k$ (resp. $5^k$) ($k = 0,1,\ldots$).
  • Si la suma de todos los otros dígitos de $n$ (a partir de la primera, el dígito más a la izquierda) es divisible por $11$, $n$ es divisible por $11$.

El primer punto debe ser su go-to para cualquier entero con $3$ dígitos o menos, ya que hay sólo $11$ primos menos de $\sqrt{1,000}$.

1voto

Mastrem Puntos 385

Existen algoritmos para hacer esto, pero se ejecutan en el no-tiempo polinomio (aunque con un ordenador cuántico sería capaz de hacerlo en el polinomio de tiempo).

Existen algunos accesos directos para comprobar si un número $n$ es divisible por un primo $p$ para un par de números primos. Por ejemplo:

Si el último dígito de un número es par, entonces el número es divisible por $2$.

Si la suma de los dígitos de un número es divisible por $3$, entonces el número es divisible por $3$.

Si el último dígito de un número es o $5$ o $0$, entonces el número es divisible por $5$

Si usted toma un número y la etiqueta de cada dígito, después de lo cual se suman todos los dígitos en una posición impar y todos los dígitos en una posición, el hecho de que su diferencia es divisible por 11 significa que el número entero es divisible por 11 (Ejemplo: $796235$, $(7+6+3)-(9+2+5=)=0$ en$11\ |\ 0$$11\ |\ 796235$).

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X