# An integer divisible by 8 and 15 must also be divisible by 24. Why?

I have a question on the GRE that says "If an integer is divisible by both 8 and 15, then the integer must also be divisible by" and the choices are:

• 16
• 24
• 32
• 36
• 45

The answer is 24. I guess I could figure out that the first common multiple of 8 and 15 is 120 and plug in the numbers, but is there a more sophisticated way to do it? Something that follows from the properties of 8 and 15? It happens that 24 is the only number that goes into 120 but what if it wasn't? Is there a way to prove that 24 is the only one that works?

• $\operatorname{lcm}(8,15)=120$. $\\\\24\mid 120$. – Don Thousand Nov 13 at 15:41
• Think about the prime factors of each. – Randall Nov 13 at 15:41
• You've done it the right way. Such a number must be divisible by $120$, and so by any factor of $120$. If $60$ were on the list and $24$ was not, then the answer would be $60$. You can't tell the answer without looking at the list. – saulspatz Nov 13 at 15:46
• @saulpatz, But 60 is not divisible by 8. – michaelrr Nov 13 at 15:54
• "But 60 is not divisible by 8. " and $24$ is not divisible by $15$. That doesn't matter. $1$ is not divisible by anything and it divides all integers. – fleablood Nov 13 at 16:47

If $$K$$ is divisible by $$a$$ and $$K$$ is divisible by $$b$$ then $$K$$ is divisible by the least common multiple of $$a$$ and $$b$$. ANd $$K$$ is divisible by all factors of the least common multiple of $$a,b$$.

The least common multiple of $$8$$ and $$15$$ is $$8*15 = 120$$. And the factors of $$120$$ are $$1,2,3,4,5,6,8,10, 12,15,20,24,30,40,60,120$$ and those will all divide the integer. $$24$$ is the only one on the list.

Of course you don't have to create the entire list. You just have to know $$120$$ divide the integer so anything that divides $$120$$ will also divide the integer. And $$24$$ is the only thing on the list that divides $$120$$.

More detail:

$$8 = 2^3$$ and $$15 = 3^15^1$$ and the least common multiple of $$8$$ and $$15$$ is $$2^33^15^1$$ and that divides our integer. So any number of the form $$2^a3^b5^c$$ where $$a$$ is at most $$3$$, $$b$$ is at most $$1$$ and $$c$$ is at most $$1$$ (and they can be $$0$$) will divide the integer. But if any of the factors have larger powers or if the have primes other than $$2,3,5$$ we can't know they divide the integers.

$$16 = 2^4$$ that's out because $$4 > 3$$.

$$24 = 2^3*3^1$$ that's okay because $$3 \le 3$$ and $$1 \le 1$$.

$$32 = 2^5$$ that's out because $$5 > 3$$.

$$36 = 2^2*3^2$$ and that's out because $$2 > 1$$.

$$45= 3^2*5^1$$ and that's out because $$2 > 1$$.

If this integer is divisible by $$8$$ and $$15=3×5,$$ then it is perforce divisible by $$8$$ and $$3,$$ and consequently, by $$8×3$$ as well.

• that makes sense. Thanks. – michaelrr Nov 13 at 16:25
• Gotta be careful. If we were told the integer were divisible by $8$ and by $12=4\times 3$ that would mean it is divisible by $8$ and $4$. But that does not mean it is divisible by$8\times 4$. (Because $8$ and $4$ aren't relatively prime.) – fleablood Nov 13 at 16:40
• @fleablood I wouldn't argue that way since $4$ is already contained in the $8.$ – Allawonder Nov 13 at 16:53
• @michaelrr Glad this helped you. – Allawonder Nov 13 at 16:53
• Exactly. I'm pointing out that we need to avoid that error. – fleablood Nov 13 at 17:56

The prime numbers tell you everything here. The list of possible answers are relatively small so I’d begin by factoring each out: $$16 = 2^4$$ $$24 = 8 \cdot 3 = 2^3 \cdot 3$$ $$32 = 2^5$$ $$36 = 6^2 = 2^2 \cdot 3^2$$ $$45 = 3^2 \cdot 5.$$

Now, a number divisible by $$8 = 2^3$$ must have at least $$3$$ factors of $$2$$ and a number divisible by $$15 = 3 \cdot 5$$ must have at least one factor of $$3$$ and at least one factor of $$5$$.

Let’s now take a look at the list of possible answers. $$16$$ and $$32$$ won’t work since we only require $$3$$ factors of $$2$$. $$36$$ and $$45$$ won’t work because we require just one factor $$3$$. Hence the only remaining possibility among the list is $$24$$ (this case can be verified to be fine but I’d probably fill in $$24$$ and move on since it’s the GRE).

We prove the following general result:

If

$$p, q \in \Bbb P \tag 1$$

are distinct primes and

$$n \in \Bbb Z \tag 2$$

with

$$p^3 \mid n, \; q \mid n, \tag 3$$

then

$$p^3q \mid n; \tag 4$$

for we have

$$\gcd(p^3, q) = 1; \tag 5$$

hence by Bezout's identity there exist $$a, b \in \Bbb Z$$ such that

$$ap^3 + bq = 1; \tag 6$$

we multiply this through by $$n$$:

$$ap^3n + bqn = n; \tag 7$$

we also have

$$p^3 \mid n \Longrightarrow n = p^3x, \; x \in \Bbb Z, \tag 8$$

$$q \mid n \Longrightarrow n = qy, \; y \in \Bbb Z; \tag 9$$

we substitute (8) and (9) into (7):

$$ap^3qy + bqp^3x = n, \tag{10}$$

whence

$$p^3q(ay + bx) = n \Longrightarrow p^3q \mid n. \tag{11}$$

Now taking

$$p = 2, q = 3 \tag{12}$$

yields the specific result that

$$24 = 2^3 \cdot 3 \mid n. \tag{13}$$

Note Added in Edit, Wendesday 13 November 2019 9:50 AM PST: It is perhaps worth noting that our result here may easily be extended from the case $$p^3 \mid n$$ to the case $$p^k \mid n$$ for arbitrary $$k \in \Bbb N$$; indeed, one need merely walk through the above with $$p^3$$ replaced by $$p^k$$ to see that this is so.

It is also likely worth pointing out that

$$\gcd(p, q) = 1 \Longrightarrow \gcd(p^k, q) = 1, \; \forall k \in \Bbb N; \tag{14}$$

indeed, we may write

$$ap + bq = 1, \; a, b \in \Bbb Z; \tag{15}$$

focussing for the moment on the case $$k = 2$$ we multiply (15) through by $$p$$:

$$ap^2 + bqp = p; \tag{16}$$

then

$$\gcd(p^2, q) = d > 1 \Longrightarrow d \mid p^2, \; d \mid q; \tag{17}$$

by virtue of (16) this implies

$$d \mid p \Rightarrow \Leftarrow \gcd(p, q) = 1; \tag{18}$$

$$\gcd(p^2, q) = 1; \tag{20}$$

this logic may be extended to general $$k \in \Bbb N$$ by an inductive argument: if

$$\gcd(p^k, q) = 1, \tag{21}$$

we multiply (15) by $$p^k$$:

$$ap^{k + 1} + bqp^k = p^k; \tag{22}$$

now if

$$\gcd(p^{k + 1}, q) = d > 1, \tag{23}$$

as above we have

$$d \mid p^{k + 1}, \; d \mid q \Longrightarrow d \mid p^k, \tag{24}$$

which of course is precluded by (21); therefore

$$\gcd(p, q) = 1 \Longrightarrow \gcd(p^k, q) = 1, \; \forall k \in \Bbb N. \tag{25}$$

End of Note.

• That is great, @robertlewis. I am really grateful that you put all the effort into this fine proof but I must admit it is a little over my head. – michaelrr Nov 14 at 1:46
• @michaelrr: Thank you for the kind words. I simply used standard facts and techniques from very basic number theory. You might check out en.wikipedia.org/wiki/B%C3%A9zout%27s_identity. Cheers! – Robert Lewis Nov 14 at 1:51