How Well Do You Know Your Factors?

Quarter Wit, Quarter WisdomIn the last three weeks, we discussed a couple of strategies we can use to solve max-min questions: ‘Establishing Base Case’ and ‘Focus on Extremes’. Now try to use those to solve this question:

Question: A carpenter has to build 71 wooden boxes in one week. He can build as many per day as he wants but he has decided that the number of boxes he builds on any one day should be within 4 off the number he builds on any other day.
(A) What is the least number of boxes that he could have build on Saturday?
(B) What is the greatest number of boxes that he could have build on Saturday?

Meanwhile, let’s move on to something else today. What we will discuss today is a very simple concept but it seems odd to us when we first confront it even if we are very comfortable with factors and divisibility. If we tell you the concept right away, you will probably not believe us when we say that many people are unable to come up with it on their own. Hence, we will first give you a question which you need to answer in 30 seconds. If you are unable to do so, then we will discuss the concept with you!

Question: A, B, C and D are positive integers such that A/B = C/D. Is C divisible by 5?

Statement 1: A is divisible by 210

Statement 2: B = 7^x, where x is a positive integer

Solution: Let’s discuss the solution till the point I assume you will be quite comfortable.

We need to find whether C is divisible by 5. So let’s separate the C out of the variables.

C = AD/B

Since C is an integer, AD will be divisible by B but what we don’t know is that after the division, is the quotient divisible by 5?

Statement 1: A is divisible by 210

We still have no idea what B is so this statement alone is not sufficient. Let’s take an example of how the value of B could change our answer. Assume A is 210.

If B is 3, AD/B will be divisible by 5.

If B is 10, AD/B may not be divisible by 5 (depending on the value of D).

Statement 2: B = 7^x, where x is a positive integer

We have no idea what A and D are hence this statement alone is not sufficient.

Using both together: Now, this is where the trick comes in. Using both statements together, we see that C = (210*a*D)/(7^x)

Now we can say for sure that C will be divisible by 5. If you are not sure why, read on.

The Concept:

As you know, factors (also called divisors) of a number N are those positive integers which completely divide number N i.e. they do not leave a remainder on dividing N. If F is a factor of N, N/F leaves no remainder. This also means that N can be written as F*m where m is an integer. Sure you feel this is elementary but this concept is not as internalized in your conscience as you believe. To prove it, let me give you a question.

Example 1: Is 3^5 * 5^9 * 7 divisible by 18?

Did you take more than 2 seconds to say ‘No’ confidently?

For N to be divisible by F, you should be able to write N as F*m i.e. N must have F as a factor. F here is 18 (= 2*3^2) but we have no 2 in N (which is 3^5 * 5^9 * 7) though we do have a couple of 3s. Hence this huge product is not divisible by 18.

This helps us deduce that odd numbers are never divisible by even numbers.

Example 2: Is 3^5*7^6*11^3 divisible by 13?
The answer is simply ‘No’.

For the numerator to be divisible by the denominator, the denominator MUST BE a factor of the numerator. In the entire numerator, there is no 13 so the numerator is not divisible by 13.

Example 3: On the other hand, is 3^5*7^6*11^3*13 divisible by 13?

Yes, it is. 13 gets cancelled and the quotient will be 3^5*7^6*11^3.

Example 4: Is 2^X divisible by 3?

No. No matter what X is, you will only have X number of 2s in the numerator and will never have a 3. So this will not be divisible by 3.

Let’s come back to the original question now:

Given that C = (210*a*D)/(7^x)

Whatever x is, 7^x will get cancelled out by the numerator and we will be left with something. That something will include 5 (obtained from 210) since only 7s will be cancelled out from the numerator. Hence C is divisible by 5.

Answer (C)

Karishma, a Computer Engineer with a keen interest in alternative Mathematical approaches, has mentored students in the continents of Asia, Europe and North America. She teaches the GMAT for Veritas Prep and regularly participates in content development projects such as this blog!