Integer Properties and Divisibility

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?

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.

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.

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.

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.

Let's work through a GRE-style problem that synthesizes prime factorization, factor counting, and GCD/LCM computation.

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.

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.

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.