## GMAT Primes

### Introduction:

Primes are a fundamental concept in number theory and play a significant role in the GMAT quantitative section. This course will dive into the properties and characteristics of prime numbers, helping you strengthen your understanding of this crucial topic. In this first part of our four-part series on primes and number properties, we will cover the basic concepts and definitions, divisibility rules, and some essential properties of prime numbers.

## Part 1: Understanding Prime Numbers and Number Properties

Definition of Prime Numbers A prime number is a natural number greater than 1 that has only two distinct positive divisors: 1 and itself. In other words, a prime number cannot be formed by multiplying two smaller natural numbers. The first few prime numbers are 2, 3, 5, 7, 11, 13, 17, etc.

Definition of Composite Numbers A composite number is a natural number greater than 1 that is not a prime number. In other words, a composite number has more than two distinct positive divisors. For example, 4, 6, 8, 9, and 10 are composite numbers.

Unique Factorization Theorem: The Fundamental Theorem of Arithmetic states that every integer greater than 1 can be represented uniquely as a product of prime numbers, up to the order of the factors. For example, 24 can be represented as 23 × 31, and this representation is unique.

Divisibility Rules Divisibility rules help us quickly determine whether a number is divisible by another without performing long division. Some common divisibility rules are:

a) Divisibility by 2: A number is divisible by 2 if its last digit is even (0, 2, 4, 6, or 8).

b) Divisibility by 3: A number is divisible by 3 if the sum of its digits is divisible by 3.

c) Divisibility by 4: A number is divisible by 4 if its last two digits form a number divisible by 4.

d) Divisibility by 5: A number is divisible by 5 if its last digit is 0 or 5.

e) Divisibility by 6: A number is divisible by 6 if it is divisible by both 2 and 3.

f) Divisibility by 9: A number is divisible by 9 if the sum of its digits is divisible by 9.

Prime Number Properties Some essential properties of prime numbers include:

a) Except for 2, all prime numbers are odd.

b) There is an infinite number of prime numbers.

c) The difference between two consecutive prime numbers can be any even number except 2.

d) Every even number greater than 2 can be expressed as the sum of two prime numbers (Goldbach’s Conjecture).

In this first part of our four-part series on primes and number properties, we have covered the basic concepts, divisibility rules, and essential properties of prime numbers. Stay tuned for Part 2, where we will delve deeper into prime factorization, least common multiple (LCM), and greatest common divisor (GCD).

## Part 2: Prime Factorization, Least Common Multiple (LCM), and Greatest Common Divisor (GCD)

In this second part of our four-part series on primes and number properties, we will explore prime factorization, least common multiple (LCM), and greatest common divisor (GCD), along with some useful techniques and examples to help you master these concepts.

Prime Factorization Prime factorization is the process of breaking down a number into a product of its prime factors. It is based on the Unique Factorization Theorem, which states that every integer greater than 1 can be uniquely represented as a product of prime numbers.

Example: Find the prime factorization of 84. Solution: Divide 84 by the smallest prime number (2) and continue dividing the quotient by the smallest possible prime numbers until you reach a prime quotient. 84 ÷ 2 = 42 42 ÷ 2 = 21 21 ÷ 3 = 7 So, 84 = 22 × 31 × 71.

Least Common Multiple (LCM) The least common multiple (LCM) of two or more numbers is the smallest multiple divisible by each number. LCM can be found using prime factorization.

Example: Find the LCM of 12 and 20. Solution: Prime factorize the numbers: 12 = 22 × 31 and 20 = 22 × 51 Now, take the highest powers of all the prime factors present and multiply them together: LCM(12, 20) = 22 × 31 × 51 = 60

Greatest Common Divisor (GCD) The greatest common divisor (GCD) of two or more numbers is the largest number that divides each of the given numbers without leaving a remainder. Like LCM, GCD can also be found using prime factorization.

Example: Find the GCD of 18 and 24. Solution: Prime factorize the numbers: 18 = 21 × 32 and 24 = 23 × 31 Now, take the lowest powers of all the common prime factors and multiply them together: GCD(18, 24) = 21 × 31 = 6

Relationship between LCM and GCD For any two positive integers a and b: LCM(a, b) × GCD(a, b) = a × b

Example: Given that LCM(10, 15) = 30 and GCD(10, 15) = 5, verify the relationship. Solution: LCM(10, 15) × GCD(10, 15) = 30 × 5 = 150 And, 10 × 15 = 150 Hence, the relationship holds.

In this second part of our series, we have explored prime factorization, least common multiple (LCM), and greatest common divisor (GCD). In Part 3, we will discuss concepts like prime gaps, twin primes, and prime counting functions and their applications in GMAT problem-solving.

## Part 3: Prime Gaps, Twin Primes, and Prime Counting Functions

In this third part of our four-part series on primes and number properties, we will delve into prime gaps, twin primes, and prime counting functions. We will also explore their applications in GMAT problem-solving.

Prime Gaps Prime gap refers to the difference between consecutive prime numbers. Prime gaps can be of varying sizes, and no fixed pattern exists. As the numbers increase, the prime gaps tend to become larger on average, but smaller gaps can still appear.

Example: The prime gap between 3 and 5 is 2, while the prime gap between 23 and 29 is 6.

Twin Primes Twin primes are pairs of prime numbers with a difference of 2. Examples of twin prime pairs include (3, 5), (5, 7), (11, 13), and (17, 19). It is conjectured that there are infinitely many twin primes, but this has not been proven.

Prime Counting Function (π(x)) The prime counting function, denoted as π(x), represents the number of prime numbers less than or equal to x. For example, π(10) = 4, as four prime numbers (2, 3, 5, 7) are less than or equal to 10. The prime counting function can be used to estimate the density of prime numbers within a given range.

Application of Prime Gaps and Twin Primes in GMAT Problem-Solving Prime gaps and twin primes can solve GMAT problems involving consecutive prime numbers or prime pairs with specific differences. Understanding these concepts can help you quickly identify patterns and find solutions.

Example: Find the sum of all twin prime pairs between 10 and 50. Solution: Identify the twin prime pairs in the given range: (11, 13), (17, 19), (29, 31), and (41, 43). Now, find the sum of these twin prime pairs: (11 + 13) + (17 + 19) + (29 + 31) + (41 + 43) = 204

Application of Prime Counting Function in GMAT Problem-Solving The prime counting function can solve problems requiring determining the number of prime numbers within a range or estimating the density of primes in larger intervals.

Example: Estimate the number of prime numbers between 1 and 100. Solution: Using the prime number theorem, we can approximate π(x) with the function x / ln(x), where ln(x) is the natural logarithm of x. So, π(100) ≈ 100 / ln(100) ≈ 100 / 4.605 = 21.7. Therefore, there are approximately 22 prime numbers between 1 and 100.

In this third part of our series, we have covered prime gaps, twin primes, prime counting functions, and their applications in GMAT problem-solving. In the final part of this series, we will discuss special prime numbers, prime sieves, and advanced prime number techniques for more complex GMAT problems.

## Part 4: Special Prime Numbers, Prime Sieves, and Advanced Techniques

In this final part of our four-part series on primes and number properties, we will explore special prime numbers, prime sieves, and advanced techniques for tackling more complex GMAT problems involving prime numbers.

Special Prime Numbers Apart from the regular prime numbers, there are some special categories of prime numbers, such as:

a) Mersenne Primes: Prime numbers of the form 2^p – 1, where p is a prime number. Examples include 3 (22 – 1), 7 (23 – 1), and 31 (25 – 1). b) Fermat Primes: Prime numbers of the form 2(2^n) + 1, where n is a non-negative integer. Examples include 5 (2(2^0) + 1) and 17 (2(2^1) + 1).

Prime Sieves Prime sieves are algorithms for finding prime numbers within a specific range. One of the most famous prime sieves is the Sieve of Eratosthenes. It is an ancient algorithm for finding all prime numbers up to a given limit by iteratively eliminating multiples of known primes.

Example: Find all prime numbers less than or equal to 30 using the Sieve of Eratosthenes. Solution: Begin with the list of numbers from 2 to 30. Starting with 2, cross out all multiples of 2 (except 2) in the list. Then, move to the next unmarked number (3) and cross out all multiples of 3 (except 3). Continue this process; the remaining unmarked numbers are the prime numbers: 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29.

Advanced Techniques for GMAT Prime Number Problems Some advanced techniques for tackling complex GMAT problems involving prime numbers include:

a) Using modular arithmetic to simplify calculations.

b) Applying the Chinese Remainder Theorem to solve problems involving congruences.

c) Leveraging Euler’s Totient Function to determine the count of relatively prime numbers to a given number.

Example: Solve the following GMAT problem using modular arithmetic: Find the remainder when 7^200 is divided by 10. Solution: Instead of calculating the entire expression, we can find the repeating pattern of the remainders when powers of 7 are divided by 10: 71 % 10 = 7, 72 % 10 = 9 73 % 10 = 3 74 % 10 = 1 The pattern repeats after every 4 powers. So, 7200 has the same remainder as 7(200 % 4) = 70, which is 1.

In this final part of our primes and number properties series, we explored special prime numbers, prime sieves, and advanced techniques for solving complex GMAT problems involving prime numbers. Understanding these concepts and practicing problems that apply these techniques will help you gain a more profound mastery of prime numbers and their properties, ultimately improving your performance in the GMAT quantitative section.

## Practice questions with an answer key.

### Problem-Solving Questions

Question 1:

Which of the following numbers is a prime number?

A) 18 B) 21 C) 23 D) 24 E) 27

Question 2:

What is the least common multiple (LCM) of 6 and 10?

A) 20 B) 24 C) 30 D) 40 E) 60

Question 3:

What is the greatest common divisor (GCD) of 14 and 28?

A) 2 B) 7 C) 14 D) 28 E) 56

Question 4:

Which of the following is a twin prime pair? A)

(9, 11) B) (14, 16) C) (17, 19) D) (20, 22) E) (25, 27)

Answer: C) (17, 19)

Question 5:

What is the prime factorization of 56?

A) 22 × 72 B) 22 × 71 C) 23 × 71 D) 21 × 72 E) 23 × 72

Answer: B) 22 × 71

Question 6:

How many prime numbers are there between 10 and 50?

A) 8 B) 9 C) 10 D) 11 E) 12

Question 7:

If p and q are prime numbers such that p > q, which of the following must be true for p + q?

A) Odd B) Even C) Prime D) Composite E) Perfect square

Question 8:

What is the sum of all the prime factors of 90?

A) 10 B) 11 C) 13 D) 15 E) 17

Question 9:

Which of the following numbers is a Mersenne prime?

A) 7 B) 15 C) 17 D) 31 E) 33

Question 10:

What is the remainder when 3^100 is divided by 5?

A) 0 B) 1 C) 2 D) 3 E) 4

Question 11:

For a positive integer n, let f(n) be the product of all prime numbers less than n. What is the value of f(12)?

A) 30 B) 42 C) 70 D) 210 E) 231

Question 12:

If p is a prime number, which of the following is NOT a possible value for the expression p2 – 1?

A) 20 B) 48 C) 80 D) 120 E) 240

Question 13:

Let a, b, and c be distinct prime numbers such that a < b < c. If the product of any two of them is 35 less than the product of all three, what is the value of c?

A) 11 B) 13 C) 17 D) 19 E) 23

Question 14:

How many prime numbers less than 50 have the property that the sum of their digits is also a prime number?

A) 5 B) 6 C) 7 D) 8 E) 9

Question 15:

Given that a, b, and c are consecutive prime numbers such that a < b < c, and the product abc = 9699690, what is the value of b?

A) 7 B) 11 C) 13 D) 17 E) 19

Question 16:

Let p and q be two distinct prime numbers greater than 3. Which of the following CANNOT be the sum of p and q?

A) 20 B) 21 C) 22 D) 23 E) 24

Question 17:

If a and b are distinct prime numbers, and x = 2^a × 3^b, which of the following CANNOT be the value of x?

A) 72 B) 108 C) 162 D) 216 E) 324

Question 18:

Let S be the sum of all three-digit positive integers that have exactly two distinct prime factors. What is the sum of the digits of S?

A) 18 B) 21 C) 24 D) 27 E) 30

Question 19:

If a and b are prime numbers, which of the following numbers must be an integer? A) (ab + ba)/a

B) (ab + ba)/b

C) (ab – ba)/a

D) (ab – ba)/b

E) (ab – ba)/(a – b)

Answer: E) (ab – ba)/(a – b)

Question 20:

If x is a positive integer such that 2x – 1 is a prime number, which of the following could be a divisor of x?

A) 3 B) 5 C) 7 D) 9 E) 11

### Data Sufficiency (Five answer choices; one correct answer)

#### For each Data sufficiency Question, the Answer choice would be

###### E) Statements (1) and (2) TOGETHER are NOT sufficient to answer the question asked, and additional data are needed.

Question 1:

Is integer n a prime number?

(1) n is odd.

(2) n has exactly two distinct positive divisors.

Answer: B) Statements (1) and (2) together are sufficient, but neither statement alone is sufficient.

Question 2:

What is the greatest common divisor (GCD) of integers x and y?

(1) x = 12

(2) y = 20

Answer: C) Both statements together are sufficient, but neither statement alone is sufficient.

Question 3:

Is the product of integers a and b divisible by 15?

(1) a is a multiple of 3.

(2) b is a multiple of 5.

Answer: C) Both statements together are sufficient, but neither statement alone is sufficient.

Question 4:

Is integer p a prime number?

(1) The square of p is greater than 20.

(2) p is odd.

Answer: E) Statements (1) and (2) together are not sufficient.

Question 5:

What is the least common multiple (LCM) of positive integers m and n?

(1) m = 4

(2) n = 6

Answer: C) Both statements together are sufficient, but neither statement alone is sufficient.

Question 6:

What is the sum of the prime factors of integer x?

(1) x is divisible by 6.

(2) x is divisible by 35.

Answer: E) Statements (1) and (2) together are not sufficient.

Question 7:

Is integer n a prime number?

(1) n is an odd integer greater than 20.

(2) n + 1 is a multiple of 6.

Answer: D) Statement (2) alone is sufficient, but statement (1) alone is not sufficient.

Question 8:

If p is a prime number, what is the value of p?

(1) p is the smallest prime number greater than 20.

(2) p is the largest prime number less than 30.

Answer: A) Statement (1) alone is sufficient, but statement (2) alone is not sufficient.

Question 9:

What is the greatest common divisor (GCD) of integers a and b?

(1) The least common multiple (LCM) of a and b is 420.

(2) a is a multiple of 7, and b is a multiple of 5.

Answer: E) Statements (1) and (2) together are not sufficient.

Question 10:

If x and y are positive integers, is xy a prime number?

(1) x and y are both prime numbers.

(2) y = 2.

Answer: B) Statement (2) alone is sufficient, but statement (1) alone is not sufficient.

Question 11:

What is the sum of the prime factors of integer x?

(1) x is divisible by 10.

(2) x is divisible by 21.

Answer: E) Statements (1) and (2) together are not sufficient.

Question 12:

If p and q are distinct prime numbers, what is the value of pq?

(1) p – q = 2

(2) p + q = 20

Answer: C) Both statements together are sufficient, but neither statement alone is sufficient.

Question 13:

Is the product of integers x and y divisible by 30?

(1) x is a multiple of 10 and y is a multiple of 3.

(2) The greatest common divisor (GCD) of x and y is 2.

Answer: A) Statement (1) alone is sufficient, but statement (2) alone is not sufficient.

Question 14:

What is the value of integer x?

(1) The least common multiple (LCM) of x and 18 is 72.

(2) The greatest common divisor (GCD) of x and 18 is 6.

Answer: D) Statement (2) alone is sufficient, but statement (1) alone is not sufficient.

Question 15:

If a, b, and c are distinct prime numbers such that a < b < c, what is the value of c?

(1) The product of any two of a, b, and c is 19 less than the product of all three.

(2) a + b + c = 22

Answer: B) Statement (2) alone is sufficient, but statement (1) alone is not sufficient.

Question 16:

What is the smallest prime factor of positive integer n?

(1) n is a multiple of 30.

(2) n is a multiple of 49.

Answer: A) Statement (1) alone is sufficient, but statement (2) alone is not sufficient.

Question 17:

Is the product of two positive integers x and y divisible by 77?

(1) x is a multiple of 7, and y is a multiple of 11.

(2) x + y is a multiple of 18.

Answer: A) Statement (1) alone is sufficient, but statement (2) alone is not sufficient.

Question 18:

If x, y, and z are positive integers, is xy × yz a prime number?

(1) x and y are distinct prime numbers, and z = 1.

(2) x = y.

Answer: E) Statements (1) and (2) together are not sufficient.

Question 19: If p and q are distinct prime numbers, what is the value of p2 × q?

(1) p2 × q is a factor of 420.

(2) p2 × q is a factor of 330.

Answer: E) Statements (1) and (2) together are not sufficient.

Question 20: What is the value of prime number p?

(1) The square of p is a factor of 196.

(2) The cube of p is a factor of 343.

Answer: D) Statement (2) alone is sufficient, but statement (1) alone is not sufficient.