Prime numbers

Overview

Prime numbers are fundamental building blocks in number theory and appear frequently throughout the GRE Quantitative Reasoning section. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. Understanding prime numbers is not merely about memorizing a list—it requires recognizing their properties, identifying when they're being tested, and applying strategic reasoning to solve complex problems efficiently.

The GRE tests prime numbers both directly and indirectly across multiple question formats. Direct questions might ask students to identify prime numbers, count primes within a range, or determine properties of prime factorizations. Indirect applications appear in problems involving divisibility, greatest common factors (GCF), least common multiples (LCM), remainders, and even data interpretation questions where prime number properties simplify calculations. Mastery of gre prime numbers concepts enables students to solve problems more quickly and recognize patterns that less-prepared test-takers miss.

Within the broader Quantitative Reasoning framework, prime numbers connect intimately with arithmetic fundamentals, number properties, and algebraic reasoning. They serve as the foundation for understanding composite numbers, factorization, and divisibility rules. Strong command of prime number concepts also supports work with fractions, ratios, exponents, and even probability problems where counting techniques depend on recognizing prime factors. This topic represents high-yield material that appears in approximately 10-15% of GRE Quantitative questions either directly or as an underlying concept necessary for efficient problem-solving.

Learning Objectives

• [ ] Identify when Prime numbers is being tested
• [ ] Explain the core rule or strategy behind Prime numbers
• [ ] Apply Prime numbers to GRE-style questions accurately
• [ ] Determine whether a given number is prime using efficient testing methods
• [ ] Recognize and utilize the unique properties of prime numbers in factorization problems
• [ ] Distinguish between prime and composite numbers in complex numerical reasoning scenarios
• [ ] Apply prime number concepts to solve problems involving GCF, LCM, and divisibility

Prerequisites

• Basic multiplication and division: Essential for testing divisibility and understanding factors
• Understanding of factors and multiples: Prime numbers are defined by their factor properties
• Divisibility rules: Enable quick determination of whether numbers have certain prime factors
• Basic exponent notation: Prime factorization often uses exponential form (e.g., 2³ × 5²)

Why This Topic Matters

Prime numbers represent one of the most elegant and practical concepts in mathematics, with applications ranging from cryptography and computer science to music theory and biological patterns. In everyday contexts, prime numbers underpin internet security protocols, optimize resource allocation problems, and help identify patterns in natural phenomena.

For GRE test-takers, prime numbers appear with remarkable frequency across the Quantitative Reasoning section. Statistical analysis of recent GRE exams reveals that approximately 12-15% of questions either directly test prime number knowledge or require prime number concepts as part of the solution pathway. These questions appear in multiple formats: Quantitative Comparison questions asking students to compare expressions involving primes, Problem Solving questions requiring prime factorization, and Data Interpretation questions where recognizing prime factors simplifies calculations.

Common exam scenarios include: identifying the number of prime numbers within a specified range; determining the prime factorization of composite numbers; solving problems involving GCF or LCM that require prime factorization; answering questions about divisibility that depend on prime factor analysis; and working with expressions where recognizing prime properties eliminates answer choices. The GRE particularly favors questions that test conceptual understanding rather than rote memorization—for instance, asking about properties of products of primes rather than simply requesting identification of prime numbers from a list.

Core Concepts

Definition and Fundamental Properties

A prime number is a natural number greater than 1 that has exactly two distinct positive divisors: 1 and itself. This definition contains several critical elements. First, 1 is explicitly excluded from the set of prime numbers—a common source of confusion. Second, prime numbers must be natural numbers (positive integers), so negative numbers and fractions cannot be prime. Third, the phrase "exactly two distinct positive divisors" is precise: prime numbers cannot have any other factors besides 1 and themselves.

The number 2 holds a unique position as the only even prime number. Every other even number is divisible by 2 and therefore has at least three divisors (1, 2, and itself), making it composite. This makes 2 the "oddest" prime—literally the only even one. All other prime numbers are odd, though not all odd numbers are prime (9, 15, 21, 25, 27, etc., are odd but composite).

The First Twenty-Five Prime Numbers

Memorizing the first several prime numbers provides immediate advantages on the GRE. The first 25 primes are:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

Students should memorize at minimum the primes up to 50, as these appear most frequently in GRE questions. Recognizing that 51 = 3 × 17, 57 = 3 × 19, and 91 = 7 × 13 are composite (not prime) prevents common errors.

Testing for Primality

To determine whether a number n is prime, test divisibility by all prime numbers up to √n. If n is not divisible by any prime up to its square root, then n is prime. This method is efficient because if n = a × b where both a and b are greater than √n, then a × b would exceed n.

Example: To test whether 89 is prime, calculate √89 ≈ 9.4. Test divisibility by primes less than 9.4: 2, 3, 5, 7. Since 89 is odd (not divisible by 2), not divisible by 3 (8 + 9 = 17, not divisible by 3), ends in 9 (not divisible by 5), and 89 ÷ 7 = 12.71... (not divisible by 7), we conclude 89 is prime.

Prime Factorization

Every composite number can be expressed uniquely as a product of prime numbers raised to various powers. This is the Fundamental Theorem of Arithmetic. Prime factorization is the process of breaking down a composite number into its prime components.

Example: 360 = 2³ × 3² × 5

The process involves repeatedly dividing by the smallest prime factors:

• 360 ÷ 2 = 180
• 180 ÷ 2 = 90
• 90 ÷ 2 = 45
• 45 ÷ 3 = 15
• 15 ÷ 3 = 5
• 5 is prime

Prime factorization enables efficient calculation of GCF and LCM, determination of the number of factors, and simplification of complex expressions.

Composite Numbers

Composite numbers are natural numbers greater than 1 that have more than two positive divisors. In other words, composite numbers are not prime. Every composite number can be expressed as a product of prime numbers. The smallest composite number is 4 (= 2 × 2).

Special Properties and Patterns

Consecutive primes (twin primes) are pairs of prime numbers that differ by 2, such as (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), and (41, 43). The GRE occasionally tests whether students recognize that except for the pair (2, 3), consecutive primes always differ by at least 2.

Prime gaps increase as numbers get larger, though primes continue infinitely. Between 1 and 100, there are 25 primes. Between 101 and 200, there are 21 primes. This decreasing density matters for questions asking about the probability of selecting a prime from a range.

The sum of two primes can be even (when one prime is 2) or odd (when both primes are odd). The product of two distinct primes is always composite and has exactly four factors: 1, the first prime, the second prime, and their product.

Applications to GCF and LCM

Prime factorization provides the most efficient method for finding the Greatest Common Factor (GCF) and Least Common Multiple (LCM) of two or more numbers.

For GCF: Take the product of all common prime factors, each raised to the lowest power that appears in any factorization.

For LCM: Take the product of all prime factors that appear in any factorization, each raised to the highest power that appears.

Example: Find GCF and LCM of 72 and 90

• 72 = 2³ × 3²
• 90 = 2 × 3² × 5
• GCF = 2¹ × 3² = 18
• LCM = 2³ × 3² × 5 = 360

Concept Relationships

Prime numbers serve as the atomic elements of number theory, connecting to virtually every other arithmetic concept tested on the GRE. The relationship flows as follows:

Prime Numbers → Prime Factorization → Divisibility: Understanding which numbers are prime enables prime factorization of composite numbers, which in turn reveals all divisibility relationships. A number is divisible by another if and only if its prime factorization contains all the prime factors (with at least the same powers) of the divisor.

Prime Factorization → GCF and LCM: Once numbers are expressed as products of primes, finding their GCF and LCM becomes systematic rather than trial-and-error. This connection is bidirectional: problems involving GCF or LCM often require working backward to understand prime factorizations.

Prime Numbers → Number of Factors: The prime factorization of a number n = p₁^a × p₂^b × p₃^c reveals that n has exactly (a+1)(b+1)(c+1) total factors. This formula connects prime factorization to counting problems.

Prime Numbers → Remainders and Modular Arithmetic: Many remainder problems simplify when numbers are expressed in terms of their prime factors, particularly when working with divisibility rules.

Prime Numbers → Probability and Counting: Questions asking about the probability of selecting a prime number from a set, or counting primes within a range, directly test prime number identification skills.

The prerequisite knowledge of factors, multiples, and divisibility rules feeds directly into prime number mastery, while prime number concepts enable progression to more advanced topics like rational expressions, polynomial factoring, and number theory problems involving perfect squares and cubes.

High-Yield Facts

⭐ 2 is the only even prime number; all other primes are odd

⭐ 1 is neither prime nor composite; it has exactly one positive divisor (itself)

⭐ The first ten prime numbers are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

⭐ To test if n is prime, check divisibility by all primes up to √n

⭐ Every composite number has a unique prime factorization (Fundamental Theorem of Arithmetic)

• The smallest prime number is 2; the smallest composite number is 4

• There are exactly 25 prime numbers between 1 and 100

• The largest two-digit prime number is 97

• Consecutive primes (except 2 and 3) differ by at least 2

• The product of two distinct primes has exactly four factors

• If p is prime and p divides ab, then p divides a or p divides b (or both)

• The sum of any two odd primes is even

• Numbers ending in 0, 2, 4, 5, 6, or 8 cannot be prime (except 2 and 5)

• The number of factors of n = p₁^a × p₂^b is (a+1)(b+1)

• Prime numbers greater than 3 can be expressed as 6k±1 for some integer k

Common Misconceptions

Misconception: 1 is a prime number because it's only divisible by 1 and itself.

Correction: By definition, prime numbers must have exactly two distinct positive divisors. Since 1 has only one divisor (itself), it is neither prime nor composite. This exception exists to preserve the uniqueness of prime factorization.

Misconception: All odd numbers are prime.

Correction: While all primes except 2 are odd, many odd numbers are composite. Examples include 9 (= 3 × 3), 15 (= 3 × 5), 21 (= 3 × 7), 25 (= 5 × 5), 27 (= 3³), and 33 (= 3 × 11). Being odd is necessary but not sufficient for primality.

Misconception: Large numbers that don't end in 0, 2, 4, 5, 6, or 8 are probably prime.

Correction: Many composite numbers end in 1, 3, 7, or 9. For example, 51 = 3 × 17, 91 = 7 × 13, 119 = 7 × 17, and 121 = 11². Always test divisibility systematically rather than assuming based on the final digit.

Misconception: To test if a number n is prime, you must test divisibility by all numbers less than n.

Correction: You only need to test divisibility by prime numbers up to √n. If n has a factor greater than √n, it must also have a corresponding factor less than √n. This dramatically reduces the work required.

Misconception: The GCF of two prime numbers is always 1.

Correction: The GCF of two distinct prime numbers is 1, but if the same prime appears twice (e.g., GCF of 7 and 7), the GCF equals that prime. Also, when working with powers of primes, the GCF is the lower power: GCF(2³, 2⁵) = 2³.

Misconception: Prime factorization and finding factors are the same thing.

Correction: Prime factorization expresses a number as a product of primes (e.g., 12 = 2² × 3), while finding factors lists all divisors (1, 2, 3, 4, 6, 12). Prime factorization is a tool that helps find all factors, but they're distinct concepts.

Worked Examples

Example 1: Identifying Primes and Applying Properties

Question: If p and q are distinct prime numbers, each greater than 2, which of the following must be true?

I. p + q is even

II. pq has exactly four factors

III. p - q is even

Solution:

Step 1: Recognize what we know. Since p and q are primes greater than 2, both must be odd (2 is the only even prime).

Step 2: Evaluate Statement I.

• The sum of two odd numbers is always even
• Example: 3 + 5 = 8, 7 + 11 = 18
• Statement I is TRUE

Step 3: Evaluate Statement II.

• The product of two distinct primes has factors: 1, p, q, and pq
• Example: 3 × 5 = 15 has factors 1, 3, 5, 15
• This gives exactly four factors
• Statement II is TRUE

Step 4: Evaluate Statement III.

• The difference of two odd numbers is always even
• Example: 7 - 3 = 4, 11 - 5 = 6
• Statement III is TRUE

Answer: All three statements (I, II, and III) must be true.

Connection to Learning Objectives: This problem tests the ability to identify when prime number properties are being tested (odd/even nature of primes, factor counting) and apply core strategies (recognizing that primes > 2 are odd, understanding factor structure of prime products).

Example 2: Prime Factorization Application

Question: What is the greatest common factor of 180 and 234?

Solution:

Step 1: Find the prime factorization of 180.

• 180 = 2 × 90 = 2 × 2 × 45 = 2 × 2 × 9 × 5 = 2² × 3² × 5

Step 2: Find the prime factorization of 234.

• 234 = 2 × 117 = 2 × 9 × 13 = 2 × 3² × 13

Step 3: Identify common prime factors.

• Both contain: 2¹ and 3²
• 180 contains 5, but 234 does not
• 234 contains 13, but 180 does not

Step 4: Calculate GCF using lowest powers of common primes.

• GCF = 2¹ × 3² = 2 × 9 = 18

Step 5: Verify by checking that 18 divides both numbers.

• 180 ÷ 18 = 10 ✓
• 234 ÷ 18 = 13 ✓

Answer: The GCF of 180 and 234 is 18.

Connection to Learning Objectives: This demonstrates applying prime number concepts to GRE-style questions accurately, specifically using prime factorization as a strategy for finding GCF efficiently rather than listing all factors.

Exam Strategy

When approaching GRE questions involving prime numbers, begin by identifying trigger words and phrases: "prime," "prime factorization," "greatest common factor," "least common multiple," "divisible by," "factors of," and "relatively prime." These signals indicate that prime number concepts will likely provide the most efficient solution path.

Time-saving approach: Memorize primes up to 50 before test day. This eliminates calculation time and prevents errors. When testing whether a number is prime, immediately check divisibility by 2, 3, and 5 using quick divisibility rules before testing other primes. For numbers less than 100, you only need to test primes up to 7 (since √100 = 10).

Process of elimination for Quantitative Comparison: When comparing expressions involving primes, test with small prime values first (2, 3, 5) to eliminate answer choices. Remember that 2 behaves differently from other primes (it's even), so always test it separately if the question doesn't specify "odd prime."

Strategic substitution: Many abstract prime number questions become clearer when you substitute actual prime values. If a question asks about "prime number p," try p = 2, then p = 3, then p = 5 to identify patterns or eliminate impossible answers.

Factor-counting shortcut: If a question asks about the number of factors, immediately think prime factorization. Convert the number to prime factor form (p₁^a × p₂^b × p₃^c), then apply the formula (a+1)(b+1)(c+1) rather than listing factors manually.

Red flag numbers: Be especially careful with 1 (not prime), 2 (only even prime), 51 (looks prime but equals 3 × 17), 57 (= 3 × 19), and 91 (= 7 × 13). These frequently appear as trap answers.

Allocate approximately 1-2 minutes for straightforward prime identification questions, but budget 2-3 minutes for complex problems requiring prime factorization of large numbers or multi-step reasoning involving GCF/LCM.

Memory Techniques

Mnemonic for first ten primes: "Two Three Five Seven Eleven" creates a rhythm: 2-3-5-7-11, then continue with 13-17-19-23-29.

Visual pattern for primes under 30: Imagine a number line with primes highlighted. Notice the pattern: 2 (alone), then pairs near each other (3,5,7), a gap, then (11,13), another gap, then (17,19), gap, then (23,29). This clustering pattern helps recall.

"PRIME" acronym for testing primality:

• Pick the square root
• Round up to nearest integer
• Identify primes below that number
• Methodically test each prime divisor
• Eliminate if any divide evenly

Divisibility quick checks:

• 2: Last digit even
• 3: Sum of digits divisible by 3
• 5: Last digit 0 or 5
• 7: Double the last digit, subtract from remaining number; if result divisible by 7, original is too

Factor formula memory: "Add one to each exponent, then multiply" — for n = p₁^a × p₂^b, factors = (a+1)(b+1)

GCF vs. LCM distinction: "Common means Choose the Common factors with Conservative (lowest) powers" for GCF. "Multiple means Maximize — take Maximum powers" for LCM.

Summary

Prime numbers are natural numbers greater than 1 with exactly two positive divisors: 1 and themselves. Mastery of prime numbers for the GRE requires three core competencies: identifying primes efficiently (testing divisibility by primes up to the square root), understanding prime factorization and its applications (GCF, LCM, factor counting), and recognizing when prime number properties provide solution shortcuts. The number 2 stands alone as the only even prime, while 1 is neither prime nor composite. Every composite number has a unique prime factorization, making this concept foundational for divisibility, factor analysis, and number property questions. GRE questions test both direct recognition of primes and indirect applications through problems involving GCF, LCM, divisibility, and factor counting. Success requires memorizing primes through at least 50, understanding the systematic approach to primality testing, and recognizing the special properties that distinguish primes from composite numbers. These concepts appear in approximately 12-15% of Quantitative Reasoning questions and provide efficient solution pathways for many additional problems where prime factorization simplifies complex calculations.

Key Takeaways

• Prime numbers have exactly two divisors (1 and themselves); 1 is not prime, and 2 is the only even prime
• Memorize primes up to 50 for immediate recognition and time savings on test day
• Test primality efficiently by checking divisibility only by primes up to the square root
• Prime factorization is unique for every composite number and enables systematic calculation of GCF and LCM
• GCF uses lowest powers of common prime factors; LCM uses highest powers of all prime factors
• Factor counting formula: For n = p₁^a × p₂^b × p₃^c, the number of factors is (a+1)(b+1)(c+1)
• Watch for trap numbers: 51, 57, 91, and 119 appear prime but are composite; always verify systematically

Related Topics

Divisibility Rules: Understanding which numbers divide evenly into others connects directly to prime factorization, as divisibility depends on the presence of specific prime factors. Mastering primes enables quick application of divisibility tests.

Greatest Common Factor (GCF) and Least Common Multiple (LCM): These concepts rely entirely on prime factorization for efficient calculation. Strong prime number skills make GCF and LCM problems straightforward rather than time-consuming.

Perfect Squares and Cubes: Recognizing that perfect squares have prime factorizations where all exponents are even (and cubes have exponents divisible by 3) builds on prime factorization mastery.

Rational Number Operations: Simplifying fractions to lowest terms requires finding the GCF of numerator and denominator, which depends on prime factorization skills.

Modular Arithmetic and Remainders: Advanced number theory problems involving remainders often simplify when numbers are expressed in terms of their prime factors.

Practice CTA

Now that you've mastered the core concepts of prime numbers, it's time to solidify your understanding through active practice. Attempt the practice questions to test your ability to identify primes quickly, apply prime factorization strategies, and solve GRE-style problems under timed conditions. Use the flashcards to reinforce memorization of primes up to 50 and key properties. Remember: prime numbers appear in approximately one out of every seven or eight Quantitative Reasoning questions—your investment in mastering this topic will pay dividends throughout the exam. Challenge yourself to move beyond recognition toward automatic application, and you'll find that many seemingly complex problems become straightforward when viewed through the lens of prime number properties.