# Factors of a number?

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.

-
Say you have a number $N$ decomposed into its prime factors $N = p_1^{a_1} ... p_n^{a_n}$. Can you see that any positive factor of $N$ must be of the form $p_1^{b_1}...p_n^{b_n}$, where $0 \leq b_i \leq a_i$? Once you've observed this, we can count how many numbers there are of this form: we have $a_1 + 1$ choices for $b_1$, $a_2 + 1$ choices for $b_2$, and so on, and so we have $T = (a_1+1)(a_2+1)...(a_n+1)$ total factors of $N$ (since prime factorisation is unique). Note that this number $T$ includes the trivial factors $1$ and $N$. –  Matt Jan 29 '12 at 2:10
If you wish to generate the different factors of $N$, you can list the results from considering all different combinations of the $b_i$. –  Matt Jan 29 '12 at 2:13
Is this really on collegeboard.org as practice for the SAT? I don't remember anything half as advanced as this on the SAT. –  JohnJamesSmith Jan 29 '12 at 3:57
@JohnJamesSmith, Yeah, it surprised me too. I thought if anything, I knew a little more than was needed for the SAT. I'm still coming across new things. –  mowwwalker Jan 29 '12 at 21:10

$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.

-
Sorry, I always feel a bit thick when I'm on the Math portion of stackexchange. I still don't understand any of this. What do you mean by arbitrary primes? How can you then infer that $p^5$ has exactly 6 factors? I understand that in math there are some things we have to accept as truths, and some things that we have to derive ourselves, but, having never worked with primes this way before, I can't differentiate. –  mowwwalker Jan 29 '12 at 2:49
You can list all the factors ("divisors") of $p^5$ : $1, p, p^2, p^3, p^4, p^5$ so there are six of them. –  The Chaz 2.0 Jan 29 '12 at 3:11
You have to read what I wrote. What I mean by "arbitrary primes" is explained in the very next clause: "that is, if $p$ is any prime whatsoever...." How can I infer that $p^5$ has exactly 6 factors? By using that formula I gave, the one about which I said "everything rests on a formula...." Nothing I wrote has to be accepted as true; you don't have to derive it yourself, either; you can do what I suggested in the last sentence of my answer. –  Gerry Myerson Jan 29 '12 at 8:59

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.

-
+1 Very detailed and thorough explanation! –  JavaMan Jan 29 '12 at 5:53
Awesome answer, I started to understand when you mentioned the permutations of the powers of the prime factors. What about 4096? That would be 13, but 13 being a prime, the only factorization is 13*1. Is that to say that 2^12 IS the smallest number with 13 factors? –  mowwwalker Jan 29 '12 at 6:10
Exactly! So glad to see you taking off with this :) –  The Chaz 2.0 Jan 29 '12 at 6:13

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.

-
All right, maybe this answer should have ended up as a comment (was going to include more until I realized the Chaz had it covered), but I still stand behind it. The original poster said this was a problem he came across studying for the SAT, which, unless it has changed, offers multiple choices and is timed. Also, without knowing the formula for the number of factors for a given number, which I never saw in high school, there is no good way to proceed. But he can certainly tell what the least answer is that has 6 factors. –  Mike Jan 30 '12 at 7:10