9. Divisibility & Primes Flashcards
What are the basic arithmetic rules for integers?
(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
What does Divisible mean?
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
How do you determine if x + y is divisible by y?
In order for x + y to be divisible by y, x itself must be divisible by y
What is the only even prime number?
2
What integers are not prime numbers?
0 and 1
What are the divisibility rules for small integers (ie the counting numbers 2-10)?
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)
What is a factor?
- 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
What does Divisible mean?
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
What is a multiple?
- 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
What are Factor Pairs?
A list of all the pairs of factors of a particular number
Factor pairs of 60
- Label two columns “small” and “large”
- Start with 1 and 60
- Next small number 2 because it is a factor of 60
- 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
What is the shortcut for determining the number of factors of a number (e.g. 180)?
(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
What are the different ways the GMAT can phrase information about divisibility? (e.g. 12 and 3)
- 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
What happens if you add or subtract two multiples of N? (e.g. 35 + 21 = 56, 35 – 21 = 14)
- 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
What are Prime Numbers?
- 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
What are the defining characteristics of prime numbers?
(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
What is the Prime Factorization?
- 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
What are the different situations in which you might use prime factorization?
(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
What rule should you remember when a problem states or assumes that a number is an integer?
-You may need to use prime factorization to solve the problem
What is a Factor Tree?
- Use the factor tree to break down any number into its prime factors
- Circle prime numbers as you go
What is the 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, “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
What are the divisibility rules with respect to addition and subtraction?
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)
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 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
What is the Greatest Common Factor? (e.g. 12 and 30)
- 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.
What is the Least Common Multiple? (e.g. 6 and 9)
- 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
What is the best way to find the GCF or LCM? (e.g. 30 and 24)
(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
What is the GCF and LCM if two integers have no primes in common?
GCF = 1 LCM = the product of the two integers
How do you determine the GCF and LCM of large numbers (e.g. 100, 140, 250)?
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
What are the general properties of the GCF and LCM?
(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
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 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
If the LCM of a and 12 is 36, what are the possible values of a?
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
What are the three basic rules of factors?
(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)
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)?
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
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)?
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
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)
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.
Factors of X and Y. What can you conclude given X is divisible by 6 and Y is divisible by 9?
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
What does the following statement imply: “m/2 is NOT an even integer”?
This does NOT mean that m/2 is an odd integer! Rather, it may be that m/2 is not an integer at all
If you add two non-multiples of N, what is the result?
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)
How do you determine the number of different factors for a large number (e.g. 2,000)?
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)
How many different factors does 9,450 have?
(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
How many unique prime factors of 1,400 are there?
- 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
How is the length of an integer defined?
The total number of primes (not necessarily distinct) that, when multiplied together, equal that integer
What is the length of 1,400?
Add the exponents of each prime factor.
Three 3’s + two 5’s + one 7 = 3 + 2 + 1 = 6
How many total factors of 1,400 are there?
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
What are two defining characteristics of perfect squares?
(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
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 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
What characteristics do factorials have with respect to divisibility?
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
What is the dividend?
- Number being divided (numerator)
- In the operation 22/4, 22 is the dividend
What is the divisor?
- Number that is dividing (denominator)
- In the operation 22/4, 4 is the divisor
What is the quotient?
- 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.
What is the remainder?
- 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.
What is the relationship between the quotient and the remainder?
When a positive integer is divided by another positive integer:
Dividend = Quotient * Divisor + Remainder Dividend/Divisor = Quotient + Remainder/Divisor
What is the quotient and remainder when 3 is divided by 5?
Quotient = 0 Remainder = 3
What are the three ways to express remainders?
(1) Integer
(2) Fraction
(3) Decimal
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 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
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 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
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?
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
What two rules apply to arithmetic with remainders if you have the same divisor throughout?
(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
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?
4 + 2 = 6 after division by 7
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?
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
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?
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
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?
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
Ch 2, Q 28. 28. If 7x is a multiple of 210, must x be a multiple of 12?
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.
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?
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
Ch 2, Q 41. 4, 21, and 55 are factors of n. Does 154 divide n?
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.
Ch 2, Q 42. If n is divisible by 196 and by 15, is 270 a factor of n?
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.
Number Properties Guide, Ch 1, Q 2. If 80 is a factor of r, is 15 a factor of r?
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
Number Properties Guide, Ch 1, Q 4. If j is divisible by 12 and 10, is j divisible by 24?
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
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?
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
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?
- 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
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 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)
Number Properties, Ch 6, Q 4. Is p divisible by 168?
(1) p is divisible by 14
(2) p is divisible by 12
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
Number Properties, Ch 6, Q 5. Is pq divisible by 168?
(1) p is divisible by 14
(2) q is divisible by 12
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.
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 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
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 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
Number Properties, Ch 6, Q 8. If x^2 is divisible by 216, what is the smallest possible value for positive integer x?
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
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?
- 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
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?
- 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
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
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
Recognition: Is x^2 + 4xy + 4 divisible by 4?
Factor the equation when you see a divisibility problem and a quadratic equation
(x + 2)(x + 2) / 4 = integer?
Recognition: “none left over”
DIVISIBILITY
Rule: divisibility of n consecutive integers
- 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
0!
0! = 1
Factorial of a negative number
Undefined
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?)
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
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!?)
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
