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