Integer Properties
and Divisibility
Master the foundational rules of divisibility, prime factorization, and integer behavior that appear repeatedly on the GRE Quantitative section.
What Are Integers?
Integers are the set of whole numbers and their negatives: \( \{ \ldots, -3, -2, -1, 0, 1, 2, 3, \ldots \} \). They include no fractions and no decimals.
What Does Divisibility Mean?
An integer \( a \) is divisible by an integer \( b \) (where \( b \neq 0 \)) if there exists an integer \( k \) such that:
Why This Matters on the GRE
Integer properties underpin many GRE Quantitative questions. Recognizing factors, multiples, and divisibility rules lets you solve problems in seconds rather than minutes.
Essential Divisibility Rules
Prime Factorization: The Core Tool
Every integer greater than \(1\) can be expressed as a unique product of prime numbers. This is called the Fundamental Theorem of Arithmetic.
GCD and LCM from Prime Factors
Given the prime factorizations of two numbers, you can find their Greatest Common Divisor and Least Common Multiple instantly.
Factors vs. Multiples
| Factors of 12 | Multiples of 12 | |
|---|---|---|
| Definition | Numbers that divide evenly into \(12\) | Numbers that \(12\) divides evenly into |
| Direction | Go down (smaller) | Go up (larger) |
| Count | Finite: \(1,2,3,4,6,12\) | Infinite: \(12,24,36,48,\ldots\) |
| Range | \(1 \le f \le 12\) | \(12 \le m < \infty\) |
Counting Total Factors
If a number has the prime factorization \( n = p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_k^{a_k} \), then the total number of positive divisors is:
Even and Odd Integer Rules
| Operation | Result | Example |
|---|---|---|
| Even + Even | Even | \(4 + 6 = 10\) |
| Odd + Odd | Even | \(3 + 7 = 10\) |
| Even + Odd | Odd | \(4 + 3 = 7\) |
| Even × Any | Even | \(4 \times 5 = 20\) |
| Odd × Odd | Odd | \(3 \times 5 = 15\) |
The Division Algorithm
For any integer \( a \) and positive integer \( d \), there exist unique integers \( q \) (quotient) and \( r \) (remainder) such that:
How to Solve Divisibility Problems
Example 1: Finding GCD and LCM
Problem: Find \( \text{GCD}(48, 180) \) and \( \text{LCM}(48, 180) \).
Example 2: Counting Factors
Problem: How many positive factors does \( 2{,}520 \) have?
Example 3: Remainder Problem
Problem: When a positive integer \( n \) is divided by \(7\), the remainder is \(3\). What is the remainder when \( n^2 \) is divided by \(7\)?
Common Mistakes to Avoid
Quick Reference Summary
| Concept | Formula / Rule | Example |
|---|---|---|
| Divisibility | \( b \mid a \Leftrightarrow a = bk \) | \( 6 \mid 42 \) since \( 42 = 6 \times 7 \) |
| Factor Count | \( (a_1+1)(a_2+1)\cdots \) | \( 12 = 2^2 \times 3 \Rightarrow 6 \) factors |
| GCD | min of each exponent | \( \text{GCD}(12,18) = 6 \) |
| LCM | max of each exponent | \( \text{LCM}(12,18) = 36 \) |
| Remainder | \( a = dq + r \), \( 0 \leq r < d \) | \( 23 = 5 \times 4 + 3 \) |
Question 1 of 5
How many positive factors does \(72\) have?
Question 2 of 5
What is \(\text{LCM}(15, 20)\)?
Question 3 of 5
When \(n\) is divided by \(6\), the remainder is \(4\). What is the remainder when \(3n\) is divided by \(6\)?
Question 4 of 5
Which of the following must be odd?
Question 5 of 5
If \(\text{GCD}(a, b) = 12\) and \(a \times b = 4{,}320\), what is \(\text{LCM}(a, b)\)?