Historical Context & Motivation
The study of integers and their divisibility properties is one of the oldest branches of mathematics, stretching back thousands of years to civilizations that needed to divide resources, measure land, and construct calendars. The ancient Egyptians and Babylonians developed practical techniques for factoring and dividing whole numbers, but it was the Greeks who first elevated these observations into a rigorous theoretical framework. Understanding integer properties and divisibility is not merely an academic exercise; these concepts form the bedrock of modern number theory, cryptography, computer science, and—most immediately for your purposes—standardized test reasoning on the GRE.
On the GRE, questions about integer properties and divisibility appear in both the Quantitative Comparison and Problem Solving formats. They test your ability to reason quickly about factors, multiples, remainders, and prime decomposition—often without a calculator. The central question this lesson addresses is: How can you systematically determine the relationships between integers—who divides whom, what factors they share, and what structure their prime factorizations reveal?
Core Principles & Definitions
Before tackling GRE problems, you need a precise vocabulary. An integer is any whole number—positive, negative, or zero—belonging to the set {..., −3, −2, −1, 0, 1, 2, 3, ...}. Divisibility is the relationship that tells us when one integer divides another without leaving a remainder. We say that integer a divides integer b (written a | b) if there exists an integer k such that b = a × k. The following foundational ideas organize everything you need to know.
Factors & Multiples
Prime Numbers
Fundamental Theorem of Arithmetic
GCD and LCM
The Division Algorithm
Visual Explanation — The Factor Tree & Divisibility Map
The factor tree above illustrates the most important technique you will use on GRE divisibility problems: reducing a composite number to its prime building blocks. Notice that the order in which you divide does not matter—you could split 360 into 10 × 36 instead—but the final set of prime factors is always the same. This is the Fundamental Theorem of Arithmetic in action: uniqueness of prime factorization guarantees a single canonical decomposition for every positive integer greater than 1. Once you have the prime factorization, you can immediately read off the total number of factors, determine divisibility relationships, and compute the GCD or LCM with any other integer.
Mathematical Framework
The prime factorization of an integer is the master key to nearly every divisibility question on the GRE. Let us formalize the relationships and formulas that follow from this decomposition.
These formulas convert abstract questions about divisibility into concrete arithmetic on exponents. On the GRE, the most common application is counting factors: the test loves to ask "how many positive divisors does n have?" or "which of the following must be a factor of n?" Both reduce to the prime factorization plus the divisor-count formula. Similarly, remainder problems exploit the Division Algorithm: when the GRE asks for the remainder when 247 is divided by 6, you compute 247 = 6 × 41 + 1, so the remainder is 1.
Divisibility Rules & Classification
Because the GRE does not allow a calculator on the Quantitative Reasoning section, divisibility rules serve as mental shortcuts that let you quickly test whether a given integer is divisible by small primes or composite numbers. Memorizing these rules saves valuable time and reduces computational errors under test pressure.
A few of these rules deserve special attention for GRE purposes. The rules for 3 and 9 both depend on the digit sum, which exploits the fact that 10 ≡ 1 (mod 3) and 10 ≡ 1 (mod 9). The rule for 4 checks only the last two digits because 100 is divisible by 4, and analogously the rule for 8 checks the last three digits because 1000 is divisible by 8. For the rule for 11, the alternating-sum property arises because 10 ≡ −1 (mod 11), so powers of 10 alternate between +1 and −1 modulo 11. Understanding the "why" behind each rule strengthens your recall and helps you extend the logic to unfamiliar situations on test day.
Worked Example
Let's work through a GRE-style problem that synthesizes prime factorization, factor counting, and GCD/LCM computation.
GRE Strategies & Common Pitfalls
Integer properties questions on the GRE test conceptual understanding as much as computational skill. Knowing the rules is necessary but insufficient—you also need to recognize the common traps the test employs and choose efficient strategies. The table below contrasts effective strategies with the pitfalls they help you avoid.
| Strategy | Common Pitfall | GRE Context |
|---|---|---|
| Always factor into primes before attempting divisibility conclusions. | Assuming that if a | n and b | n, then ab | n (true only when GCD(a,b) = 1). | Quantitative Comparison: "n is divisible by 6 and 10. Is n divisible by 60?" (Not necessarily—LCM(6,10) = 30.) |
| Remember that 0 is an integer and is divisible by every nonzero integer. | Forgetting 0 when asked about "nonnegative integers" or "integers between −5 and 5." | Counting problems that include 0 in the valid range inflate the answer by 1. |
| Recall that 1 is neither prime nor composite. | Counting 1 as a prime number, which overstates prime counts and distorts factorizations. | "How many prime factors does 30 have?" Answer: 3 (not 4). The primes are 2, 3, 5. |
| Distinguish "distinct prime factors" from "total prime factors" (with multiplicity). | Confusing "the number of prime factors of 12" (2, counted as 2 and 3) with "12 has 4 prime factors" (2 × 2 × 3). | Read the question carefully: "different" or "distinct" signals unique primes; otherwise, count with multiplicity. |
| Use the remainder pattern (cycling) for large exponents. | Trying to compute large powers directly instead of recognizing repeating remainder cycles. | "What is the remainder when 7¹⁰⁰ is divided by 5?" Since 7¹ ≡ 2, 7² ≡ 4, 7³ ≡ 3, 7⁴ ≡ 1 (mod 5), the cycle has period 4, and 100 ÷ 4 = 25 exactly, so the remainder is 1. |
Connections to Advanced Number Theory
While the GRE tests fundamental integer properties, these concepts serve as the gateway to far deeper mathematics. The skills you develop here—prime factorization, modular reasoning, and divisor analysis—reappear in more sophisticated forms in graduate-level number theory, abstract algebra, and computational complexity. The table below maps each GRE-level concept to its more advanced generalization, providing context for why these foundations matter beyond test preparation.
| GRE-Level Concept | Advanced Generalization |
|---|---|
| Prime factorization of integers | Unique factorization domains (UFDs) in ring theory; prime ideals in algebraic number fields |
| Divisibility rules using digit sums | Modular arithmetic and congruence theory; Chinese Remainder Theorem for systems of congruences |
| Counting divisors via τ(n) | Multiplicative arithmetic functions (σ(n), Euler's totient φ(n)); Dirichlet series and analytic number theory |
| GCD and LCM via prime exponents | Lattice theory of divisors; Bézout's identity and the Extended Euclidean Algorithm |
| Remainder and quotient (Division Algorithm) | Euclidean domains; polynomial division in F[x]; modular exponentiation in cryptography (RSA, Diffie-Hellman) |
One particularly elegant extension is Euler's totient function φ(n), which counts the number of integers from 1 to n that are coprime to n. For a prime p, φ(p) = p − 1, and for a product of prime powers, φ(n) = n × ∏(1 − 1/p) over all distinct primes p dividing n. This function powers Euler's theorem: a^φ(n) ≡ 1 (mod n) whenever GCD(a, n) = 1, which generalizes Fermat's Little Theorem and is the theoretical backbone of RSA encryption. If you continue to graduate study in mathematics or computer science, you will see these GRE-level ideas elevated into powerful abstract tools.
Practice Problems
Lesson Summary
This lesson established the core framework for reasoning about integer properties and divisibility on the GRE. Every positive integer greater than 1 has a unique prime factorization, which serves as the master key to all divisibility questions. From this factorization, you can count positive divisors using the formula τ(n) = (a₁ + 1)(a₂ + 1)…(aₖ + 1), compute the GCD by taking minimum exponents and the LCM by taking maximum exponents, and verify results using the identity GCD × LCM = a × b.
For efficient test performance, internalize the divisibility rules for 2 through 12, understand that composite-number rules combine the rules of their coprime components, and remember key pitfalls: 1 is not prime, 2 is the only even prime, and 0 is divisible by every nonzero integer. When in doubt, break numbers into primes, compare exponents, and let the Division Algorithm handle remainder questions. These tools, practiced to fluency, will make GRE integer-property questions among the fastest and most reliable points you can earn.