Quarter Wit, Quarter Wisdom: Divisibility by Powers of 2

Quarter Wit, Quarter WisdomWe know the divisibility rules of 2, 4 and 8:

For 2 – If the last digit of the number is divisible by 2 (is even), then the number is divisible by 2.

For 4 – If the number formed by last two digits of the number is divisible by 4, then the number is divisible by 4.

For 8 – If the number formed by last three digits of the number is divisible by 8, then the number is divisible by 8.

A similar rule applies to all powers of 2:

For 16 – If the number formed by last four digits of the number is divisible by 16, then the number is divisible by 16.

For 32 – If the number formed by last five digits of the number is divisible by 32, then the number is divisible by 32.

and so on…

Let’s figure out why:

The generic rule can be written like this: A number M is divisible by 2^n if the last n digits of M are divisible by 2^n.

Take, for example, a division by 8 (= 2^3), where M = 65748048 and n = 3.

Our digits of interest are the last three digits, 048.

48 is completely divisible by 8, so we conclude that 65748048 is also divisible by 8.

A valid question here is, “What about the remaining five digits? Why do we ignore them?”

Breaking down M, we can see that 65748048 = 65748000 + 048 (we’ve separated the last three digits).

Now note that 65748000 = 65748 * 1000. Since 1000 has three 0s, it is made up of three 2s and three 5s. Because 1000 it has three 2s as factor, it also has 8 as a factor. This means 65748000 has 8 as a factor by virtue of its three 0s.

All we need to worry about now is the last three digits, 048. If this is divisible by 8, 65748048 will also be divisible by 8. If it is not, 65748048 will not be divisible by 8.

In case the last three digits are not divisible by 8, you can still find the remainder of the number. Whatever remainder you get after dividing the last three digits by 8 will be the remainder when you divide the entire number by 8. This should not be a surprise to you now – 65748000 won’t have a remainder when divided by 8 since it is divisible by 8, so whatever the remainder is when the last 3 digits are divided by 8 will be the remainder when the entire number is divided by 8.

In the generic case, the number M will be split into a number with n zeroes and another number with n digits. The number with n zeroes will be divisible by 2^n because it has n 2s as factors. We just need to see the divisibility of the number with n digits.

We hope you have understood this concept. Let’s take look at a quick GMAT question to see this in action:

What is the remainder when 1990990900034 is divided by 32 ?

(A) 16
(B) 8
(C) 4
(D) 2
(E) 0

Breaking down our given number, 1990990900034 = 1990990900000 + 00034.

1990990900000 ends in five 0’s so it is divisible by 32. 34, when divided by 32, gives us a remainder of 2. Hence, when 1990990900034 is divided by 32, the remainder will be 2. Our answer is D.

Getting ready to take the GMAT? We have free online GMAT seminars running all the time. And, be sure to follow us on FacebookYouTubeGoogle+, and Twitter!

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!

GMAT Tip of the Week

Divide and Conquer

(This is one of a series of GMAT tips that we offer on our blog.)

The quantitative section of the GMAT features a heavy emphasis on the divisibility of numbers, as multiple questions will require division as a necessary arithmetic step, and others will require you to reduce fractions or note whether a particular number is a factor of another. Because of this, the ability to see divisibility in short order is extremely helpful for both speed and accuracy.

Many numbers feature “tricks” to assist test-takers as they determine divisibility (i.e. an integer is divisible by 5 if its units digit is 0 or 5), but in many cases those tricks can be more trouble to memorize than they are worth. (We cover some of the more-worthwhile tips in one of last year’s Tip of the Week entries.) For numbers that don’t feature a quick-recognition divisibility trick, a universal divisibility strategy is likely the fastest way to perform the operation:

When assessing whether a number is divisible by another, you can take advantage of the algebraic concept that a(b + c) = ab + ac. In numerical terms, you could say that 7(17) = 7 (10 + 7), or 70 + 49, which equals 119.

Knowing that, we can apply the same concept in reverse – while 119 may not look to be an easy-to-divide number (it’s not even, not divisible by 3, not divisible by 5…), we can test for divisibility by 7 without having to perform long division. Instead, we can try to break 119 apart by subtracting multiples of 7 that are easy to calculate:

119 (our starting value)
-70 (a known multiple of 7)

49 (the difference)
-49 (another known multiple of 7)

0 (there is no remainder, so 119 is, indeed, divisible by 7)

In short, to determine if a number is divisible by a potential factor, you can simply subtract multiples of that factor until you reduce the number to 0. If you can’t arrive at 0, the lowest positive value you can reach is the remainder, and the initial number is not divisible by the other.

For more GMAT prep tips and resources, take a look at all that Veritas Prep has to offer!