Factors of a number?

Question

I'm studying for the SAT on collegeboard.org, and I came across the problem: What is the least positive integer that has the same number of positive factors as 175?

The answer was 12, explained as:

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.

I've never learned anything about the number of factors for a number, so this line: The numbers with 6 positive factors are of the form$p_1^2*p_2$or$p^5$ doesn't make sense to me. Out of context, I understand that $p_1$ is 2, but I don't understand where those two formulas came from or what p is supposed to be the set of.

Answer 1

$p_1$, $p_2$, and $p$ in your quote stand for primes - arbitrary primes. That is, if $p$ is any prime whatsoever, then $p^5$ has exactly 6 factors; and if $n$ has exactly 6 factors, then either $n=p^5$ for some prime $p$, or $n=p_1^2p_2$ for some primes $p_1$ and $p_2$. Everything rests on a formula for the number of factors: if $$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)$$

You can find this explained in any good introductory number theory textbook.

Answer 2

I'll try to approach this from a layman's perspective, shying away from the $p_1^{a_1}$ notation in favor of a more conversational approach...

Note: When they say "factor", they mean what most of us would call "divisor". I might switch between the two without warning.

We have a few tasks. The first is to determine the number of positive divisors of $175$. We could just list and then count them (and if you have to do this at most one time on the SAT, then this might be your best bet...) to arrive at $1, 5, 7, 25, 35, 175$. This much you could do.

On the other hand, we could look at the prime factorization of $175$ as $5^2 \cdot 7^1$ and determine how many divisors we could make from these numbers. Since a prime that divides $175$ must be among the primes in $175$, we can only choose combinations of powers of $5$ and of $7$. Since a divisor of $175$ can't be bigger than $175$, we can't make the exponents bigger than what we have in $5^2 \cdot 7^1$ (so the max exponent of $5$ is $2$ and the max exponent of $7$ is $1$). Note that $0$ is the smallest exponent of a prime that we can use.

So we choose a power of $5$ and a power of $7$ and multiply them together to get a divisor of $175$ ... only if the exponent of $5$ is $0, 1, 2$ and the exponent of $7$ is $0, 1$. There are three choices for our first exponent and two for our second exponent, leaving us with $3 \cdot 2 = 6$ divisors. The divisor $1$ corresponds to taking both exponents to be zero; the divisor $175$ corresponds to taking both exponents to be as large as possible (as outlined above).

This is where Gerry gets the formula for "number of factors". The most the exponent of a certain prime can be is just whatever that exponent is in the number we're inspecting ($175$ up till now). But it could also be as low as zero, so there are (exponent + 1) options for each prime. Multiplying these together gives us the total number of factors/divisors.

---

Once we have the number of divisors ($6$ in our example), we need to find the divisors of this number! Since $6 = 1 \cdot 6 = 2 \cdot 3$, we either multiplied together one and six, or two and three in the above calculation of the number of divisors of the original number ($175$). If it was one and six, then we had an exponent of $5$ (since this is $6 - 1$) for our prime. If it was two and three, then we had exponents of $1$ and $2$ for our primes. Keep in mind that we don't know what these primes are yet.

But if we take the smallest possible primes, we could have $2^5$ (for the case of one prime to the fifth power), $2^1 \cdot 3^2$ or $2^2 \cdot 3^1$ for the case of one to the first power, one to the second power). The smallest of these three numbers is $12$.

---

Now for a more involved example, in hopes that you can generalize from here, incorporating the other answers:

What is the least positive integer that has the same number of positive factors as 2048?

Since $2048 = 2^{11}$, there are $11 + 1 = 12$ positive divisors/factors of $2048$. So we want the smallest positive integer $n$ that has $12$ positive divisors.

But when we factor $12$, it gets a little more complicated!

For $12 = 12 \cdot 1$, we have $n = $ (some prime to the eleventh power, which we already know is) $2^{11}$.

For $12 = 2 \cdot 6$, we have $n = p^1 \cdot q^5$, the smallest two being $2 \cdot 3^5$ and $3 \cdot 2^5$.

For $12 = 3 \cdot 4$, we have...

But there's one more!

For $12 = 2 \cdot 2 \cdot 3$, we could have $p^1 \cdot q^1 \cdot r^2$. I won't belabor this further, but you can see that the number of candidates for smallest $n$ grows rapidly.

Answer 3

This seems a little hard for the SATs. I assume there were multiple choices? This might have been one case where you might have tried working backwards, counting the factors of each answer starting with the least.