# GMAT. How do you tell if a number is divisible by a divisor using prime factors?

Say I have a dividend (15) and a divisor (6). Using prime numbers, how do I tell if the dividend is divisible by the divisor?

The primes for 15 are $5^13^1$. The primes for 6 are $3^12^1$.

What's the rule regarding prime factors and divisibility? The divisor needs to have only the prime factors of the dividend, in any amount, but no other factors?

But a number is a multiple of another number if it contains at least the factorization of the smaller number? Is that correct? For example:

45 has a factorization of $3^25^1$
15 has a factorization of $3^15^1$
9 has a factorization of $3^2$

The above 3 are factors of 45.

But: 12 has a factorization of $2^23^1$

12 is not a factor because of the extra 2 right? 45 is not a multiple of 12 because it does not contain the factorization of 12 right?

• The dividend has to have all the prime factors of the dividend (and possibly others), and at least as many each prime factor. So $60 = 2^2 3^1 5^1$ is divisible by $6=2^13^1$ and $12=2^2 3^1$ but not by $24=2^3 3^1$ or by $14 = 2^1 7^1$ – Henry Nov 18 '15 at 8:42
• You mean the dividend has to have all the prime factors of the divisor? – Jwan622 Nov 19 '15 at 1:17
• Yes - and you have to take into account multiplicity – Henry Nov 19 '15 at 9:01

Choose whichever way you find more convenient to remember:

The exponent of each factor in the dividend must be larger than or equal to the exponent of the corresponding factor in the divisor (if no such factor exists in the divisor then it's OK, just keep checking).

The exponent of each factor in the divisor must be smaller than or equal to the exponent of the corresponding factor in the dividend (if no such factor exists in the dividend then stop checking, the answer is no).

This is a great question. There is a lot about this property and it is used everywhere in Number Theory. The fact that every integer can be broken down as such is referred to as the Fundamental Theorem of Arithmetic. However, we typically only consider the positive integers, since the only difference between the two is a sign change.

If we have a number, for example $360$, and we wish to know its divisors, we first decompose it as a product of primes: $$360 = 2^3\cdot 3^2 \cdot 5^1$$

Although it doesn't take much to show, we know that if a number $r$ divides $360$, it is of the form $2^a3^b5^c$ where $0 \leq a \leq 3$, $0 \leq b \leq 2$, and $0 \leq c \leq 1$.

And yes, a number is a multiple of another if its prime factorization is "inside" the other numbers'. For example, we know that $9$ divides $360$ since $3^2 = 9$ and $3^2$ is in the prime decomposition of $360$.

• What does the "its" refer to in your second to last sentence? Does it refer to "another" or "number"? – Jwan622 Nov 19 '15 at 1:19
• @Jwan622 that number which is a multiple. – 9301293 Nov 19 '15 at 3:25