Divisibility/Multiples/Factors: Tips and hints

Question

!	This post is a part of the Quant Tips and Hints by Topic Directory focusing on Quant topics and providing examples of how to approach them. Most of the questions are above average difficulty.

DIVISIBILITY
1. Every GMAT divisibility question will tell you in advance that any unknowns represent positive integers (ALL GMAT divisibility questions are limited to positive integers only).

2. On the GMAT when we are told that \(a\) is divisible by \(b\) (or which is the same: "\(a\) is multiple of \(b\)", or "\(b\) is a factor of \(a\)"), we can say that:
(i) \(a\) is an integer;
(ii) \(b\) is an integer;
(iii) \(\frac{a}{b}=integer\).

FACTORS
1. A divisor of an integer \(n\), also called a factor of \(n\), is an integer which evenly divides \(n\) without leaving a remainder. In general, it is said \(m\) is a factor of \(n\), for non-zero integers \(m\) and \(n\), if there exists an integer \(k\) such that \(n = km\).

2. 1 (and -1) are divisors of every integer.

3. Every integer is a divisor of itself.

4. Every integer is a divisor of 0, except, by convention, 0 itself.

5. Numbers divisible by 2 are called even and numbers not divisible by 2 are called odd.

DIVISIBILITY RULES
1. 2 - If the last digit is even, the number is divisible by 2.

2. 3 - If the sum of the digits is divisible by 3, the number is also.

3. 4 - If the last two digits form a number divisible by 4, the number is also.

4. 5 - If the last digit is a 5 or a 0, the number is divisible by 5.

5. 6 - If the number is divisible by both 3 and 2, it is also divisible by 6.

6. 7 - Take the last digit, double it, and subtract it from the rest of the number, if the answer is divisible by 7 (including 0), then the number is divisible by 7.

7. 8 - If the last three digits of a number are divisible by 8, then so is the whole number.

8. 9 - If the sum of the digits is divisible by 9, so is the number.

9. 10 - If the number ends in 0, it is divisible by 10.

10. 11 - If you sum every second digit and then subtract all other digits and the answer is: 0, or is divisible by 11, then the number is divisible by 11.
Example: to see whether 9,488,699 is divisible by 11, sum every second digit: 4+8+9=21, then subtract the sum of other digits: 21-(9+8+6+9)=-11, -11 is divisible by 11, hence 9,488,699 is divisible by 11.

11. 12 - If the number is divisible by both 3 and 4, it is also divisible by 12.

12. 25 - Numbers ending with 00, 25, 50, or 75 represent numbers divisible by 25.

GCD and LCM:
1. The greatest common divisor (GCD), of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.

So GCD can only be positive integer. It should be obvious as greatest factor of two integers can not be negative. For example if -3 is a factor of two integer then 3 is also a factor of these two integers.

2. The lowest common multiple (LCM), of two integers \(a\) and \(b\) is the smallest positive integer that is a multiple both of \(a\) and of \(b\).

So LCM can only be positive integer. It's also quite obvious as if we don not limit LCM to positive integer then LCM won't make sense any more. For example what would be the lowest common multiple of 2 and 3 if LCM could be negative? There is no answer to this question.

3. Divisor of a positive integer cannot be more than that integer (for example 4 doesn't have a divisor more than 4, the largest divisor it has is 4 itself). From this it follows that the greatest common divisor of two positive integers x and y can not be more than x or y.

FINDING THE NUMBER OF FACTORS OF AN INTEGER
First make prime factorization of an integer \(n=a^p*b^q*c^r\), where \(a\), \(b\), and \(c\) are prime factors of \(n\) and \(p\), \(q\), and \(r\) are their powers.

The number of factors of \(n\) will be expressed by the formula \((p+1)(q+1)(r+1)\). NOTE: this will include 1 and n itself.

Example: Finding the number of all factors of 450: \(450=2^1*3^2*5^2\)

Total number of factors of 450 including 1 and 450 itself is \((1+1)*(2+1)*(2+1)=2*3*3=18\) factors.

WHEN THE SUM OR THE DIFFERENCE OF NUMBERS IS A MULTIPLE OF AN INTEGER
1. If integers \(a\) and \(b\) are both multiples of some integer \(k>1\) (divisible by \(k\)), then their sum and difference will also be a multiple of \(k\) (divisible by \(k\)):
Example: \(a=6\) and \(b=9\), both divisible by 3 ---> \(a+b=15\) and \(a-b=-3\), again both divisible by 3.

2. If out of integers \(a\) and \(b\) one is a multiple of some integer \(k>1\) and another is not, then their sum and difference will NOT be a multiple of \(k\) (divisible by \(k\)):
Example: \(a=6\), divisible by 3 and \(b=5\), not divisible by 3 ---> \(a+b=11\) and \(a-b=1\), neither is divisible by 3.

3. If integers \(a\) and \(b\) both are NOT multiples of some integer \(k>1\) (divisible by \(k\)), then their sum and difference may or may not be a multiple of \(k\) (divisible by \(k\)):
Example: \(a=5\) and \(b=4\), neither is divisible by 3 ---> \(a+b=9\), is divisible by 3 and \(a-b=1\), is not divisible by 3;
OR: \(a=6\) and \(b=3\), neither is divisible by 5 ---> \(a+b=9\) and \(a-b=3\), neither is divisible by 5;
OR: \(a=2\) and \(b=2\), neither is divisible by 4 ---> \(a+b=4\) and \(a-b=0\), both are divisible by 4.

This week's PS question
This week's DS Question

Theory on Number Properties: math-number-theory-88376.html

DS Divisibility/Multiples/Factors questions to practice: search.php?search_id=tag&tag_id=354
PS Divisibility/Multiples/Factors questions to practice: search.php?search_id=tag&tag_id=185

Please share your Divisibility tips below and get kudos point. Thank you.

chetan2u · Accepted Answer

Hi,
taking the method used for 7, we can check for some more. lets see till 30..
7 :- Subtract 2 times the last digit from remaining number. Repeat the step if required. If the result is divisible by 7, the original number is also divisible by 7 
13 :- Add 4 times the last digit to the remaining number. Repeat the step if required. If the result is divisible by 13, the original number is also divisible by 13 
15 :- ends with 5 or 0 and sum of the digit is div by 3
16 :- last 4 digits should be div by 16. wil not be required as it itself becomes a long calculation
17 :- Subtract 5 times the last digit from remaining number. Repeat the step if required. If the result is divisible by 17, the original number is also divisible by 17 
18 :- should be even number and the sum of digits div by 9..
19 Add 2 times the last digit to the remaining number. Repeat the step if required. If the result is divisible by 19, the original number is also divisible by 19 
23 Add 7 times the last digit to the remaining number. Repeat the step if required. If the result is divisible by 23, the original number is also divisible by 23 
29 Add 3 times the last digit to the remaining number. Repeat the step if required. If the result is divisible by 29, the original number is also divisible by 29

Although you will have to remember the numeric value to be added/subtracted in 13,17,19,23,29,31...etc.. 
One pattern can be kept in mind .. anything ending in 1 and 3 will have addition and 7 ,9 will have subtraction...

bazc · Answer

Tip.

1)
For checking divisibility by ‘x’, which is of the format of 10^n – 1, sum of blocks of size ‘n’ needs to be checked (Blocks should be considered from the least significant digit ie the right side). If the sum is divisible by x, then the number is divisible by x.
Example: Check if a number (N = abcdefgh) is divisible by 9
9 is 10^1 – 1
Sum of digits is done 1 at a time = a + b + c + d + e + f + g + h = X
If X is divisible by 9, N is divisible by 9
Also, N is divisible by all factors of 9. Hence the same test works for 3.

Similarly, can be done for 99, 999, etc.

2)
For checking divisibility by ‘x’, which is of the format of 10^n + 1, alternating sum of blocks of size ‘n’ needs to be checked (Blocks should be considered from the least significant digit ie the right side). If the alternating sum is divisible by x, then the number is divisible by x.
(Alternating Sum: Sum of a given set of numbers with alternating + and – signs. Since we are using it to just check the divisibility, the order in which + and – signs are used is of no importance.)

Example:
Check if a number (N = abcdefgh) is divisible by 101
101 is 102 + 1
Alternating sum of digits is done 2 at a time = ab - cd + ef - gh = X 
If X is divisible by 101, N is divisible by 101

Dhwanii · Answer

Num ending w 9 have addition, you have written subtraction in the last statement

tickledpink001 · Answer

Please can someone help with this -

The rule is that any n consecutive integers are divisible by n!- so how is (x-1)x(x+1) divisible by 24 (if x is odd) and not 6 (3! since they are 3 consecutive integers?)

thanks

Bunuel · Answer

If x is odd, then (x - 1) and (x + 1) are consecutive even integers, making one of them a multiple of 4. Thus, (x - 1)(x + 1) must be divisible by 2*4 = 8. Additionally, since (x - 1), x, and (x + 1) are three consecutive integers, one of them must be a multiple of 3. Therefore, (x - 1)x(x + 1) must be divisible by 8*3 = 24 for any odd value of x.

Hope it helps.

tickledpink001 · Answer

Thanks Bunuel.

I'm still a bit unclear - I understand both rules and how (x - 1)x(x + 1) must be divisible by 8*3 = 24 for any odd value of x, but what I'm trying to understand is this-

Given we know that (x - 1)x(x + 1) are 3 consecutive integers, shouldn't the product of these terms should first and foremost be divisible by 3! only? and subsequently therefore any other multiple of 3! ?

Bunuel · Answer

Yes, the product of three consecutive integers, like (x - 1)x(x + 1), is always divisible by 3! = 6. However, when the middle integer x is odd, the product becomes divisible by 24, a multiple of 6. Not sure what is the source of the confusion here.

bumpbot · Answer

Hello from the GMAT Club BumpBot!

Thanks to another GMAT Club member, I have just discovered this valuable topic, yet it had no discussion for over a year. I am now bumping it up - doing my job. I think you may find it valuable (esp those replies with Kudos).

Want to see all other topics I dig out? Follow me (click follow button on profile). You will receive a summary of all topics I bump in your profile area as well as via email.

Divisibility/Multiples/Factors: Tips and hints

Prep Toolkit

Top 5 GMAT Debrief Videos

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia

My Rewards