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?
 A: 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$.
A: 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.
A: 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).
A: 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}$
this contradiction forces
$\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.
