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

Question

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?

Answer 1

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

Answer 2

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