0
$\begingroup$

The problem is as follows

If $A = 9n$ and $B = 8n$ where $n$ is a positive integer, which one has a greater number of distinct prime factors ?

According to the answer, we cannot tell. However, I am not totally convinced because I don't know exactly how many distinct prime factors there are in the first place.

For $A$, I am not sure if I am supposed to think 3 as one prime factor or $3*3$ as two factors. I want to say that there is only one prime factor that has to do with $9$.

I understand that $n$ can have multiple prime factors, but I don't think that matters because $B$ also has $n$ in it, so I disregarded it (I am suspecting that this is the reason I got it wrong).

For $B$, if $8 = 2*2*2$ considered as having one distinct prime factor, then the number of distinct prime factor would be one, thus I concluded that $A$ and $B$ has the same number of distinct prime factors...

What am I missing here ?

$\endgroup$
  • 1
    $\begingroup$ "For $A,$ I am not sure if I am supposed to think 3 as one prime factor or 3∗3 as two factors." The word "distinct" means that 3 is counted only once as a factor. For example, the distinct prime factors of 9*60 are 2, 3, and 5. The distinct prime factors of 8*60 are also 2, 3, and 5. The distinct prime factors of 9*21 are 3 and 7, while the distinct prime factors of 8*21 are 2, 3, and 7. $\endgroup$ – Will Orrick Aug 19 '13 at 5:13
  • $\begingroup$ Thanks for the clarification. $\endgroup$ – hyg17 Aug 19 '13 at 15:08
1
$\begingroup$

If $n$ has a factor of $2$ but no factor of $3$, then $8n$ has the same number of distinct prime factors as $n$, and $9n$ has one more, namely, $3$. If $n$ has a factor of $3$ but no factor of $2$, the situation is exactly reversed. And if $n$ has both a factor of $2$ and a factor of $3$, or if it has neither $2$ nor $3$ as a prime factor, then $9n$ and $8n$ have the same number of distinct prime factors.

In a little more detail, suppose that $n$ has $k$ distinct prime factors. If $2\mid n$, then $8n$ also has $k$ distinct prime factors, but if $2\nmid n$, then $8n$ has $k+1$ distinct prime factors: it has $2$ as a prime factor in addition to the ones that $n$ already had. Similarly, if $3\mid n$, then $9n$ has $k$ distinct prime factors, but if $3\nmid n$, then $9n$ has $k+1$ distinct prime factors. Thus,

  • $8n$ and $9n$ both have $k$ distinct prime factors if $2\mid n$ and $3\mid n$;
  • $8n$ and $9n$ both have $k+1$ distinct prime factors if $2\nmid n$ and $3\nmid n$;
  • $8n$ has $k$ distinct prime factors and $9n$ has $k+1$ if $2\mid n$ and $3\nmid n$; and
  • $8n$ has $k+1$ distinct prime factors and $9n$ has $k$ if $2\nmid n$ and $3\mid n$.
$\endgroup$
  • $\begingroup$ Thank you, that was very helpful. So n containing 2 or 3 was the fact that I was not looking at. Tricky. $\endgroup$ – hyg17 Aug 19 '13 at 15:09
  • 1
    $\begingroup$ @hyg17: You’re welcome. $\endgroup$ – Brian M. Scott Aug 19 '13 at 16:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.