# Why is this prime factor not counted

I came across a question:

If j is divisible by 12 and 10, is it divisible by 24 ?

The example draws the following factor tree which I agree with

But then it states that

There are only two 2's that are definitely in the prime factorization of j. because the 2 in the prime factorization in 10 maybe redundant.That is it may be the same 2 as one of the 2's in the prime factorization of 12.

My question is what does " That is it may be the same 2 as one of the 2's in the prime factorization of 12. " mean ?

Edit: Can we consider it this way "Since the 2s have already been accounted for in 12 of the first figure there is no need to consider the 2s from the second figure in the final figure - in short the final figure is a union of both"

-
The reason is given in the paragraph that you posted. In general, the reasoning is the same as in your question here. – Brandon Carter Jul 4 '12 at 18:26
You don't need the $2$ from the right figure to have $10$ as a factor. – Andrew Jul 4 '12 at 18:27
The "union" perspective is good, but it's not /exactly/ a set-theoretic union, because the number of 2s and 3s and 5s matters... – Ben Millwood Jul 4 '12 at 18:46
@BenMillwood What i meant to say is that in such a case the no of maximum repetitions of a specific no will be added to the final figure and that no shall be then neglected from other figures as the case of 2. – Rajeshwar Jul 4 '12 at 18:49
Yeah, that's correct (except for the bit about neglect, which I don't understand), but I'm just saying it's not quite a union as the term is normally used unless you look at the things in a certain sort of way. – Ben Millwood Jul 4 '12 at 18:54

You are trying to compute the least common multiple of $12$ and $10$. The idea is that to compute the least common multiple, you prime factor each of the two numbers. Then in the lcm, the exponent of $p$ is the max of the exponent of $p$ in the two numbers. So if $p = 2$, $2^2$ appears in $12$ and $2^1$ appears in $10$. Hence the lcm must have $2^2$.

-
Can we put it this way "Since the 2s have already been accounted for in 12 of the first figure there is no need to consider the 2s from the second figure in the final figure - in short the final figure is a union of both" – Rajeshwar Jul 4 '12 at 18:39
@Rajeshwar The idea is that $j$ needs to be divisible by $12$. $12$ contains $4 = 2^2$. So $j$ must contain at least $2^2$. $10$ only has $2$. If $j$ is divisible by $4$, then it is already divisible by $2$. There is no need to add any more $2$'s. – William Jul 4 '12 at 18:48
Thanks for the great explanation. That definitely makes sense!!!! Thanks – Rajeshwar Jul 4 '12 at 18:55

Because, as they said, it may be redundant: it may be one of the two $2$’s already counted in the lefthand tree. Suppose, for instance, that $j=60$: then $j=2^2\cdot3\cdot5$ has only two factors of $2$, but it is divisible by both $12$ and $10$.

-

In order for $j$ to be divisible by $10$, it needs to be divisible by all the prime factors of $24$ counting multiplicity. In order for $j$ to be divisible by $12$, it needs to be divisible by all the prime factors of $24$ counting multiplicity. Thus for $j$ to be divisible by both $10$ and $12$, it has to be divisible by all the prime factors of $10$ counting their multiplicity as well as all the prime factors of $12$ counting their multiplicity. Notice that we aren't trying to divide $j/10$ by the prime factors of $12$, and so we have no reason to add the multiplicities. Indeed, since $2$ is a factor of $10$ with multiplicity $1$ and a factor of $12$ with multiplicity $2$, all we know from this is that $2$ is a factor of $j$ with multiplicity at least $\max\{1,2\}=2$.

-

I'm not sure what your question is. The 2 from the middle figure is one of the 2's in the right figure. The other two from the left figure is somewhere in the factor (sub)tree of the middle figure.

I'm going to answer what I hope is your question - the organization of the right-hand figure itself, not the mathematics involved.

If they'd done the middle figure like 5-2-? and the right figure like 5-2-2-3-? would that have made this clearer?

Luckily, it doesn't matter what order these go in! That's part of the Fundamental Theorem of Arithmetic - there is a unique prime factorization, up to order.

-