Number System

Every number belongs to a family, and the families sit inside one another like boxes inside boxes. Learn the boxes once and a classification question takes you a moment.

• Natural numbers (N): 1, 2, 3, 4, …, the counting numbers. Note that 0 is not a natural number.
• Whole numbers (W): 0, 1, 2, 3, …, that is, natural numbers along with 0.
• Integers (Z): …, −3, −2, −1, 0, 1, 2, 3, …, whole numbers along with the negatives.
• Rational numbers (Q): any number that can be written as pq, where p and q are integers and q ≠ 0. Every integer is rational (7 = 71), and so are 34, −2.5 and 0.333…
• Irrational numbers: real numbers that can NOT be written as pq: √2, √5, π, 2 + √3. For a non-negative integer n, √n is rational exactly when n is a perfect square; otherwise it is irrational, so the square root of every prime is irrational. For a fraction in lowest terms, both the numerator and the denominator must be perfect squares (√0.25 = 12 is rational).
• Real numbers (R): rational and irrational together, which means every point of the number line.

So N ⊂ W ⊂ Z ⊂ Q ⊂ R, and the irrationals sit in R outside Q. A number is either rational or irrational, never both. Hence the intersection of the rationals and the irrationals is the empty set, and their union is the set of real numbers.

[[fig:0]]

What lies outside the real numbers? Square roots of negative numbers such as √-4. No real number has a negative square, so these are called imaginary numbers, and numbers of the form a + ib are complex numbers. The real numbers are a subset of the complex numbers, not the other way round.

The decimal tells you the family. Write the fraction in lowest terms and look at the denominator:

• If the denominator has no prime factor other than 2 and 5, the decimal terminates. 740 = 0.175 because 40 = 2³ × 5.
• If the denominator has any other prime (3, 7, 11, …), the decimal never ends but repeats. 512 = 0.41666… because 12 has a 3.
• A repeating decimal is pure recurring if the repetition starts right after the decimal point (0.27), and mixed recurring if a few digits come first and the repetition starts later (0.46).
• Terminating and repeating decimals are rational. Non-terminating, non-repeating decimals are irrational.

[[fig:1]]

What happens when you combine them (closure):

• rational ± rational and rational × rational are always rational. Rational ÷ non-zero rational is rational.
• rational ± irrational is always irrational. Non-zero rational × irrational is irrational.
• irrational + irrational can be either. √3 + √3 = 2√3 is irrational, but √3 + (−√3) = 0 is rational. Products behave the same way: √2 × √8 = 4.

Radhika wants to know whether 975 terminates. First reduce it: 975 = 325, and 25 = 5². Only 5s are left in the denominator, so it terminates: 325 = 0.12. The 3 in 75 disappeared after cancelling, which is exactly why you reduce first.

In the number 47,382 the digit 7 is written once, but it means seven thousand. That is the idea of place value.

• Face value of a digit is the digit itself. The face value of 7 in 47,382 is 7.
• Place value = face value × value of its place. The place value of 7 in 47,382 = 7 × 1000 = 7000. The place value of 0 is always 0, wherever it sits.

[[fig:0]]

Forming numbers from given digits. For the largest number, arrange the digits in descending order; for the smallest, arrange them in ascending order. A number cannot start with 0, though, so put the smallest non-zero digit first and the 0 right after it. With the digits 4, 0, 8, 1: largest = 8410, smallest = 1048.

Counting the digits used to write numbers. From 1 to 9 there are 9 one-digit numbers, from 10 to 99 there are 90 two-digit numbers, and from 100 to 999 there are 900 three-digit numbers. So writing 1 to 99 uses 9 × 1 + 90 × 2 = 189 digits. Beyond that, add 3 digits for every three-digit number.

Integers on the number line. A movement upward or to the right is +, downward or to the left is −. A rise from −6 to +5 is a rise of 5 − (−6) = 11 units. The rule is change = final − initial, with signs.

[[fig:1]]

Binary numbers. Our usual system works in base 10 (place values 1, 10, 100, …). The binary system works in base 2: it uses only the digits 0 and 1, and the place values from the right are 1, 2, 4, 8, 16, 32, 64, 128, …

• Binary → decimal: add the place values wherever there is a 1. 1011 = 8 + 0 + 2 + 1 = 11.
• Decimal → binary: break the number into powers of 2. 45 = 32 + 8 + 4 + 1 ⇒ 101101.
• A binary number made only of 1s is one less than a power of 2: 1111 = 16 − 1 = 15, and eight 1s = 256 − 1 = 255.

[[fig:2]]

Radhika has the digits 3, 0, 7, 5 and wants the smallest four-digit number. Ascending order is 0, 3, 5, 7, but 0 cannot lead, so she writes 3 first and then 0. The number is 3057.

Octal and hexadecimal numbers. The binary idea works for any base. In the octal system the base is 8, the digits are 0 to 7, and the place values from the right are 1, 8, 64, 512, … In the hexadecimal system the base is 16 and the digits are 0 to 9 followed by A = 10, B = 11, C = 12, D = 13, E = 14, F = 15; the place values are 1, 16, 256, …

[[fig:3]]

• To decimal: multiply each digit by its place value and add. Octal 345 = 3 × 64 + 4 × 8 + 5 = 229. Hexadecimal 2F = 2 × 16 + 15 = 47.
• From decimal: divide repeatedly by the base and read the remainders from the bottom up. 100 ÷ 8 = 12 remainder 4, 12 ÷ 8 = 1 remainder 4, 1 ÷ 8 = 0 remainder 1, so 100 is 144 in octal.
• Binary shortcut: group the bits in threes from the right for octal, and in fours for hexadecimal. 101110 = 101 | 110 = 5 | 6 = octal 56; 10101111 = 1010 | 1111 = A | F = hexadecimal AF.

How many times does a digit appear? Count place by place. From 1 to 99, each digit from 1 to 9 appears 20 times (10 times as a unit digit and 10 times as a tens digit), while 0 appears only 9 times (in 10, 20, …, 90). From 1 to 999, each digit from 1 to 9 appears 300 times and 0 appears 189 times. In general, from 1 to 10^k − 1 each digit from 1 to 9 appears k × 10^k−1 times.

For a range such as 1 to 400, the unit and tens places give 20 appearances of each digit per 100 numbers, that is 4 × 20 = 80 in all. The hundreds place then adds more: the digit 3 is the hundreds digit of all 100 numbers from 300 to 399, so it appears 80 + 100 = 180 times. The digit 5 appears 80 times, and the digit 4 appears 80 + 1 = 81 times (the extra one is 400 itself).

A prime number has exactly two different factors: 1 and itself. A composite number has more than two factors. And 1 is neither prime nor composite, because it has only one factor.

Learn the primes up to 100 by heart. There are 25 of them:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.

[[fig:0]]

A few facts settle many questions:

• 2 is the only even prime. Every other prime is odd. So if three primes add up to an even number, one of them must be 2 (odd + odd + odd is odd).
• Every prime greater than 3 is of the form 6k ± 1 (29 = 6 × 5 − 1, 31 = 6 × 5 + 1). The reverse is not true: 25 = 6 × 4 + 1 is not prime.
• To test whether a number is prime, divide it by the primes up to its square root. For 221, √221 ≈ 14.9, so test 2, 3, 5, 7, 11 and 13. Since 221 = 13 × 17, it is composite. Watch out for 91 (7 × 13), 119 (7 × 17), 133 (7 × 19), 143 (11 × 13) and 187 (11 × 17): they look prime, but they are not.

Co-prime numbers are two numbers whose only common factor is 1, that is, their HCF is 1. They need not be prime themselves; 8 and 15 are co-prime. Any two consecutive numbers are co-prime, and 1 is co-prime with every number. Two even numbers can never be co-prime, because 2 divides both.

[[fig:1]]

Twin primes are primes that differ by 2: (3, 5), (11, 13), (17, 19), (41, 43), (71, 73).

When the product of two primes is given, the smaller prime cannot be bigger than the square root of the product, so start testing from the primes just below the square root. Suppose Radhika is told that two primes multiply to 247. √247 ≈ 15.7, so she tries the primes just below 15.7. The first one, 13, divides 247, and 247 = 13 × 19.

Euler's totient: how many numbers up to N are co-prime to N. Write N = p^a q^b …; then
φ(N) = N × (1 − 1p) × (1 − 1q) × …
Only the different primes matter. For 100 = 2² × 5²: φ(100) = 100 × 12 × 45 = 40, so 40 numbers from 1 to 100 are co-prime to 100 (exactly those divisible by neither 2 nor 5). For a prime p, φ(p) = p − 1. For N > 2 the numbers co-prime to N pair up as r and N − r, so their sum is N × φ(N)2. For 12 the co-primes are 1, 5, 7, 11 and the sum is 12 × 4 ÷ 2 = 24.

Two results on primes. For every prime p > 3, p² − 1 = (p − 1)(p + 1) is divisible by 24. Since p is odd, p − 1 and p + 1 are consecutive even numbers, so their product is divisible by 8; since p is not a multiple of 3, one of them is a multiple of 3. Check: 7² − 1 = 48 = 24 × 2 and 11² − 1 = 120 = 24 × 5. Also, 3, 5, 7 is the only triple of primes of the form p, p + 2, p + 4, because one of any three such numbers is a multiple of 3.

A perfect square is a number of the form n² where n is an integer: 1, 4, 9, 16, 25, … Three tools settle almost every question of this type.

1. The prime-power test. A number is a perfect square exactly when every prime in its factorisation has an even power. 3600 = 2⁴ × 3² × 5²: all powers are even, so it is a square (60²). 1200 = 2⁴ × 3 × 5²: the power of 3 is odd, so it is not.
The same factorisation tells you what to multiply or divide by. To make 1200 a perfect square, multiply by the prime with the odd power: 1200 × 3 = 3600. To make it a square by division, divide by 3: 1200 ÷ 3 = 400.

[[fig:0]]

2. The unit-digit test, to reject options quickly. A perfect square can end only in 0, 1, 4, 5, 6 or 9. A square never ends in 2, 3, 7 or 8. Also:

• If a square ends in 0, it ends in an even number of zeros (100, 2500, 90000).
• If a square ends in 5, its tens digit is 2 (25, 225, 625).
• If a square ends in 6, its tens digit is odd (16, 36, 196, 576).

[[fig:1]]

3. Squares near a number (least number to add or subtract). Estimate the square root, then find the two squares on either side of the number. Say Radhika wants the least number to add to 2000 to get a perfect square. 44² = 1936 and 45² = 2025, so she adds 2025 − 2000 = 25. If she had to subtract instead, she would subtract 2000 − 1936 = 64.

[[fig:2]]

Counting squares in a range. The squares from a² to b² are a², (a + 1)², …, b², which makes b − a + 1 squares. So count the integers whose squares fall in the range. Between two consecutive squares n² and (n + 1)² there are exactly 2n non-square natural numbers.

Digits in the square root. If a perfect square has n digits, its square root has n2 digits when n is even and n + 12 digits when n is odd. A 6-digit square has a 3-digit root.

A number and its square root. For a question like a number minus its square root is 132, let the root be r. Then r² − r = 132 ⇒ r(r − 1) = 132 = 12 × 11, so r = 12 and the number is 144. The pattern to spot is a product of two consecutive numbers.

Cube roots of perfect cubes. The unit digit of a cube tells the unit digit of the root, and here every digit has exactly one answer. Learn the table: 1 → 1, 2 → 8, 3 → 7, 4 → 4, 5 → 5, 6 → 6, 7 → 3, 8 → 2, 9 → 9, 0 → 0. Only 2 ↔ 8 and 3 ↔ 7 exchange places.

[[fig:3]]

Radhika wants ∛10648. Cut off the last three digits: 10 | 648. The cube ends in 8, so the root ends in 2. The remaining part 10 lies between 2³ = 8 and 3³ = 27, so the tens digit is the smaller one, 2. The root is 22. Check: 22³ = 10648.

For a decimal, the number of decimal places must be a multiple of 3. Take the cube root of the digits and give the answer one third of the places: ∛0.001728 = 0.12, because 6 places become 2 places and 12³ = 1728. And ∛2764 = 34.

A divisibility rule tells you whether one number divides another without doing the full division. Each rule has a reason, and once you see the reason you will not forget the rule.

Rules based on the last digits (powers of 2 and 5). 10 = 2 × 5, 100 = 4 × 25 and 1000 = 8 × 125. So everything except the last one, two or three digits is automatically divisible by these numbers, and only the tail needs checking.

[[fig:0]]

Rules based on the digit sum (3 and 9). Each of 10, 100, 1000, … leaves remainder 1 when divided by 3 or 9. So a number leaves the same remainder as the sum of its digits. Divisible by 3 ⇔ digit sum divisible by 3; divisible by 9 ⇔ digit sum divisible by 9.

Rule of 11. Add the digits in the odd places (counting from the right), add the digits in the even places, and take the difference. If the difference is 0 or a multiple of 11, the number is divisible by 11. For 72919: odd places 9 + 9 + 7 = 25, even places 1 + 2 = 3, difference 22, so it is divisible.

[[fig:1]]

Rule of 7, 11 and 13 together. 7 × 11 × 13 = 1001. Make groups of three digits from the right and find the alternating sum of the groups. If that result is divisible by 7, 11 or 13, so is the number. 371371 gives groups 371 | 371 and 371 − 371 = 0, so it is divisible by 7, 11 and 13. For 1,001,077 the groups are 1 | 001 | 077 and 77 − 1 + 1 = 77 = 7 × 11, so it is divisible by 7 and 11 but not by 13.

Composite divisors: split into co-prime parts. A number is divisible by 6 if it is divisible by both 2 and 3; by 12 if by 3 and 4; by 15 if by 3 and 5; by 18 if by 2 and 9; by 24 if by 3 and 8; by 36 if by 4 and 9; by 72 if by 8 and 9; by 88 if by 8 and 11. The two parts must be co-prime. 24 = 4 × 6 does NOT work, because 4 and 6 share a 2 (12 is divisible by both 4 and 6 but not by 24).

Nearest multiples and the least number to add or subtract. Divide the number by the divisor and look at the remainder r.

• Least number to subtract = r.
• Least number to add = divisor − r (if r = 0, nothing needs to be added; the answer is 0 unless the question asks for the least positive number).
• Largest n-digit multiple = (largest n-digit number) − r.
• Smallest n-digit multiple = (smallest n-digit number) + (divisor − r), unless r = 0.

Radhika wants the largest 4-digit number divisible by 37. 9999 ÷ 37 leaves remainder 9999 − 37 × 270 = 9, so the answer is 9999 − 9 = 9990.

[[fig:2]]

Digital root: add the digits again and again. Add the digits of a number. If the answer still has two or more digits, add its digits again, and go on till one digit is left. That last digit is the digital root. For 7865: 7 + 8 + 6 + 5 = 26, and 2 + 6 = 8.

[[fig:3]]

The digital root of N is the remainder when N is divided by 9 (write 9 when the remainder is 0). The reason is simple: 10, 100, 1000, … all leave remainder 1 on division by 9, so a number and its digit sum leave the same remainder.

This gives a quick check for answers. The digital root of a sum or a product is found from the digital roots of the numbers. Radhika multiplies 47 × 38 and gets 1786. The digital roots are 2 and 2, so the product must have digital root 4. For 1786 we get 1 + 7 + 8 + 6 = 22 and 2 + 2 = 4 ✓. If an option has a different digital root, it is wrong at once.

Two more uses: a perfect square always has digital root 1, 4, 7 or 9, so a number with digital root 2, 3, 5, 6 or 8 is never a perfect square. And for a big power, find the digital root of the base and follow its cycle: 4, 7, 1, 4, 7, 1 … for the powers of 4 (since 4³ = 64 has digital root 1).

Testing with a multiplier (the osculator method). For a divisor that ends in 9 or 1, cut off the last digit, multiply it by a small fixed number k, and then ADD it to the rest of the number (divisor ending in 9) or SUBTRACT it from the rest (divisor ending in 1). Repeat until the number is small enough to see. For a divisor M ending in 9, k = (M + 1) ÷ 10 and you add; for M ending in 1, k = (M − 1) ÷ 10 and you subtract. The reason, for M = 19: if N = 10 × rest + last digit, then 10 × (rest + 2 × last digit) = N + 19 × last digit, so the new number is divisible by 19 exactly when N is.

For divisors ending in 3 or 7, use a multiple of the divisor that ends in 9 or 1:

Test 2,793 for 19: 279 + 2 × 3 = 285, then 28 + 2 × 5 = 38 = 19 × 2, so it is divisible. Test 4,018 for 7: 401 − 2 × 8 = 385, then 38 − 2 × 5 = 28 = 7 × 4, so it is divisible.

Rules for 99, 999 and 101. 100 leaves remainder 1 on division by 99, so a number and the sum of its two-digit groups (made from the right) leave the same remainder on division by 99, and so also by 3, 9, 11 and 33. For 7,425: 74 + 25 = 99, so it is divisible by 99. In the same way 1000 leaves remainder 1 on division by 999, so add the three-digit groups: 2,997 gives 2 + 997 = 999, so it is divisible by 999, and therefore by 27 and 37. For 101, the number 100 leaves remainder −1, so take the alternating sum of the two-digit groups from the right: 10,302 gives 02 − 03 + 1 = 0, so it is divisible by 101.

A shortcut for 8. 100 leaves remainder 4 on division by 8, and 1000 is a multiple of 8. So look at the last two digits; if the hundreds digit is odd, add 4 to them first, and if it is even, use them as they are. For 3,176 the hundreds digit 1 is odd and 76 + 4 = 80, which is divisible by 8 ✓. For 5,364 the hundreds digit 3 is odd and 64 + 4 = 68, which is not divisible by 8, so the number is not either.

In this type one digit (or two) of the number is hidden, and you are told that the number is divisible by something. Turn the divisibility rule into a small equation in the hidden digit. A digit can only be 0 to 9, and that limit does half the work for you.

Step 1: break the divisor into co-prime parts. 72 = 8 × 9, 88 = 8 × 11, 36 = 4 × 9, 40 = 8 × 5, 33 = 3 × 11, 15 = 3 × 5, 105 = 3 × 5 × 7.

Step 2: apply the last-digits rule first. The rules of 2, 4, 5 and 8 involve only the tail, so they usually fix the last digit straight away, or narrow it to two or three values.

Step 3: then apply the digit-sum rule or the rule of 11. These involve every digit. Write the sum of the known digits, add the unknown, and see which values make it a multiple of 3, 9 or 11.

[[fig:0]]

Radhika has to fill the blank in 52*6 so that the number is divisible by 9. The known digits add up to 5 + 2 + 6 = 13. The next multiple of 9 is 18, so the digit is 18 − 13 = 5. (Reaching 27 would need the digit 14, which is impossible.) The number is 5256.

[[fig:1]]

Two unknowns. Use one rule to get the possible values of one digit, the other rule for the second digit, and then pick what the question asks for: the maximum sum, the minimum product, or a particular pair. Always list every possibility. In maximum and minimum questions, the first value you find is often not the answer.

Rule of 11 with unknowns. The difference (odd-place sum − even-place sum) can be 0, 11, −11, 22, … With one unknown digit, usually only one of these is reachable. With two unknowns, check both 0 and ±11.

"Which cannot be the value" questions. Find all the values that work and pick the option outside that list. If the unknown sits inside the last digits that decide divisibility by 4 or 8, write all the multiples in that range and read off the digit.

Sometimes the question gives no ordinary number at all. Instead it gives an expression like 5⁴⁰ + 5⁴¹ + 5⁴², or a pattern like a six-digit number formed by repeating a three-digit number. Here a few facts about structure do the work that digit rules did earlier.

1. Take the common power out. aⁿ + aⁿ⁺¹ + aⁿ⁺² = aⁿ(1 + a + a²). So 5⁴⁰ + 5⁴¹ + 5⁴² = 5⁴⁰ × (1 + 5 + 25) = 5⁴⁰ × 31. It is divisible by 31, by 5, by 31 × 5 = 155, and so on.

[[fig:0]]

2. aⁿ − bⁿ and aⁿ + bⁿ.

• aⁿ − bⁿ is always divisible by (a − b).
• aⁿ − bⁿ is divisible by (a + b) when n is even.
• aⁿ + bⁿ is divisible by (a + b) when n is odd.

Take 9⁶ − 1. Here a = 9, b = 1 and n = 6 is even, so it is divisible by 9 − 1 = 8 and by 9 + 1 = 10. Also 9⁶ − 1 = 81³ − 1, so it is divisible by 81 − 1 = 80 as well.

3. Patterns of repeated digits.

• aaa = a × 111 = a × 3 × 37
• abab = ab × 101
• abcabc = abc × 1001 = abc × 7 × 11 × 13
• A two-digit number plus its reverse: (10a + b) + (10b + a) = 11(a + b), always a multiple of 11. The difference is 9(a − b), always a multiple of 9.

[[fig:1]]

4. Shuffling digits. Rearranging the digits does not change the digit sum, so divisibility by 3 and 9 survives any shuffle. Divisibility by 2, 4, 5, 8 and 11 depends on positions, so it may be lost.

5. Sums and differences. If N and k are both divisible by d, then N + k and N − k are divisible by d. If k is not divisible by d, then N + k is not divisible by d either. So when 21 is added to a multiple of 33, the result is still divisible by 3 (because 21 is), but no longer by 11.

6. Consecutive numbers. The product of n consecutive integers is divisible by n! (1 × 2 × … × n). So two consecutive numbers give an even product, three consecutive numbers give a multiple of 6, and n³ − n = (n − 1)n(n + 1) is always divisible by 6.

How many numbers from 1 to 500 are divisible by 7? You do not list them. From 1 to N, the multiples of d are d, 2d, 3d, …, and their count is the integer part of Nd, written ⌊Nd⌋. From 1 to 500 that is ⌊5007⌋ = 71, since 7 × 71 = 497.

[[fig:0]]

A range that does not start from 1. Count up to the top and subtract the count below the start:
multiples of d from a to b (both included) = ⌊bd⌋ − ⌊a − 1d⌋.
Or use the AP way: (last multiple − first multiple) ÷ d + 1.
For the multiples of 9 from 200 to 300, the first multiple is 207 and the last is 297, so the count is 297 − 2079 + 1 = 11.

"Between" versus "from … to". Between 100 and 200 normally leaves out the end points; from 100 to 200 or including both keeps them. This matters only if an end point is itself a multiple, so always look at the end points.

Divisible by both a and b. A number divisible by both is divisible by their LCM. When a and b are co-prime the LCM is just a × b: divisible by both 7 and 11 ⇔ divisible by 77. If they share a factor, the LCM is smaller: divisible by both 4 and 6 ⇔ divisible by 12, not 24.

Divisible by a or b (inclusion–exclusion). Count(a) + Count(b) − Count(both). The numbers divisible by both were counted twice, so we remove them once.

Neither a nor b = total − Count(a or b).
Divisible by a but not by b = Count(a) − Count(both).
Divisible by a or b but not by both = Count(a) + Count(b) − 2 × Count(both).

[[fig:1]]

Three conditions. Divisible by a or b or c:
n(a) + n(b) + n(c) − n(ab) − n(bc) − n(ca) + n(abc),
where n(ab) counts the numbers divisible by the LCM of a and b, and n(abc) those divisible by the LCM of all three. The numbers divisible by all three were added three times and removed three times, so they must be added back once. From 1 to 100, the numbers divisible by none of 2, 3 and 5 are 100 − (50 + 33 + 20) + (16 + 10 + 6) − 3 = 26 (these are exactly the numbers co-prime to 30).

The unit digit of a product depends only on the unit digits of the numbers being multiplied. In 4,327 × 5,689 only 7 × 9 = 63 matters, so the product ends in 3. Sums and differences follow the same rule: work only with the last digits.

Powers repeat in cycles. Write the powers of 2: 2, 4, 8, 16, 32, 64, … The unit digits are 2, 4, 8, 6, 2, 4, 8, 6, … and they repeat every 4 steps. This is called cyclicity, and every digit has a cycle of length 1, 2 or 4.

[[fig:0]]

The method for (…a)ⁿ. Take only the last digit a. Divide the power n by 4 and look at the remainder r:

• r = 1, 2, 3 ⇒ the unit digit is that of a^r.
• r = 0 ⇒ the unit digit is that of a⁴ (6 for 2, 4, 6, 8 and 1 for 3, 7, 9).

To divide n by 4, you need only the last two digits of n.

[[fig:1]]

Find the unit digit of 3⁵⁷: 57 = 4 × 14 + 1, so r = 1 and the unit digit is 3¹ = 3. For 8³⁰: 30 = 4 × 7 + 2, so r = 2 and the unit digit is that of 8² = 64, which is 4.

Squares and their unit digits (useful for rejecting options): a square ends only in 0, 1, 4, 5, 6 or 9. A number ending in 1 or 9 has a square ending in 1; ending in 2 or 8 gives 4; ending in 3 or 7 gives 9; ending in 4 or 6 gives 6.

Last two or three digits. For a product, keep only the last two (or three) digits of each number and multiply, keeping the last two (or three) digits at every step. The last three digits of 2,345 × 6,789 are the last three digits of 345 × 789 = 272205, that is, 205.

Factorials. From 5! onwards every factorial contains 2 × 5, so every factorial from 5! onwards ends in 0. In 1! + 2! + 3! + … + 100!, only 1! + 2! + 3! + 4! = 33 decides the unit digit, and it is 3.

Shortcuts for 4, 9 and 5. Powers of 4 and of 9 repeat in a cycle of two, so only odd or even matters: 4^odd ends in 4 and 4^even in 6; 9^odd ends in 9 and 9^even in 1. A product of odd numbers that includes a number ending in 5 always ends in 5. When the power is a factorial, note that n! is a multiple of 4 for every n ≥ 4, so a^n! has the unit digit of a⁴. For example, 3^5! = 3¹²⁰ ends in 1.

Last two digits of a power. If a is co-prime to 10 (it ends in 1, 3, 7 or 9), then a²⁰ always ends in 01. So reduce the power modulo 20 and work with what is left: 3⁴⁵ = (3²⁰)² × 3⁵ ends in the last two digits of 3⁵ = 243, that is 43. If a number ends in 1, write it as 10m + 1; then the last two digits of (10m + 1)ⁿ are the last digit of m × n followed by 1. For 21³⁷: m = 2, 2 × 37 = 74, so the tens digit is 4 and the number ends in 41. A number ending in 25 or in 76 keeps that ending in every power: 25ⁿ ends in 25 and 76ⁿ ends in 76.

Every division can be written in one line:

Dividend = Divisor × Quotient + Remainder, with 0 ≤ Remainder < Divisor.

When 47 is divided by 6: 47 = 6 × 7 + 5. Dividend 47, divisor 6, quotient 7, remainder 5. The remainder is always smaller than the divisor, and this one fact settles many find the divisor questions.

[[fig:0]]

Remainder by a rule, without long division.

• By 2, 4, 8 (or 5, 25, 125): the remainder of the last 1, 2 or 3 digits.
• By 3 or 9: the remainder of the digit sum. For 5,237 ÷ 9 the digit sum is 17, so the remainder is 17 − 9 = 8.
• By 11: (sum of odd-place digits − sum of even-place digits), adjusted to lie between 0 and 10.

Divisor of the divisor. If N ÷ D leaves remainder r, and d divides D, then N ÷ d leaves the same remainder as r ÷ d. The reason: N = Dk + r, and Dk is a multiple of d. So if N ÷ 36 leaves 25, then N ÷ 12 leaves the remainder of 25 ÷ 12, which is 1. This works only when d is a factor of D.

Remainders of sums and multiples. If A ÷ d leaves a and B ÷ d leaves b, then (A + B) ÷ d leaves the remainder of (a + b), and k × A ÷ d leaves the remainder of k × a. So:

• If a + b is more than the actual remainder of the sum, the excess is the divisor: d = (a + b) − (remainder of the sum). If a + b equals the remainder of the sum, nothing wrapped around and d is not fixed (remainders 2 and 3 with sum remainder 5 suit every divisor above 5).
• If N leaves 15 and 10N leaves 6, then 150 and 6 differ by a multiple of d, so d divides 144 and d > 15.

Divisor, quotient and remainder linked. Suppose the divisor is 4 times the quotient and 3 times the remainder, and the remainder is 20. Then divisor = 3 × 20 = 60, quotient = 60 ÷ 4 = 15 and dividend = 60 × 15 + 20 = 920. Find the divisor first, from the remainder.

Two numbers with a given difference. If the difference is 2,000 and larger ÷ smaller gives quotient 5 and remainder 40, then L = 5S + 40 and L − S = 2000 ⇒ 4S + 40 = 2000 ⇒ S = 490.

Successive division. When N is divided by 3, the quotient by 5, and that quotient by 7, work backwards from the last quotient: number = (((last quotient × 7) + r₃) × 5 + r₂) × 3 + r₁.

[[fig:1]]

Radhika divides 2,000 by a number and gets quotient 45 and remainder 20. The divisor is 2000 − 2045 = 198045 = 44.

When the dividend is a huge product or a huge power, we never calculate it. We replace each number by its remainder and work only with small numbers. This is allowed because remainders multiply and add just like the numbers themselves.

1. Product rule. The remainder of (A × B × C) ÷ d equals the remainder of (r_A × r_B × r_C) ÷ d, where r_A is the remainder of A ÷ d, and so on. The same is true for sums and differences.

2. Negative remainders. When a number is just below a multiple of the divisor, its remainder can be written as negative. 19 ÷ 20 leaves 19, but 19 = 20 − 1, so we can treat it as −1. Powers then become easy: (−1)^even = 1 and (−1)^odd = −1. If the final answer is negative, add the divisor to make it positive: −1 on division by 20 means remainder 19.

[[fig:0]]

3. Power rule: look for 1 or −1. For aⁿ ÷ d:

• If a leaves 1, then aⁿ leaves 1 for every n.
• If a leaves −1 (a = d − 1), then aⁿ leaves 1 when n is even and d − 1 when n is odd.
• Otherwise, find a small power of a that leaves 1 or −1, and break n using it.

Take 2¹⁰⁰ ÷ 9. Here 2³ = 8 = 9 − 1 leaves −1. So 2¹⁰⁰ = (2³)³³ × 2 → (−1)³³ × 2 = −2, and the remainder is 9 − 2 = 7.

[[fig:1]]

4. Fermat's little theorem. If p is a prime and a is not a multiple of p, then a^p−1 ÷ p leaves remainder 1. So 5¹² ÷ 13 leaves 1, and 5⁶² = (5¹²)⁵ × 5² leaves the remainder of 25 ÷ 13, which is 12. (Euler's theorem, a more general version, says a^φ(n) ÷ n leaves 1 when a and n are co-prime. For SSC, Fermat and the idea of finding a power that gives ±1 are enough.)

5. Remainder of an expression in n. If n ÷ d leaves r, then any polynomial in n, such as n² + 3n + 1, leaves the same remainder as r² + 3r + 1. Put the remainder in place of n.

6. Polynomial remainder theorem. When a polynomial f(x) is divided by (x − a), the remainder is f(a). For a divisor (2x + 1), put x = −12.

Standard results (n any natural number):

• (aⁿ + 1) ÷ (a + 1): remainder 0 if n is odd, 2 if n is even (for a > 1).
• (aⁿ − 1) ÷ (a + 1): remainder 0 if n is even.
• (aⁿ + a) ÷ (a + 1): remainder a − 1 if n is odd, 0 if n is even, because aⁿ → (−1)ⁿ.

7. Wilson's theorem. If p is a prime, then (p − 1)! leaves remainder p − 1 on division by p (that is, (p − 1)! + 1 is divisible by p). So 10! ÷ 11 leaves 10. A useful by-product: (p − 2)! leaves remainder 1, because (p − 1)! = (p − 1) × (p − 2)! and p − 1 behaves like −1. So 11! ÷ 13 leaves 1. If n ≥ p for a prime p, then n! is a multiple of p and leaves 0. The theorem needs p to be prime: for the composite 6, 5! = 120 leaves 0, not 5.

8. Euler's theorem in use. φ(n) is the number of integers from 1 to n that are co-prime to n (see co-prime numbers). If a and n are co-prime, then a^φ(n) ÷ n leaves remainder 1. This works for a composite divisor, where Fermat's theorem cannot be used (Fermat is the case n = p, φ(p) = p − 1). For 7¹⁰⁰ ÷ 15: φ(15) = 15 × 23 × 45 = 8, so 7⁸ leaves 1. Now 100 = 8 × 12 + 4, so 7¹⁰⁰ leaves the same remainder as 7⁴ = 2401, which is 1.

9. Two different remainders. Find the numbers that leave remainder 3 when divided by 5 and remainder 4 when divided by 7. The divisors are co-prime, so there is exactly one such number below 5 × 7 = 35, and every other one differs from it by a multiple of 35. List the numbers of the form (bigger divisor) × k + (its remainder), here 7k + 4 = 4, 11, 18, …, and test each against the other condition. 18 ÷ 5 leaves 3 ✓. So the numbers are 18, 53, 88, … , that is, 35t + 18. (When divisor − remainder is the same for every divisor, the LCM method of the LCM and HCF chapter is quicker.)

Every factor of a number is built from the same primes as the number, with powers that are not larger. If N = 2³ × 5², a factor looks like 2^x × 5^y with x = 0, 1, 2, 3 (4 choices) and y = 0, 1, 2 (3 choices). So N has 4 × 3 = 12 factors, and the rest of this type grows from this one picture.

[[fig:0]]

Number of factors. If N = p^a × q^b × r^c …, then the number of factors = (a + 1)(b + 1)(c + 1)… This count includes 1 and N. For factors other than 1 and N, subtract 2.

Sum of factors. (1 + p + p² + … + p^a) × (1 + q + … + q^b) × …
Take 540 = 2² × 3³ × 5. Number of factors = 3 × 4 × 2 = 24. Sum of factors = (1 + 2 + 4)(1 + 3 + 9 + 27)(1 + 5) = 7 × 40 × 6 = 1680.

Product of factors. N^d2, where d is the number of factors (factors pair up as a × Na).

Factors with a condition: fix the powers.

• Odd factors: allow only the power 0 for 2. For 540 that gives (3 + 1)(1 + 1) = 8 odd factors. Even factors = total − odd = 24 − 8 = 16.
• Perfect-square factors: every power must be even. For p^a the even choices are 0, 2, 4, …, which gives ⌊a2⌋ + 1 choices.
• Factors divisible by k: put k's primes into the factor first and let the remaining powers vary. For divisible by 18 but not by 36, the power of 2 must be exactly 1 and the power of 3 at least 2.

[[fig:1]]

Numbers with an exact number of factors.

• Exactly 2 factors ⇔ prime.
• Exactly 3 factors ⇔ square of a prime (4, 9, 25, 49, …).
• An odd number of factors ⇔ perfect square.

"n divides N and leaves remainder r". Then n divides N − r exactly and n > r. So count the factors of N − r that are greater than r.

More results from the power form. Let N = p^a q^b … have d factors.

• Ways to write N as a product of two factors (order ignored) = d2, or d + 12 if N is a perfect square. If the order matters, the count is d.
• Ways to write N as a product of two co-prime factors (order ignored) = 2^k−1, where k is the number of different primes in N.
• Sum of odd factors = the sum formula with the prime 2 left out. Sum of even factors = total sum − sum of odd factors.
• Sum of the reciprocals of all factors = sum of factorsN.

For 540 = 2² × 3³ × 5: d = 24, so there are 12 ways to write it as a product of two factors. With k = 3 there are 2² = 4 co-prime pairs: (1, 540), (4, 135), (5, 108), (20, 27). The sum of odd factors is (1 + 3 + 9 + 27)(1 + 5) = 240, so the sum of even factors is 1680 − 240 = 1440. The sum of the reciprocals of the factors is 1680540 = 289.

Factorial. n! = 1 × 2 × 3 × … × n, and 0! = 1. Keep the first few values ready: 1! = 1, 2! = 2, 3! = 6, 4! = 24, 5! = 120, 6! = 720, 7! = 5040, 8! = 40320. Factorials grow so fast that a question like n + n! = some number is solved just by looking at this list.

Trailing zeros come from 10 = 2 × 5. Each pair of one 2 and one 5 in the prime factorisation gives one zero at the end. So

number of trailing zeros = the smaller of (power of 2, power of 5).

[[fig:0]]

Multiply 25 × 48 × 35. Here 25 = 5², 48 = 2⁴ × 3 and 35 = 5 × 7, so the power of 5 is 3 and the power of 2 is 4. That makes 3 pairs, and the product ends in 3 zeros (it is 42000).

A number ending in k zeros has a square ending in 2k zeros and a cube ending in 3k zeros, because every 2 and every 5 gets doubled or tripled.

Highest power of a prime p in n! (Legendre's method). Count the multiples of p, then of p², p³, …, and add:
power of p in n! = ⌊np⌋ + ⌊np²⌋ + ⌊np³⌋ + …
In practice, keep dividing n by p and add the quotients.

• Zeros at the end of 100!: power of 5 = 20 + 4 = 24 (there are always more 2s than 5s), so 24 zeros.
• Highest power of 3 in 30!: 10 + 3 + 1 = 14.

[[fig:1]]

Highest power of a composite number. Break it into primes and see which prime runs out first. For 12 = 2² × 3 in 30!, the power of 2 is 15 + 7 + 3 + 1 = 26, enough for 13 copies of 2², and the power of 3 is 14. The smaller one, 13, is the answer.

Highest power in a given product. Factorise each number and add the powers of the prime you want.

Which factorial ends in exactly k zeros? The count of zeros rises only when n reaches a multiple of 5, so n!, (n + 1)!, …, (n + 4)! have the same number of zeros when n is a multiple of 5. Start near n = 4k, find the zeros of that n, and move to the multiple of 5 that gives k. Since 100! has 24 zeros, 100!, 101!, …, 104! all end in exactly 24 zeros, and the smallest n is 100. At a multiple of 25 the count jumps by 2 (24! has 4 zeros but 25! has 6), so some numbers of zeros, such as 5, 11, 17 and 23, never occur at all.

The last non-zero digit. To find the digit just before the trailing zeros, write n! = 2^x × 5^y × m, where m has no factor 2 or 5. There are always more 2s than 5s, so the last non-zero digit is the unit digit of 2^x−y × m. For 10!: 10! = 2⁸ × 3⁴ × 5² × 7, so m = 3⁴ × 7 = 567 and 2⁸⁻² = 64. The unit digits give 4 × 7 = 28, so the last non-zero digit is 8 (indeed 10! = 3628800).

You never need to add a long list of numbers one by one. Almost every series in this chapter is either an equally spaced list (an AP) or can be paired into one.

Equally spaced numbers. For any list with a fixed gap:

• Number of terms = last − firstgap + 1
• Sum = number of terms × first + last2

The reason is simple. Pair the first term with the last, the second with the second-last, and so on; every pair has the same sum.

[[fig:0]]

Standard results.

[[fig:1]]

Radhika adds 1 to 20 and gets 20 × 212 = 210. In the same way, the squares of 1 to 10 add to 10 × 11 × 216 = 385, the cubes of 1 to 10 add to 55² = 3025, and the odd numbers 1, 3, …, 39 (twenty of them) add to 20² = 400.

Alternating series: pair them. In 1 − 2 + 3 − 4 + …, each pair (1 − 2), (3 − 4), … gives −1, so count the pairs.

Differences of squares: pair them too. a² − b² = (a + b)(a − b). When the numbers are consecutive, a − b = 1, so a² − b² = a + b. A long series like 40² − 39² + 38² − 37² + … + 2² − 1² then becomes 40 + 39 + 38 + … + 1 = 820.

Mixed patterns. If a series repeats a two-step pattern (like 1, 4, 5, 8, 9, 12, …), treat each pattern as one term; the groups form an equally spaced list.

Divisibility of a sum. n(n + 1)2 is a product, so its factors are easy to see. The sum of 1 to 20 is 10 × 21, which is divisible by 3, 5, 7, 10, 21, …

Consecutive natural numbers differ by 1 (7, 8, 9); consecutive even or odd numbers differ by 2 (14, 16, 18 or 15, 17, 19). The neatest way to name them is to put the middle number at the centre:

• three consecutive numbers: n − 1, n, n + 1
• three consecutive even (or odd) numbers: n − 2, n, n + 2
• five consecutive even (or odd) numbers: n − 4, n − 2, n, n + 2, n + 4

When the sum is given. With this naming the extra parts cancel, so middle number = sum ÷ number of terms (for an odd number of terms). If three consecutive even numbers add up to 96, the middle one is 32 and the numbers are 30, 32, 34.

[[fig:0]]

When the product is given. The numbers are close to each other, so they sit near the square root (for two numbers) or the cube root (for three). Suppose two consecutive odd numbers multiply to 399. √399 ≈ 20, so the numbers are 19 and 21 (19 × 21 = 399). If three consecutive odd numbers multiply to 4845, ∛4845 ≈ 16.9, so the middle odd number is 17, and 15 × 17 × 19 = 4845 ✓. Always confirm by multiplying. The unit digit (5 × 7 × 9 → 5) is a quick check as well.

When the difference of squares is given. For consecutive odd (or even) numbers n and n + 2:
(n + 2)² − n² = (n + 2 + n)(2) = 2 × (sum of the two numbers).
So the sum of the two numbers = difference of squares ÷ 2. If the squares of two consecutive even numbers differ by 60, the numbers add up to 30, so they are 14 and 16. Check that the numbers come out of the kind the question asks for, even or odd.

Squares of consecutive numbers. For five consecutive odd numbers with middle m, the sum of the squares is 5m² + 2(2² + 4²) = 5m² + 40, so the average of the squares is m² + 8.

Two-digit numbers. If the tens digit is a and the units digit is b, the number is not a × b or a + b; it is 10a + b. The reversed number is 10b + a. Two results follow from these two lines:

• Sum of a number and its reverse = 11(a + b)
• Difference = 9(a − b)

So the number increases by 27 when the digits are reversed means 9(b − a) = 27, that is, b − a = 3. Combine it with the sum of the digits and the question is over.

[[fig:0]]

The digits of Radhika's two-digit number add up to 11, and reversing the digits increases the number by 45. Then b − a = 5 and a + b = 11, so b = 8, a = 3, and the number is 38. Check: 83 − 38 = 45 ✓.

Three-digit numbers. 100a + 10b + c. Reversing gives 100c + 10b + a, and the difference is 99(a − c).

Number puzzles in words. Turn each sentence into an equation, one unknown at a time:

• A number's fifth part increased by 5 → x5 + 5.
• If A gives one to B, they become equal → A − 1 = B + 1, so A − B = 2.
• x is three times y → x = 3y.

Two numbers with sum S and difference D are S + D2 and S − D2.

The assumption method (heads and legs, coins, tickets). Assume everything is of the cheaper (or smaller) kind, find the shortage, and divide it by the difference per item. Suppose 30 animals, hens and goats, have 80 legs. If all were hens there would be 60 legs, a shortage of 20. Each goat adds 2 legs, so there are 10 goats and 20 hens.

[[fig:1]]

Testing options. In this type the options are usually small numbers. If the equation looks messy (a quadratic, or fractions), put the options in; the right one fits quickly.