QUANTITATIVE REASONING · GMAT-Q-REM-01

Remainders, Units Digits and Cyclicity

GMAT lesson development preview · DRAFT · Original learning and assessment material

Concepts and problem-solving strategy

Division algorithm

n = d q + r, q \in Z, 0 \leq r < d

Congruence

a \equiv b (mod m) ⟺ m ∣ (a - b)

Operations

a \equiv b (mod m) \Rightarrow a + c \equiv b + c (mod m)

Repeating powers

a^{k} (mod m) repeats; establish the cycle before reducing k

Units digits

7^{1}, 7^{2}, 7^{3}, 7^{4} \equiv 7, 9, 3, 1 (mod 10)

Think Like a GMAT Test-Taker

A remainder is the amount left after removing complete groups of the divisor. Write n=dq+r, with integer q and 0≤r<d. Congruence means two numbers leave the same remainder; it does not mean they are equal. For powers, first establish a repeating pattern.

Faster Methods

Substitute n=dq+r into expressions containing n.

To find a units digit, work modulo 10 and list one full cycle.

Reduce a large exponent modulo the verified cycle length; remainder zero selects the last cycle term.

Check compatibility when conditions use different divisors.

Worked example 1

If n leaves remainder 5 when divided by 8, find the remainder of 3n+2.

n = 8 q + 5 \Rightarrow 3 n + 2 = 8 (3 q + 2) + 1

Substituting 8q+5 gives 24q+17. Remove another two groups of eight from 17: the leftover is 1. The quotient changes, but the remainder must stay between 0 and 7.

Worked example 2

Find the units digit of $7^{43}$ .

43 \equiv 3 (mod 4); cycle: 7, 9, 3, 1

The units digits of the first four positive powers are 7, 9, 3, 1. Multiplying by 7 repeats the cycle. Since 43=4×10+3, choose its third entry, 3; do not calculate the enormous power.

Worked example 3

Find the remainder of $5^{4}$ divided by 13.

5^{2} \equiv - 1 (mod 13) \Rightarrow 5^{4} \equiv 1 (mod 13)

Squaring −1 gives remainder 1.

Worked example 4

A positive integer leaves remainder 3 when divided by 4 and remainder 2 when divided by 5. Find the least possible integer.

n \in {3, 7, 11, 15, 19, \dots}; 7 = 5 (1) + 2

List candidates from one condition in increasing order and test the other. Seven is the first match, so minimality is established, not merely compatibility.

Common Traps

A valid remainder is an integer from 0 through d−1 for positive divisor d.
The exponent remainder chooses a cycle position; it is not itself the final units digit.
Cancelling a factor from a congruence may change the modulus.