¿Factores de un número?

Question

Estoy estudiando para el examen SAT en collegeboard.org y me encontré con el problema: What is the least positive integer that has the same number of positive factors as 175?

La respuesta fue 12, explicado como:

The number 175 is equal to 5 x 7 x 5. It has a total of 6 positive factors: 1, 5, 7, 25, 35, and 175. The numbers with 6 positive factors are of the form$p_1^2*p_2$or$p^5$. The least number of the first form is 12. The least number of the second form is 32. Thus, the answer is 12, which has the positive factors 1, 2, 3, 4, 6, and 12.

Nunca he aprendido nada sobre el número de factores de un número, por lo que esta línea: The numbers with 6 positive factors are of the form$p_1^2*p_2$or$p^5$ no tiene sentido para mí. Fuera de contexto, entiendo que $p_1$ es de 2, pero no entiendo de dónde están esas dos fórmulas de vino o lo que p se supone que es el conjunto de.

Answer 1

$p_1$, $p_2$, y $p$ en su comilla para números primos - números primos arbitrarios. Es decir, si $p$ es cualquier primer absoluto, $p^5$ tiene exactamente 6 factores; y si $n$ tiene exactamente 6 factores, entonces cualquier $n=p^5$ % primer $p$, o $n=p_1^2p_2$ para algunos ceba $p_1$ y $p_2$. Todo se basa en una fórmula para el número de factores: si $$n=p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r}$$ where the $ p_i $ are distinct primes and the $a_1 $ are positive integers, then the number of factors of $n $ is $% $ $(a_1+1)(a_2+1)\times\cdots\times(a_r+1)$

Usted puede encontrar esto explicado en cualquier buen libro de teoría número introductorio.

Answer 2

Esto parece un poco duro para el SAT. ¿Supongo que hubo múltiples opciones? Esto pudo haber sido un caso donde podría haber intentado trabajar hacia atrás, contando los factores de cada respuesta a partir de menos.

Answer 3

Voy a tratar de acercarse a esta desde un laico de perspectiva, huyendo de la $p_1^{a_1}$ notación en favor de una más conversacional enfoque...

Nota: Cuando dicen "factor", se refieren a lo que la mayoría de nosotros le llamamos "divisor". Yo podría cambiar entre los dos sin previo aviso.

Tenemos un par de tareas. El primero es determinar el número de divisores positivos de $175$. Podríamos lista y, a continuación, el recuento de ellos (y si usted tiene que hacer esto en la mayoría de los una vez en el SAT, entonces esta podría ser su mejor apuesta...) para llegar a $1, 5, 7, 25, 35, 175$. Esta cantidad que usted podría hacer.

Por otro lado, se pudo ver en la descomposición en factores primos de a $175$ $5^2 \cdot 7^1$ y determinar cuántos divisores podríamos hacer a partir de estos números. Desde un primo que divide a $175$ debe estar entre los números primos en $175$, sólo podemos elegir las combinaciones de poderes de $5$ e de $7$. Desde un divisor de a $175$ no puede ser más grande que $175$, que no podemos hacer los exponentes más grandes de lo que tenemos en $5^2 \cdot 7^1$ (para el máximo exponente de $5$ $2$ y el máximo exponente de $7$$1$). Tenga en cuenta que $0$ es el menor exponente de un primer que podemos utilizar.

Así que elegir una potencia de $5$ y una potencia de $7$ y multiplicar juntos para obtener un divisor de a $175$ ... sólo si el exponente de $5$ $0, 1, 2$ y el exponente de $7$$0, 1$. Hay tres opciones para nuestro primer exponente y dos para nuestro segundo exponente, lo que nos deja con $3 \cdot 2 = 6$ divisores. El divisor $1$ corresponde a la toma de ambos exponentes a ser cero; el divisor $175$ corresponde a la toma de ambos exponentes a ser tan grande como sea posible (como se indica más arriba).

Aquí es donde Gerry obtiene la fórmula para el "número de factores". La mayoría de las exponente de una cierta prime puede ser justo lo que el exponente es el número que estamos inspeccionando ($175$ hasta ahora). Pero también podría ser tan bajo como cero, por lo que hay (exponente + 1) opciones para cada uno de los prime. La multiplicación de estos juntos nos da el número total de factores o divisores.

---

Una vez que tenemos el número de divisores ($6$ en nuestro ejemplo), tenemos que encontrar los divisores de este número! Desde $6 = 1 \cdot 6 = 2 \cdot 3$, se multiplican juntos uno y seis años, o de dos y de tres en el cálculo anterior de que el número de divisores del número original ($175$). Si era uno y seis, luego tuvimos un exponente de $5$ (ya que este es $6 - 1$) para el primer. Si se fue de dos y de tres, luego tuvimos exponentes de la $1$ $2$ para nuestros primos. Tenga en cuenta que no sabemos lo que estos números primos son todavía.

Pero si tomamos el menor tamaño posible de los números primos, podríamos $2^5$ (para el caso de un primer a quinto poder), $2^1 \cdot 3^2$ o $2^2 \cdot 3^1$ para el caso de la uno a la primera potencia, uno a la segunda potencia). El más pequeño de estos tres números es $12$.

---

Ahora para los más involucrados ejemplo, en la esperanza de que se puede generalizar a partir de aquí, la incorporación de las otras respuestas:

¿Cuál es el menor entero positivo que tiene el mismo número de factores positivos como 2048?

Desde $2048 = 2^{11}$, $11 + 1 = 12$ divisores positivos y/o factores de $2048$. Así que queremos que el menor entero positivo $n$ que ha $12$ divisores positivos.

Pero cuando nos factor de $12$, se pone un poco más complicado!

Para$12 = 12 \cdot 1$, $n = $ (algunos de los mejores de la undécima potencia, que ya sabemos es) $2^{11}$.

Para$12 = 2 \cdot 6$,$n = p^1 \cdot q^5$, el más pequeño de los dos se $2 \cdot 3^5$$3 \cdot 2^5$.

Para $12 = 3 \cdot 4$, tenemos...

Pero hay uno más!

Para $12 = 2 \cdot 2 \cdot 3$, podríamos $p^1 \cdot q^1 \cdot r^2$. No voy a insistir sobre esto, pero usted puede ver que el número de candidatos para los más pequeños $n$ crece rápidamente.