3
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ $\operatorname{lcm}(8,15)=120$. $\\\\24\mid 120$. $\endgroup$ – Don Thousand Nov 13 at 15:41
  • 3
    $\begingroup$ Think about the prime factors of each. $\endgroup$ – Randall Nov 13 at 15:41
  • 2
    $\begingroup$ 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. $\endgroup$ – saulspatz Nov 13 at 15:46
  • 1
    $\begingroup$ @saulpatz, But 60 is not divisible by 8. $\endgroup$ – michaelrr Nov 13 at 15:54
  • 1
    $\begingroup$ "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. $\endgroup$ – fleablood Nov 13 at 16:47
7
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ that makes sense. Thanks. $\endgroup$ – michaelrr Nov 13 at 16:25
  • 7
    $\begingroup$ 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.) $\endgroup$ – fleablood Nov 13 at 16:40
  • $\begingroup$ @fleablood I wouldn't argue that way since $4$ is already contained in the $8.$ $\endgroup$ – Allawonder Nov 13 at 16:53
  • $\begingroup$ @michaelrr Glad this helped you. $\endgroup$ – Allawonder Nov 13 at 16:53
  • 2
    $\begingroup$ Exactly. I'm pointing out that we need to avoid that error. $\endgroup$ – fleablood Nov 13 at 17:56
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – michaelrr Nov 14 at 1:46
  • $\begingroup$ @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! $\endgroup$ – Robert Lewis Nov 14 at 1:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.