9. Divisibility & Primes

Question 1

What are the basic arithmetic rules for integers?

Answer 1

(1) Sum: the sum of two integers is always an integer
(2) Subtraction: the difference of two integers is always an integer
(3) Multiplication: the product of two integers is always an integer
(4) Division: the result of dividing two integers is sometimes an integer

Question 2

What does Divisible mean?

Answer 2

If any integer x divided by another number y yields an integer, then x is said to be divisible by y

e.g. 8 is divisible by 2 because 8/2 = 4

Question 3

How do you determine if x + y is divisible by y?

Answer 3

In order for x + y to be divisible by y, x itself must be divisible by y

Question 4

What is the only even prime number?

Answer 4

2

Question 5

What integers are not prime numbers?

Answer 5

0 and 1

Question 6

What are the divisibility rules for small integers (ie the counting numbers 2-10)?

Answer 6

An integer is divisible by:

• 2: if the integer is even (e.g. 8)
• 3: if the sum of the integer’s digits is a multiple of 3 (e.g. 72)
• 4: if the integer is divisible by 2 twice; or if the last two digits are divisible by 4 (e.g. 28)
• 5: if the integer ends in 0 or 5 (e.g. 75 or 80)
• 6: if sum of digits is multiple of 3 and number is even (ie the integer is divisible by both 2 and 3 (e.g. 48)
• 8: if the integer is divisible by 2 three times, or if the last three digits are divisible by 8
• 9: if the sum of the integer’s digits is a multiple of 9 (e.g. 144)
• 10: if the integer ends in 0 (e.g. 8,730)

Question 7

What is a factor?

Answer 7

• Factors = divisors = positive integers that divide evenly into an integer
• Factors are equal to or smaller than the integer in question (ie an integer has a limited number of factors)
• An integer is always both a factor and a multiple of itself, and 1 is a factor of every integer

*FEWER FACTORS, MORE MULTIPLES

Question 8

What does Divisible mean?

Answer 8

If an integer x divided by another number y yields an integer, then x is said to be divisible by y

Example: 12 divided by 3 yields the integer 4. Therefore, 12 is divisible by 3

Question 9

What is a multiple?

Answer 9

• Multiples are integers formed by multiplying some integer by any other integer
• An integer has an infinite number of multiples
• FEWER FACTORS, MORE MULTIPLES
• NOTE: the GMAT does not test negative multiples directly

Question 10

What are Factor Pairs?

Answer 10

A list of all the pairs of factors of a particular number

Factor pairs of 60

1. Label two columns “small” and “large”
2. Start with 1 and 60
3. Next small number 2 because it is a factor of 60
4. Repeat process until the numbers in the small and large columns run into each other

1, 60
2, 30
3, 20
4, 15
5, 12
6, 10

Question 11

What is the shortcut for determining the number of factors of a number (e.g. 180)?

Answer 11

(1) Perform prime factorization of the integer
(2) Separate the exponents of each prime number into brackets and add 1
(3) Multiply them

Example:
Prime Factorization: 180 = 2 * 2 * 3 * 3 * 5 = (2^2) * (3^2 ) * (5^1)
Separate: (2+1), (2+1), (1+1)  
Multiply: (2+1)(2+1)(1+1) = 18 
180 has 18 factors

Question 12

What are the different ways the GMAT can phrase information about divisibility? (e.g. 12 and 3)

Answer 12

• 12 is divisible by 3
• 12 is a multiple of 3
• 12/3 is an integer
• 12 = 3n, where n is an integer
• 12 items can be shared among 3 people so that each has the same number of items
• 3 is a divisor of 12; 3 is a factor of 12
• 3 divides 12
• 12/3 yields a remainder of 0
• 3 goes into 12 evenly

Question 13

What happens if you add or subtract two multiples of N? (e.g. 35 + 21 = 56, 35 – 21 = 14)

Answer 13

• If you add or subtract two multiples of N, the result is a multiple of N
• Disguised: if N is a divisor of x and of y, then N is a divisor of x + y

(57) + (37) = 7(5 + 3) = 8 * 7
(57) – (37) = 7(5 – 3) = 2 * 7

Question 14

What are Prime Numbers?

Answer 14

• A positive integer with exactly two factors: 1 and itself
• The number 1 does not qualify as prime because it has only one factor (itself)
• The number 2 is the smallest prime number and the only even prime number

Memorize! 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

NOTE: Every positive integer can be placed into one of two categories – prime or not prime

Question 15

What are the defining characteristics of prime numbers?

Answer 15

(1) A positive integer with exactly two factors: 1 and itself
(2) There is an infinite number of prime numbers
(3) There is no simple pattern in the prime numbers
(4) Positive integers with only two factors must be prime, and positive integers with more than two factors are never prime (note that 1 is not prime)
(5) The number 2 is the smallest prime number and the only even prime number

Question 16

What is the Prime Factorization?

Answer 16

• A number expressed as a product of prime numbers
• Every number has a unique prime factorization
• 60 is the only number that can be written 2 x 2 x 3 x 5

*Note: Your first instinct on divisibility problems should be to break numbers down into their prime factors. For large numbers, generally start with the small prime factor

Question 17

What are the different situations in which you might use prime factorization?

Answer 17

(1) Factors: all of the factors of an integer can be found by building all the possible products of prime factors
(2) Determining whether one number is divisible by another number
(3) Determining the greatest common factor of two numbers
(4) Reducing fractions
(5) Finding the least common multiple of two or more numbers
(6) Simplifying square roots
(7) Determining the exponent on one side of an equation with integer constraints

Question 18

What rule should you remember when a problem states or assumes that a number is an integer?

Answer 18

-You may need to use prime factorization to solve the problem

Question 19

What is a Factor Tree?

Answer 19

• Use the factor tree to break down any number into its prime factors
• Circle prime numbers as you go

Question 20

What is the Factor Foundation Rule?

Answer 20

If a is a factor of b and b is a factor of c, then a is also a factor of c. In other words, “any integer is divisible by the factors of its factors”

Example: 100 is divisible by 20, and 20 is divisible by 4, so 100 is divisible by 4 as well

Question 21

What are the divisibility rules with respect to addition and subtraction?

Answer 21

For the following rules, assume that N is an integer

(1) If you add or subtract multiples of an integer, you get another multiple of that integer
(2) If you add a multiple of N to a non-multiple of N, the result is a non-multiple of N (the same holds true for subtraction)
e. g. 18 – 10 = 8 OR (multiple of 3) – (non-multiple of 3) = (non-multiple of 3)
(3) If you add two non-multiples of N, the result could be either a multiple of N or a non-multiple of N
e. g. 19 + 13 = 32 OR (non-multiple of 3) + (non-multiple of 3) = (non-multiple of 3)
e. g. 19 + 14 = 33 OR (non-multiple of 3) + (non-multiple of 3) = (multiple of 3)

Question 22

Is N divisible by 7?

(1) N = x – y, where x and y are integers
(2) x is divisible by 7, and y is not divisible by 7

Answer 22

Answer C. Divisibility & Primes.

(1) INSUFFICIENT. N is the difference between two integers (x and y), but it does not tell you anything about whether x or y is divisible by 7.
(2) INSUFFICIENT. Tells us nothing about N.
(C) SUFFICIENT. The combined statements tell you that x is a multiple of 7, but y is not a multiple of 7. The difference between x and y can NEVER be divisible by 7 if x is divisible by 7 but y is not

Question 23

What is the Greatest Common Factor? (e.g. 12 and 30)

Answer 23

• Greatest Common FACTOR = the largest factor of two (or more) integers
• Factors will be equal to or smaller than the starting integers
• The GCF of 12 and 30 is 6 because 6 is the largest number that goes into both 12 and 30.

Question 24

What is the Least Common Multiple? (e.g. 6 and 9)

Answer 24

• Least Common MULTIPLE = smallest multiple of two (or more) integers
• Multiples will be equal to or larger than the starting integers
• When two numbers do not share prime factors, their LCM is just their product
• However, when two numbers share prime factors, their LCM will be smaller than their product

General: the LCM of A (e.g. 6) and B (e.g. 9) contains only as many of a prime factor as you see it appear in either A or B separately.

Consider the LCM of 6 and 9. 6 has one 2 and 9 has no 2’s, so the LCM must have one 2. 6 has one 3 and 9 has two 3’s, so the LCM must have two 3’s. Thus, the LCM = 2 * 3 * 3 = 18

Question 25

What is the best way to find the GCF or LCM? (e.g. 30 and 24)

Answer 25

(1) Factor the numbers into primes
30 = 2 * 3 * 5
24 = 2 * 2 * 2 * 3

(2) Create a Venn Diagram
(3) Place each common factor, including copies of common factors appearing more than once, into the shared area of the diagram
(4) Place the remaining (non-common) factors into the non-shared areas

GFG = product of primes in the overlapping region = 2 * 3 = 6
LCM = product of all primes in the diagram = 5 * 2 * 3 * 2 * 2 = 120

Question 26

What is the GCF and LCM if two integers have no primes in common?

Answer 26

GCF = 1
LCM = the product of the two integers

Question 27

How do you determine the GCF and LCM of large numbers (e.g. 100, 140, 250)?

Answer 27

Use prime columns.

(1) Calculate the prime factors of each integer
100 = 2^2 * 5^2
140 = 2^2 * 5 * 7
250 = 2 * 5^3

(2) Create a column for each prime factor found within any of the integers
(3) Create a row for each integer
(4) In each cell of the table, place the prime factor raised to a power. This power counts how many copies of the column’s prime factor appear in the prime box of the row’s integer

100 = 2^2 * 5^2 * 7^0
140 = 2^2 * 5^1 * 7^1
250 = 2^1 * 5^3 * 7^0

GCF = lowest count of each prime factor found across ALL integers = 2^1 * 5^1 * 7^0 = 10
*This counts all of the shared primes

LCM = highest count of each prime factor found across ALL integers = 2^2 * 5^3 * 7^1 = 3,500
*This counts all the primes less the shared primes

Question 28

What are the general properties of the GCF and LCM?

Answer 28

(1) (GCF of m and n) * (LCM of m and n) = m * n

(2) GCF of m and n cannot be larger than the difference between m and n
e. g. assume GCF of m and n is 12. Thus, m and n are both multiple of 12. Consecutive multiples of 12 are 12 units apart on the number line. Therefore, m and n cannot be less than 12 units apart, or else they would not be multiples of 12

(3) Consecutive multiples of n have a GCF of n
e. g. 8 and 12 are consecutive multiples of 4. Thus, 4 is a common factor of both numbers. But 8 and 12 are exactly 4 apart. Thus, 4 is the greatest possible common factor of 8 and 12

Question 29

Is the integer z divisible by 6?

(1) The greatest common factor of z and 12 is 3
(2) The greatest common factor of z and 15 is 15

Answer 29

Answer A. Divisibility & Primes. Use the prime columns method to determine what conclusions can be drawn from each of these statements.
(1) SUFFICIENT. Notice that the GCF of 12 and z contains a 3. Since the GCF contains each prime factor to the power it appears the least, you know that z must also contain at least one 3. Therefore, z is divisible by 3. Notice also that the GCF contains no 2’s. Since 12 contains two 2’s, z must not contain any 2’s. Therefore, z is not divisible by 2. Since z is not divisible by 2, it cannot be divisible by 6.
z = 2^0 * 3^1
12 = 2^2 * 3^1

(2) INSUFFCIIENT. The GCF of 15 and z contains a 3. Since the GCF contains each prime factor to the power that appears least, you know that z must also contain at least one 3. Therefore, z is divisible by 3. However, this does not tell you whether z contains any 2’s. You cannot tell whether or not z has a 2 in its prime factorization.
z = 3^1 * 5^1
15 = 3^1 * 5^1

Question 30

If the LCM of a and 12 is 36, what are the possible values of a?

Answer 30

9, 18 and 36 are the only possible values of a. Notice that a cannot be larger than 36. The LCM of two or more integers is always at least as large as any of the integers. Therefore, the maximum value of a is 36.

Next, find the prime factorization of 36 = 2 * 2 * 3 * 3. Notice that the LCM of 12 and a contains two 2’s. Since the LCM contains each prime factor to the power it appears the most, and since 12 also contains two 2’s, you know that a cannot contain more than two 2’s. It does not necessarily need to contain any 2’s, so a can contain zero, one or two 2’s
a = ≤2^2 * 3^2
12 = 2^2 * 3^1

Finally, observe that the LCM of 12 and a contains two 3’s. But 12 only contains one 3. The 3^2 factor in the LCM must have come from the prime factorization of a. Thus, you know that a contains exactly two 3’s.

a could be 3 * 3 = 9, 3 * 3 * 2 = 18, or 3 * 3 * 2 * 2 = 36

Question 31

What are the three basic rules of factors?

Answer 31

(1) FACTOR FOUNDATION RULE: If a is a factor of b and b is a factor of c, then a is also a factor of c. In other words, “every number is divisible by the factors of its factors.”

Example: 100 is divisible by 20, and 20 is divisible by 4, so 100 is divisible by 4 as well.

(2) PRIMES: If d is divisible by two different prime numbers e and f, then d is also divisible by e x f. You can let e and f be the same prime, as long as there are at least two copies of that prime in d’s factor tree

Example: if 20 is divisible by 2 and by 5, then 20 is also divisible by 10 = 5 x 2. Or if 20 has two 2’s as prime factors, then 20 is divisible by 4 = 2 x 2

(3) COMBINATIONS: All of the factors of a number (except for 1) can be built with different combinations of its prime factors. To say this another way, every factor of a number (again, except 1) can be expressed as the product of a set of its prime factors

Example: 30 = 2 x 3 x 5. Factors are 1, 2, 3, 5, 6 (2 * 3), 10 (2 * 5), 15 (3 * 5) and 30 (2 * 3 * 5)

**Divisibility travels up and down the factor tree. 150 is divisible by 15 and by 10, so 150 is also divisible by everything that 10 and 15 are divisible by (e.g. 2, 3, 5)

Question 32

Factor tree of a variable. How do you determine whether or not an unknown number is divisible by some other given number (e.g. given x is divisible by 6, determine whether or not (i) x is divisible by 3, (ii) x is even (iii) x is divisible by 12)?

Answer 32

Use a factor tree with a variable on top and a question mark below to remind yourself what you do not know. Compare this factor tree to that of the number in question.

(i) x must be divisible by 3 because 6 is divisible by 2 x 3
(ii) x must be even because 6 is divisible by 2, so you know that x is divisible by 2 as well. Since x is divisible by 2, x is even
(iii) x could be divisible by 12 but it is unclear. Compare the factor tree of x and 12. x has prime factors 2 and 3. 12 has prime factors 2, 2 and 3. To guarantee that x is divisible by 12, you need to know for sure that x has two 2’s and one 3 among its prime factors

Question 33

Factors of X with no common primes. How do you determine whether or not an unknown number is divisible by some other given number if they do not share any prime numbers (e.g. given x is divisible by 3 and 10, determine whether or not (i) x is divisible by 2, (ii) x is divisible by 15 (iii) x is divisible by 45)?

Answer 33

First, create two factor trees to represent the given information, with x at the top of each one. Initially, you must always write two given facts about a variable separately. When the primes from two trees are all different, you can combine all the primes on one tree with one question mark.

(i) x must be divisible by 2 because 10 is divisible by 2
(ii) x must be divisible by 15 because it shares all of its prime factors (3 and 5) with x
(iii) x could be divisible by 45. x has prime factors 3, 2, and 5. 45 has prime factors 3, 3, 5. There needs to be one additional 3 in order to guarantee this statement

Question 34

Factors of X with primes in common. How do you determine whether or not an unknown number is divisible by some other given number if they share some prime numbers (e.g. given x is divisible by 6 and 9, determine whether or not x is divisible by 54)

Answer 34

If x is divisible by A and B, then x is divisible by the LCM of A and B, no matter what.

If two factor trees contain overlapping primes, combine the two trees of x, eliminating the overlap (do not double count!). You know that x is divisible by the LCM of the factors. Since 6 and 9 share primes, you combine to the LCM of 18 and create a tree under “x” of 18 and a question mark. Underneath 18, you combine the primes and drop the overlap, such that 18 splits into 2, 3, and 3.

54 has primes of 2, 3, 3 and 3. Thus, x could be divisible by 54, but we do not know because we are missing one 3.

Question 35

Factors of X and Y. What can you conclude given X is divisible by 6 and Y is divisible by 9?

Answer 35

If the facts are about two different variables, X and Y, then the facts do not overlap. X has its own factor tree with primes 2, 3 and ?. Y has its own factor tree with primes 3, 3, and ?.

You can conclude that XY is divisible by 54, which is further broken down into 6 and 9. Thus, XY contains primes 2, 3, 3 and 3

Question 36

What does the following statement imply: “m/2 is NOT an even integer”?

Answer 36

This does NOT mean that m/2 is an odd integer! Rather, it may be that m/2 is not an integer at all

Question 37

If you add two non-multiples of N, what is the result?

Answer 37

The result could be either a multiple of N or a non-multiple of N. We can’t tell without checking the specific numbers!

Example:
If you add or subtract two (or more) multiples of N, the result will also be a multiple of N. 16 + 12 = 28. (Multiple of 4) + (Multiple of 4) = (Multiple of 4)

If you add (or subtract) a multiple of N to (from) a non-multiple of N, the result is a non-multiple of N. 16 – 6 = 10. (Multiple of 4) – (Non-Multiple of 4) = (Non-Multiple of 4)

Question 38

How do you determine the number of different factors for a large number (e.g. 2,000)?

Answer 38

First, factor the number into its primes. 2,000 = 2^4 * 5^3
Consider each prime factor separately. (2) Because the prime factorization of 2,000 contains four 2’s, there are five possibilities for the number of 2’s in any factor of 2,000: none, one, two, three or four. (5) There are three 5’s so there are four possibilities for the number of 5’s in a factor of 2,000: none, one, two, or three.

In general, if a prime factor appears to the Nth power, then there are (N + 1) possibilities for the occurrences of that prime factor. This is true for each of the individual prime factors of any number.

Since the choice for the number of 2’s and the number of 5’s are two individual decisions and independent of one another, the total number of factors of 2,000 must be (4 + 1)(3 + 1) = 5 * 4 = 20 different factors (due to the fundamental counting principle)

Question 39

How many different factors does 9,450 have?

Answer 39

(1) Factor the number into primes
9,450 = 2^1 * 3^3 * 5^2 * 7^1

(2) Multiply each exponent plus one
(1 + 1)(3 + 1)(2 + 1)(1 + 1) = 2 * 4 * 3 * 2 = 48 different factors

Question 40

How many unique prime factors of 1,400 are there?

Answer 40

• Equivalently, how many prime numbers are factors of 252
• Count each repeated prime factor only ONCE

Prime factorization = 2 * 2 * 2 * 5 * 5 * 7 = 2^3 * 5^2 * 7

In this example, 2, 5, and 7 are distinct, so there are 3 different prime factors

Question 41

How is the length of an integer defined?

Answer 41

The total number of primes (not necessarily distinct) that, when multiplied together, equal that integer

Question 42

What is the length of 1,400?

Answer 42

Add the exponents of each prime factor.

Three 3’s + two 5’s + one 7 = 3 + 2 + 1 = 6

Question 43

How many total factors of 1,400 are there?

Answer 43

Includes all factors, not necessarily just prime factors
-Use advanced technique

Prime factorization = 2^3 * 5^2 * 7
Number of factors = (3 + 1)(2 + 1)(1 + 1) = 4 * 3 * 2 = 24

Question 44

What are two defining characteristics of perfect squares?

Answer 44

(1) All perfect squares have an odd number of total factors; all other non-square integers have an even number of factors (i.e. any number that is not a perfect square will never have an odd number of factors)
(2) The prime factorization of a perfect square contains only even powers of primes; if a number’s prime factorization contains any odd powers of primes, then the number is not a perfect square
e. g. 144 = 2^4 * 3^2 vs 132,300 = 2^2 * 3^3 * 5^2 * 7^2

*NOTE: the same logic extends to perfect cubes and other perfect powers

Question 45

If k^3 is divisible by 240, what is the least possible value of integer k?
A. 12
B. 30
C. 60
D. 90
E. 120

Answer 45

Answer C. The prime box of k^3 contains the factors of 240, which are 2, 2, 2, 2, 3 and 5. You know that the prime factors of k^3 should be the prime factors of k appearing in sets of three, so you should distribute the prime factors of k^3 into three columns to represent the prime factors of k
k, k, k
2, 2, 2
2, ?, ?
3, ?, ?
5, ?, ?

There is a complete set of three 2’s in the prime box of k^3, so k must have a factor of 2. However, there is a fourth 2 left over. That additional factor of 2 must be from k as well, so assign it to one of the component k columns. There is an incomplete set of 3’s in the prime box of k^3, but you can still infer that k has a factor of 3; otherwise, k^3 would not have any. Similarly, k^3 has a single 5 in its prime box, but that factor must be one of the factors of k as well.

Thus, k has 2, 2, 3, and 5 in its prime box, so k must be a multiple of 60

Question 46

What characteristics do factorials have with respect to divisibility?

Answer 46

N! is a multiple of all the integers from 1 to N

E.g. 10! + 7 must be a multiple of 7, because both 10! And 7 are multiples of 7
E.g. 10! + 15 must be a multiple of 15, because 10! Is divisible by 5 and 3, and 15 is divisible by 5 and 3

Question 47

What is the dividend?

Answer 47

• Number being divided (numerator)

- In the operation 22/4, 22 is the dividend

Question 48

What is the divisor?

Answer 48

• Number that is dividing (denominator)

- In the operation 22/4, 4 is the divisor

Question 49

What is the quotient?

Answer 49

• Number of times that the divisor goes into the dividend completely (always an integer)
• In the operation 22/4, the quotient is 5, because 4 goes into 22 evenly a total of five times (4*5 = 20). The left over portion, in this case 2, is the remainder.

Question 50

What is the remainder?

Answer 50

• What is left over if the dividend is not divisible by the divisor
• (10/3) or 10 ÷ 3 = 3 with a remainder of 1. 3 goes into 10 three times, for a total of 3 * 3 = 9, and 1 is left over. The 1 is not evenly divisible by the divisor, 3, so that 1 is called the remainder.

Question 51

What is the relationship between the quotient and the remainder?

Answer 51

When a positive integer is divided by another positive integer:

Dividend = Quotient * Divisor + Remainder
Dividend/Divisor = Quotient + Remainder/Divisor

Question 52

What is the quotient and remainder when 3 is divided by 5?

Answer 52

Quotient = 0
Remainder = 3

Question 53

What are the three ways to express remainders?

Answer 53

(1) Integer
(2) Fraction
(3) Decimal

Question 54

When positive integer A is divided by positive integer B, the result is 4.35. Which of the following could be the remainder when A is divided by B? (Bonus: find a set of values for A and B)
A. 13
B. 14
C. 15
D. 16
E. 17

Answer 54

Answer B. When a GMAT question refers to a remainder, it is referring to the integer form of the remainder. The value of the below relationship comes from a hidden constraint that R and B must both be integers

0.35 = Remainder/Divisor = R/B 
35/100 = R/B
7/20 = R/B
7B = 20R

In order for this equation to involve only integers, you know that the prime factors on the left side of the equation must equal the prime factors on the right side of the equation. You know that the divisor (B) MUST be a multiple of 20, and more importantly, the remainder (R) MUST be a multiple of 7. Answer B is the only option that is a multiple of 7

7/20 = 14/B
B = (14)(20) / (7) = 40

A/B = 4.35
A/40 = 4.35
A = 174

Dividend/Divisor = Quotient + Remainder/Divisor
174/40 = 4 + 14/40

Question 55

When positive integer x is divided by 5, the remainder is 2. When positive integer y is divided by 4, the remainder is 1. Which of the following values CANNOT be the sum of x + y?
A. 12
B. 13
C. 14
D. 16
E. 21

Answer 55

Answer C. To answer this question efficiently, you will need to list out possible values of x and y. Then you need to figure one number from each set to sum to the answer choices

X = 2, 7, 12, 17
Y = 1, 5, 9, 13

A. 12 = 7 + 5
B. 13 = 12 + 1
C. 14 = ?
D. 16 = 7 + 9
E. 21 = 12 + 9

The correct answer is C. There is no way for X + Y to equal 14

Question 56

If a/b yields a remainder of 5, c/d yields a remainder of 8, and a, b, c and d are all integers, what is the smallest possible value for b + d?

Answer 56

Since the remainder must be smaller than the divisor, 5 must be smaller than b. b must be an integer, so b is at least 6. Similarly, 8 must be smaller than d, and d must be an integer, so d must be at least 9. Therefore, the smallest possible value for b + d is 6 + 9 = 15

Question 57

What two rules apply to arithmetic with remainders if you have the same divisor throughout?

Answer 57

(1) You can add and subtract remainders directly, as long as you correct excess or negative remainders
(2) You can multiply remainders, as long as you correct excess remainders at the end

Question 58

If x leaves a remainder of 4 after division by 7, and y leaves a remainder of 2 after division by 7, then what is the remainder of x + y divided by 7?

Answer 58

4 + 2 = 6 after division by 7

Question 59

If x leaves a remainder of 4 after division by 7, and z leaves a remainder of 5 after division by 7, then what is the remainder of x + z divided by 7?

Answer 59

Adding the remainders together yields 9. This number is too high. The remainder must be non-negative and less than 7. You can take an additional 7 out of the remainder, because 7 is the excess portion

Thus, x + z leaves a remainder of 9 – 7 = 2 after division by 7

Question 60

If x leaves a remainder of 4 after division by 7, and z leaves a remainder of 5 after division by 7, then what is the remainder of x – z divided by 7?

Answer 60

Subtracting the remainders gives us -1, which is an unacceptable remainder (it must be non-negative). In this case, add an extra 7 to see that x – z leaves a remainder of 6 after division by 7

Question 61

If x leaves a remainder of 4 after division by 7, and z leaves a remainder of 5 after division by 7, then what is the remainder of xz divided by 7?

Answer 61

4 * 5 = 20. Two additional 7’s can be taken out of this remainder, so xz will have a remainder of 6 upon division by 7

Question 62

Ch 2, Q 28. 28. If 7x is a multiple of 210, must x be a multiple of 12?

Answer 62

No, but x could be a multiple of 12.

For x to be a multiple of 12, it would need to contain all the prime factors of 12, which are 2, 2 and 3. If 7x is a multiple of 210, it contains the prime factors 2, 3, 5 and 7. Must divide out the 7 because we are only concerned with x. We are missing one 2. Thus, it could be a multiple of 12, but does not have to be.

Question 63

Ch 2, Q 39. If n is the product of 2, 3 and a two-digit prime number, how many of its factors are greater than 6?

Answer 63

There are four factors larger than 6. We can infer that the answer will be the same regardless of which 2-digit prime we pick. So for simplicity, let’s pick the smallest and most familiar one: 11.

If n = 2 * 3 * 11, the factors are:
1, 66
2, 33
3, 22
6, 11

Question 64

Ch 2, Q 41. 4, 21, and 55 are factors of n. Does 154 divide n?

Answer 64

154 divides n. Draw three trees for n. There are no overlapping primes, so you can combine the trees into one. n has prime factors of 2, 2, 3, 7, 5, 11 and ?.

154 has prime factors of 2, 7, and 11. Thus, 154 divides n.

Question 65

Ch 2, Q 42. If n is divisible by 196 and by 15, is 270 a factor of n?

Answer 65

270 could be a factor of n. Draw two trees for n. There are no overlapping primes, so you can combine the trees into one. n has prime factors of 2, 2, 7, 7, 3, 5, ?.
270 has prime factors of 3, 3, 3, 2, and 5. There are two missing 3’s.

Question 66

Number Properties Guide, Ch 1, Q 2. If 80 is a factor of r, is 15 a factor of r?

Answer 66

CANNOT BE DETERMINED. If r is divisible by 80, its prime factors include 2, 2, 2, 2, and 5. Therefore, any integer that can be constructed as a product of any of these prime factors is also a factor of r.

15 = 3 * 5. Since you do not know whether the prime factor 3 is in the prime box, you cannot determine whether 15 is a factor of r.

As numerical examples, you could take r = 80, in which case 15 is NOT a factor of r, or r = 240, in which case 15 IS a factor of r

Question 67

Number Properties Guide, Ch 1, Q 4. If j is divisible by 12 and 10, is j divisible by 24?

Answer 67

CANNOT BE DETERMINED. Set up three factor trees for j. The first will include 2, 2, 3 and ?, the second will include 2, 5, and ?, and the final tree will be a combination of the unique prime factors, 2, 2, 3, 5, and ?

If j is divisible by 12 and by 10, its prime factors include 2, 2, 3 and 5. What is the minimum number of 2’s necessary to create 12 or 10? You need two 2’s to create 12. You could use one of those same 2’s to create the 10. Therefore, there are only two 2’s that are definitely in the prime factorization of j, because the 2 in the prime factorization of 10 may be redundant that is, it may be the same 2 as one of the 2’s in the prime factorization of 12.

24 = 2 * 2 * 2 * 3. The prime factor tree of j contains at least two 2’s and could contain more. The number 24 requires three 2’s. Therefore, you may or may not be able to create 24 from j’s prime tree; 24 is not necessarily a factor of j

Question 68

Number Properties Guide, Ch 1, Q 9. A skeet shooting competition awards prizes for each round as follows: the first place winner receives 11 points, the second place finisher receives 7 points, the third place finisher receives 5 points, and the fourth place finisher receives 2 points. No other prizes are awarded. John competes in several rounds of the skeet shooting competition and receives points every time he competes. If the product of all of the points he receives equals 84,700, in how many rounds does he participate?

Answer 68

7 rounds. Notice that the rounds for scoring first, second, third and fourth place in the competition are all prime numbers. Also notice that the product of all of the scores that John received is known. Therefore, if you simply take the prime factorization of the product of his scores, you can determine what scores he received and how many scores he received.

84,700 = 847 * 100 = 7 * 121 * 2 * 2 * 5 * 5 = 7 * 11 * 11 * 2 * 2 * 5 * 5

Thus, John received first place twice (11 points each), second place once (7 points each), third place twice (5 points each), and fourth place twice (2 points each). He received a prize 7 times, so he competed 7 times

Question 69

Number Properties, Ch 6, Q 2. a, b, and c are positive integers greater than 1. If a < b < c and abc = 286, what is c – b?

Answer 69

2. Take the prime factorization of 286 = 143 * 2 = 13 * 11 * 2. There are a total of 3 integers in this product. Furthermore, a, b, and c must each be larger than one. Thus, one of the prime factors must equal a, one of the prime factors must equal b, and one of the prime factors must equal c. You know from the problem that a < b < c, so a must equal 2, b must equal 11, and c must equal 13

13 – 11 = 2

Question 70

Number Properties, Ch 6, Q 3. All of the following have the same set of unique prime factors EXCEPT:
A. 420 
B. 490
C. 560
D. 700
E. 980

Answer 70

Answer A. Take the prime factorization of each answer choice and not the unique prime factors.

A. 420 = 3 * 7 * 2 * 2 * 5 (unique primes: 2, 3, 5, 7)
B. 490 = 7 * 7 * 2 * 5 (unique primes: 2, 5, 7)
C. 560 = 7 * 2 * 2 * 2 * 2 * 5 (unique primes: 2, 5, 7)
D. 700 = 7 * 2 * 5 * 2 * 5 (unique primes: 2, 5, 7)
E. 980 = 7 * 7 * 2 * 2 * 5 (unique primes: 2, 5, 7)

Question 71

Number Properties, Ch 6, Q 4. Is p divisible by 168?

(1) p is divisible by 14
(2) p is divisible by 12

Answer 71

Answer E. Divisibility & Primes. 168 = 2^3 * 3 * 7. The question can be rephrased to “are there at least three 2’s, one 3, and one 7 in the prime box of p?”

(1) INSUFFICIENT. p = 2 * 7 * ???. You know that p has at least a 2 and a 7 in its prime box. However, you do not know anything else about the possible prime factors in p, so you cannot determine whether p is divisible by 168.
(2) INSUFFICIENT. p = 2 * 2 * 3 * ???. You know that p has at least two 2’s and one 3 in its prime box. However, you do not know anything else about p, so you cannot determine whether p is divisible by 168.
(C) INSUFFICIENT. Note that you cannot simply combine the primes from the two prime boxes. Consider the number 84, which is divisible by both 14 and 12. 84 = 2 * 2 * 3 * 7, so you are missing a needed 2. Both statements mention that p contains at least one 2. It is possible that these statements are referring to the same 2. You have been given redundant information. You have to eliminate the redundant 2 when you combine the two views of p’s prime box. Given both statements, you only know that p has two 2’s, a 3 and a 7 in its prime box

Question 72

Number Properties, Ch 6, Q 5. Is pq divisible by 168?

(1) p is divisible by 14
(2) q is divisible by 12

Answer 72

Answer C. Divisibility & Primes. 168 = 2^3 * 3 * 7. The question can be rephrased to “are there at least three 2’s, one 3, and one 7 in the prime box of pq?” q has been introduced, and you are now told that q is divided by 12 (rather than p). Because of this change, the information in the two statements is no longer redundant. There is no overlap between the prime boxes, because the prime boxes belong to different variables, p and q.

(1) INSUFFICIENT. p = 2 * 7 * ???.
(2) INSUFFICIENT. q = 2 * 2 * 3 * ???.
(C) SUFFICIENT. When you combine the statements, you combine the prime boxes without removing any overlap, because there is no such overlap. As a result, you know that the product pq contains at least three 2’s, one 3, and one 7. Therefore, pq is divisible by 168.

Question 73

Number Properties, Ch 6, Q 6. What is the greatest common factor of x and y?

(1) x and y are both divisible by 4.
(2) x – y = 4

Answer 73

Answer C. Divisibility & Primes.

(1) INSUFFICIENT. x and y are both divisible by 4, but that does not tell you the GCF of x and y. For example, if x = 16 and y = 20, then GCF = 4. However, if x = 16 and y = 32, then GCF = 16
(2) INSUFFICIENT. This does not tell you the GCF of x and y. For example, if x = 1 and y = 5, then the GCF = 1. However, if x = 16 and y = 20, then the GCF is 4
(C) SUFFICIENT. x and y are multiples of 4 and are 4 apart on the number line. Therefore, x and y are consecutive multiples of 4. RULE: Consecutive multiples of n have a GCF of n. Since x and y are consecutive multiples of 4, their GCF is 4.

Takeaways:
-Consecutive multiples of n have a GCF of n

Question 74

Number Properties, Ch 6, Q 7. What is the value of integer x?

(1) The least common multiple of x and 45 is 225
(2) The least common multiple of x and 20 is 300

Answer 74

Answer C. Divisibility & Primes. Try to determine the value of x using the LCM of x and certain other integers

(1) INSUFFICIENT. x and 45 (3 * 3 * 5) have an LCM of 225 (3 * 3 * 5 * 5). Because 45 contains two 3’s, x can contain zero, one or two 3’s. LCM contains two 5’s and 45 only contains one 5, so x must contain exactly two 5’s. Therefore, x can be one of three values: 25 (5 * 5), 75 (5 * 5 * 3), or 225 (3 * 3 * 5 * 5)
x = 3^? * 5^2
45 = 3^2 * 5^1
LCM = 3^2 * 5^2

(2) INSUFFICIENT. x and 20 (2 * 2 * 5) have an LCM of 300 (2 * 2 * 3 * 5 * 5). x can contain zero, one or two 2’s. x must contain exactly one 3. X must contain exactly 2 5’s. Therefore, x can be one of three values: 75 (5 * 5 * 3), 150 (5 * 5 * 2 * 3), or 300 (5 * 5 * 2 * 2 * 3).
x = 2^? * 3^1 * 5^2
20 = 2^2 * 3^0 * 5^1
LCM = 2^2 * 3^1 * 5*2

(C) SUFFICIENT. Comparing the possible values of x from statement (1) and (2) shows that there is only one possible value that overlaps, 75

Question 75

Number Properties, Ch 6, Q 8. If x^2 is divisible by 216, what is the smallest possible value for positive integer x?

Answer 75

36. The prime box of x contains the prime factors of 216, which are 2, 2, 2, 3, 3, and 3. You know that the prime factors of x^2 should be the prime factors of x appearing in sets of two, or pairs. Therefore, you should distribute the prime factors of x^2 into two columns to represent the prime factors of x
x, x
2, 2
3, 3
2, ?
3, ?

There is a complete pair of 2’s and 3’s. The left over 2 and 3 must be factors of x as well. Thus, x has 2, 3, 2, and 3 in its prime box, so x must be a positive multiple of 36

Question 76

Number Properties, Ch 6, Q 9. If x and y are positive integers and x/y has a remainder of 5, what is the smallest possible value of xy?

Answer 76

30. The remainder must always be smaller than the divisor. y > 5 and y must be an integer so y must be at least 6. If y is 6, then the smallest possible value of x is 5 (other values of x that would leave a remainder of 5 when divided by 6 would be 11, 17, 23, etc). If y is chosen to be greater than 6, then the smallest possible value of x is still 5. Thus, you will get the smallest possible value of the product xy by choosing the smallest x together with the smallest y. The smallest possible value of xy = 5 * 6 = 30

Question 77

Number Properties, Ch 6, Q 11. Integer x has a remainder of 5 when divided by 9, and integer y has a remainder of 7 when divided by 9. What is the remainder when x – y is divided by 9?

Answer 77

7. Subtracting the remainder of x from the remainder of y yields -2. This number is too small, however, since remainders must be non-negative. The remainder must also be less than 9. You have to shift the remainder upwards by adding 9: -2 + 9 = 7

Question 78

Number Properties, Ch 6, Q 12. Which of the following numbers is NOT prime? 
A. 6! – 1
B. 6! + 21
C. 6! + 41
D. 7! – 1 
E. 7! + 11

Answer 78

Rules

• N! is a multiple of all integers from 1 to N.
• If two numbers share a factor, their sum or difference also shares the same factor

A. 6! – 1 might be prime because 6! and 1 do not share any prime factors
B. 6! + 21 is NOT prime because 6! and 21 are both multiples of 3. Therefore, 6! + 21 is divisible by 3
C. 6! + 41 might be prime because 6! and 41 do not share any prime factors
D. 7! – 1 might be prime because 7! and 1 do not share any prime factors
E. 7! + 11 might be prime because 7! and 11 do not share any prime factors

Question 79

Recognition: Is x^2 + 4xy + 4 divisible by 4?

Answer 79

Factor the equation when you see a divisibility problem and a quadratic equation

(x + 2)(x + 2) / 4 = integer?

Question 80

Recognition: “none left over”

Answer 80

DIVISIBILITY

Question 81

Rule: divisibility of n consecutive integers

Answer 81

• Sum of n consecutive integers is divisible by n if n is odd
• Sum of n consecutive integers is NEVER divisible by n if n is even

Question 82

0!

Answer 82

0! = 1

Question 83

Factorial of a negative number

Answer 83

Undefined

Question 84

How do you find the powers of a prime number p in the n! (e.g. if 25! Is divisible by 2^k, what is the maximum value of k?)

Answer 84

n/p + n/p^2 + n/p^3 + … n/p^k where p^k must be ≤ n

25/2 + 25/4 + 25/8 + 25/16 = 12 + 6 + 3 + 1 = 22

Question 85

How do you find the number of trailing zeros in the decimal representation of n! (e.g. how many zeros are in the end of 32!?)

Answer 85

The number of trailing zeros in the factorial of a non-negative integer n can be determined with the following formula: n/5 + n/5^2 + n/5^3 + … n/5^k where k must be chosen so that 5^k ≤ n

32/5 + 32/25 = 6 + 1 = 7