Number properties: primes, divisibility, remainders and parity

Why properties beat calculation

GMAT Quantitative Reasoning gives you 45 minutes for 21 problem-solving questions, a little over two minutes each, and you cannot use a calculator. Questions about integers are usually built so that multiplying everything out is slow, while one property of the numbers settles the answer in a line. This lesson collects the properties that do most of that work.

Primes and prime factorisation

A prime has exactly two positive divisors, 1 and itself. So 1 is not prime, and 2 is the only even prime. The primes below 30 are 2, 3, 5, 7, 11, 13, 17, 19, 23 and 29.

Every integer greater than 1 is a product of primes in exactly one way. Break a number down with small factors first: $252 = 4 \times 63 = 2^2 \times 3^2 \times 7$. The factorisation answers most integer questions directly:

• Divisibility. $n$ is divisible by $m$ when every prime power in $m$ also appears in $n$. So $252$ is divisible by $18 = 2 \times 3^2$, but not by $8 = 2^3$.
• Number of divisors. Add 1 to each exponent and multiply. A divisor chooses, for every prime, an exponent from zero up to the maximum, so the choices multiply.
• Squares and cubes. A perfect square has only even exponents; a perfect cube has exponents that are all multiples of 3.

Divisibility rules worth knowing

Divisor	Test
2, 5, 10	the last digit
4	the last two digits form a multiple of 4
8	the last three digits form a multiple of 8
3, 9	the digit sum is divisible by 3, or by 9
6	divisible by both 2 and 3

To combine conditions, use prime powers, not multiplication. A number divisible by 4 and by 6 must contain $2^2$ and $3$, so it is divisible by 12; it need not be divisible by 24, and 12 itself shows it.

Greatest common divisor and least common multiple

Write both numbers as prime powers. The GCD takes the smaller exponent of each prime, the LCM the larger. For $72 = 2^3 \times 3^2$ and $60 = 2^2 \times 3 \times 5$, the GCD is $2^2 \times 3 = 12$ and the LCM is $2^3 \times 3^2 \times 5 = 360$. For any two positive integers,

$$\gcd(a, b) \times \text{lcm}(a, b) = ab$$

and here $12 \times 360 = 4320 = 72 \times 60$. LCM questions often hide inside schedules: events that repeat every 18 minutes and every 24 minutes coincide every $\text{lcm}(18, 24) = 72$ minutes.

Remainders

Dividing $n$ by $d$ gives $n = qd + r$ with $0 \le r < d$. The remainder is always smaller than the divisor, and it can be 0, which means $d$ divides $n$. The smallest non-negative number with a given remainder is the remainder itself: if $n$ leaves remainder 5 on division by 7, $n$ could be 5, 12, 19 and so on.

Remainders survive addition and multiplication. To find the remainder of a sum or a product, replace each number by its remainder, compute, and reduce again. That is why you may test a remainder question with the smallest number that fits and trust the result for every other number that fits.

Odd, even and sign

Operation	Result
even $\pm$ even, odd $\pm$ odd	even
odd $\pm$ even	odd
a product with at least one even factor	even
a product of odd numbers only	odd

Zero is even. A product is negative exactly when it has an odd number of negative factors, and a square is never negative. The product of $k$ consecutive integers is always divisible by $k!$: $n(n+1)(n+2)$ contains a multiple of 2 and a multiple of 3, so it is divisible by 6 whatever $n$ is.

Testing cases

For "which must be true" questions, try numbers that break careless rules: 0, 1, a negative number, and one even and one odd value. A single counterexample is enough to discard an option; an option survives only if no allowed value breaks it.