Number System, HCF, LCM and Remainders

The number system is the foundation of quantitative aptitude. Questions on divisibility, factors, HCF and LCM, remainders, unit digits and number puzzles appear in nearly every test, and the same few ideas solve all of them. Every worked answer below is checked by computation.

1. Classification of numbers

• Natural numbers: 1, 2, 3, ... Whole numbers: 0, 1, 2, ...
• Integers: ..., -2, -1, 0, 1, 2, ...
• Rational numbers: $p/q$ with $q\ne 0$. Their decimals terminate or repeat.
• Irrational numbers: non-terminating, non-repeating decimals ($\sqrt{2}$, $\pi$).
• Prime numbers: exactly two factors, 1 and itself (2, 3, 5, 7, 11, ...). 2 is the only even prime. 1 is neither prime nor composite.
• Co-prime numbers: their HCF is 1 (8 and 15 are co-prime though neither is prime).

Primes up to 100: 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 (25 primes).

def is_prime(n):
    return n > 1 and all(n % d for d in range(2, int(n ** 0.5) + 1))

primes = [n for n in range(1, 101) if is_prime(n)]
assert len(primes) == 25 and primes[-1] == 97

2. Divisibility rules

def div11(n):
    d = [int(c) for c in str(n)]
    return (sum(d[::2]) - sum(d[1::2])) % 11 == 0

def div7(n):
    while n >= 100:
        n = abs(n // 10 - 2 * (n % 10))
    return n % 7 == 0

assert all(div11(n) == (n % 11 == 0) for n in range(1, 20000))
assert all(div7(n) == (n % 7 == 0) for n in range(1, 20000))
assert 918082 % 11 == 0 and div11(918082)          # alternating sum: (9+8+8) - (1+0+2) = 22
assert sum(int(c) for c in "7413") % 3 == 0 and 7413 % 3 == 0

Example 1. What digit $d$ makes $4d521$ divisible by 3? Digit sum is $4+d+5+2+1=12+d$, divisible by 3 when $d\in \{0,3,6,9\}$.

Example 2. For which digit $k$ is $5k24$ divisible by 11? Odd-position digits sum to $5+2=7$ and even-position digits to $k+4$. The difference $7-(k+4)=3-k$ must be a multiple of 11, so $k=3$. Check: $5324=11\times 484$.

assert [d for d in range(10) if int(f"4{d}521") % 3 == 0] == [0, 3, 6, 9]
assert [k for k in range(10) if int(f"5{k}24") % 11 == 0] == [3] and 5324 == 11 * 484

3. Factors and the factor-count formula

If $N=p_1^{a_1}{p}_2^{a_2}\cdots p_k^{a_k}$ (prime factorisation), then

• Number of factors $=(a_1+1)(a_2+1)\cdots (a_k+1)$.
• Sum of factors $=\prod \frac{p_i^{a_i+1}-1}{p_i-1}$.
• Number of ways to write $N$ as a product of two factors $=\frac{1}{2}\times$ (number of factors) (when $N$ is not a perfect square).
• A number is a perfect square exactly when every exponent is even, so it has an odd number of factors.

Example 3. How many factors does 360 have, and what is their sum? $360=2^3\cdot 3^2\cdot 5$. Factors: $(3+1)(2+1)(1+1)=24$. Sum: $\frac{2^4-1}{1}\cdot \frac{3^3-1}{2}\cdot \frac{5^2-1}{4}=15\cdot 13\cdot 6=1170$.

def factors(n):
    return [d for d in range(1, n + 1) if n % d == 0]

f360 = factors(360)
assert len(f360) == 24 and sum(f360) == 1170
assert len(factors(36)) % 2 == 1                    # a perfect square has an odd number of factors
assert len(factors(48)) == (4 + 1) * (1 + 1)        # 48 = 2^4 * 3

Example 4. How many odd factors does 360 have? Drop the factor 2: $3^2\cdot 5$ has $(2+1)(1+1)=6$ factors, all odd. So 6 odd factors and $24-6=18$ even factors.

assert len([d for d in f360 if d % 2]) == 6

Number of trailing zeros in $n!$ is the number of factors of 5: $\lfloor n/5\rfloor +\lfloor n/25\rfloor +\lfloor n/125\rfloor +\cdots$.

from math import factorial

def trailing_zeros(n):
    z, p = 0, 5
    while p <= n:
        z += n // p
        p *= 5
    return z

assert trailing_zeros(100) == 24 and trailing_zeros(125) == 31
assert all(trailing_zeros(n) == len(str(factorial(n))) - len(str(factorial(n)).rstrip("0")) for n in (10, 25, 50, 100, 125))

5. HCF and LCM

• HCF (GCD): the largest number dividing all of them. Product of the lowest powers of the common primes.
• LCM: the smallest number divisible by all of them. Product of the highest powers of all primes involved.
• For two numbers: $\text{HCF}\times \text{LCM}=a\times b$. (This does not extend to three numbers.)
• Euclid's algorithm: $\text{HCF}(a,b)=\text{HCF}(b,a\mathrm{mod}b)$.
• For fractions: HCF of fractions $=\frac{\text{HCF of numerators}}{\text{LCM of denominators}}$; LCM of fractions $=\frac{\text{LCM of numerators}}{\text{HCF of denominators}}$.

from math import gcd
from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

assert gcd(84, 126) == 42 and lcm(84, 126) == 252
assert gcd(84, 126) * lcm(84, 126) == 84 * 126
assert reduce(gcd, [12, 18, 24]) == 6 and reduce(lcm, [12, 18, 24]) == 72
assert 12 * 18 * 24 != 6 * 72                           # the product rule fails for three numbers

Typical application types

Type A: the largest size that divides several quantities exactly. HCF. Three ropes of 48 m, 72 m and 120 m are cut into equal pieces of the greatest possible length. What is the length, and how many pieces? HCF = 24 m; pieces: $2+3+5=10$.

Type B: events repeating together. LCM. Three bells ring every 6, 8 and 12 minutes and ring together at 9:00. When next together? LCM = 24 minutes, so 9:24.

Type C: the smallest number leaving the same remainder. Smallest number which leaves remainder 5 when divided by 6, 8 and 12? $\text{LCM}+5=29$.

Type D: the smallest number that is divisible after adding or subtracting. Smallest number that when increased by 7 is divisible by 12, 16 and 18? LCM = 144, so $144-7=137$.

Type E: the largest number that divides $a$, $b$, $c$ leaving remainders $r_1$, $r_2$, $r_3$. HCF of $(a-r_1,b-r_2,c-r_3)$. Largest number dividing 245, 1029 leaving remainders 5 and 4? HCF of 240 and 1025 = 5. Check: the divisor must exceed the remainders, and 5 is not greater than 5. So no such number from this method (a deliberate trap, since a remainder must be smaller than the divisor).

assert gcd(gcd(48, 72), 120) == 24 and 48 // 24 + 72 // 24 + 120 // 24 == 10
assert reduce(lcm, [6, 8, 12]) == 24
assert reduce(lcm, [6, 8, 12]) + 5 == 29 and all(29 % d == 5 for d in (6, 8, 12))
assert reduce(lcm, [12, 16, 18]) - 7 == 137 and all((137 + 7) % d == 0 for d in (12, 16, 18))
assert gcd(245 - 5, 1029 - 4) == 5                      # the candidate 5 is not larger than the remainder 5: invalid, so no such number

6. Remainders

Basic facts

• If $N=dq+r$ then $0\le r<d$.
• Remainders add and multiply: $(a+b)\mathrm{mod}m=((a\mathrm{mod}m)+(b\mathrm{mod}m))\mathrm{mod}m$, and likewise for products and powers.
• A negative remainder can be converted: remainder $-1$ mod $m$ is $m-1$.

Example 5. Remainder when $7^{100}$ is divided by 6? $7\equiv 1(\mathrm{mod}6)$, so $7^{100}\equiv 1$. Remainder 1.

Example 6. Remainder when $2^{50}$ is divided by 7? Powers of 2 mod 7 cycle with period 3: 2, 4, 1. $50=3\cdot 16+2$, so the remainder is the second in the cycle, 4.

Example 7. Remainder when $17\times 23\times 31$ is divided by 9? Remainders $8,5,4$: $8\times 5=40\equiv 4$, then $4\times 4=16\equiv 7$. Remainder 7.

assert pow(7, 100, 6) == 1
assert pow(2, 50, 7) == 4 and [pow(2, k, 7) for k in (1, 2, 3, 4)] == [2, 4, 1, 2]
assert (17 * 23 * 31) % 9 == 7

Remainder with negative form

Remainder when $10^{25}$ is divided by 11? $10\equiv -1(\mathrm{mod}11)$, so $10^{25}\equiv (-1{)}^{25}=-1\equiv 10$. Remainder 10.

assert pow(10, 25, 11) == 10

Wilson's, Fermat's and Euler's theorems (names worth knowing)

• Fermat's little theorem: for a prime $p$ and $a$ not divisible by $p$, $a^{p-1}\equiv 1(\mathrm{mod}p)$. So remainder of $3^{100}$ divided by 7 uses $3^6\equiv 1$: $100=6\cdot 16+4$, so $3^{100}\equiv 3^4=81\equiv 4$.
• Wilson's theorem: $(p-1)!\equiv -1(\mathrm{mod}p)$ for a prime $p$.

assert pow(3, 100, 7) == 4 and all(pow(a, 6, 7) == 1 for a in range(1, 7))
from math import factorial
assert all(factorial(p - 1) % p == p - 1 for p in (5, 7, 11, 13))

7. Unit digit and cyclicity

The last digit of $a^n$ depends only on the last digit of $a$ and on $n$ modulo the cycle length (4 for 2, 3, 7, 8; 2 for 4, 9; 1 for 0, 1, 5, 6).

Example 8. Unit digit of $7^{123}$? Cycle 7, 9, 3, 1 (length 4). $123\mathrm{mod}4=3$, so the third term, 3.

Example 9. Unit digit of $13^{47}\times 8^{32}$? $13^{47}$: unit cycle of 3, $47\mathrm{mod}4=3$, giving 7. $8^{32}$: $32\mathrm{mod}4=0$ means the fourth term, 6. Product $7\times 6=42$, unit digit 2.

assert pow(7, 123, 10) == 3
assert pow(13, 47, 10) == 7 and pow(8, 32, 10) == 6 and (pow(13, 47, 10) * pow(8, 32, 10)) % 10 == 2
assert [pow(2, k, 10) for k in range(1, 9)] == [2, 4, 8, 6, 2, 4, 8, 6]

8. Base conversions and digit problems

• Place value: $\overline{abc}=100a+10b+c$.
• A two-digit number and its reverse: $(10a+b)+(10b+a)=11(a+b)$ and $(10a+b)-(10b+a)=9(a-b)$. So the sum is always a multiple of 11 and the difference a multiple of 9.
• Converting to binary: repeated division by 2.

assert all((10 * a + b + 10 * b + a) % 11 == 0 for a in range(1, 10) for b in range(10))
assert all(((10 * a + b) - (10 * b + a)) % 9 == 0 for a in range(1, 10) for b in range(10))
assert bin(45) == "0b101101" and int("101101", 2) == 45

Example 10. A two-digit number equals 4 times the sum of its digits, and adding 27 to it reverses the digits. Find it. From $10a+b=4(a+b)$ we get $b=2a$. From $10a+b+27=10b+a$ we get $9(b-a)=27$, so $b-a=3$. With $b=2a$ this gives $a=3$, $b=6$: the number is 36. Check: $4\times 9=36$ and $36+27=63$.

assert [n for n in range(10, 100) if n == 4 * (n // 10 + n % 10) and n + 27 == int(str(n)[::-1])] == [36]
assert [n for n in range(10, 100) if n == 4 * (n // 10 + n % 10)] == [12, 24, 36, 48]

9. Counting and sequences of numbers

• Count of multiples of $k$ up to $N$: $\lfloor N/k\rfloor$.
• Numbers divisible by $a$ or $b$: $\lfloor N/a\rfloor +\lfloor N/b\rfloor -\lfloor N/\text{lcm}(a,b)\rfloor$ (inclusion-exclusion).
• Sum of the first $n$ natural numbers $=\frac{n(n+1)}{2}$; of odd numbers $=n^2$; of squares $=\frac{n(n+1)(2n+1)}{6}$; of cubes $={\left(\frac{n(n+1)}{2}\right)}^2$.

N = 500
assert N // 7 + N // 11 - N // 77 == len([n for n in range(1, N + 1) if n % 7 == 0 or n % 11 == 0]) == 110
n = 20
assert sum(range(1, n + 1)) == n * (n + 1) // 2
assert sum(range(1, 2 * n, 2)) == n ** 2
assert sum(k * k for k in range(1, n + 1)) == n * (n + 1) * (2 * n + 1) // 6
assert sum(k ** 3 for k in range(1, n + 1)) == (n * (n + 1) // 2) ** 2

10. Common traps

• Forgetting that 1 is not prime and 2 is the only even prime.
• HCF times LCM equals product only for two numbers.
• Remainder must be smaller than the divisor. Check this in "largest number that leaves remainders" questions.
• "Divisible by" versus "leaves remainder" after adding or subtracting a constant.
• Counting factors including 1 and the number itself (and "even factors" or "odd factors" variants).
• Cyclicity: when $n\mathrm{mod}4=0$, use the last element of the cycle, not the first.
• Negative remainders must be converted to positive ones.

11. Practice set with answers

1. Find the HCF and LCM of 36, 60 and 84.
2. The smallest number which leaves remainder 7 when divided by 12, 15 or 20.
3. How many factors does 720 have? How many of them are perfect squares?
4. Remainder when $5^{30}$ is divided by 13.
5. Unit digit of $4326^{125}\times 3^{47}$.
6. How many numbers up to 1000 are divisible by 6 or 15?
7. Number of trailing zeros in $50!$.
8. Two numbers have HCF 9 and LCM 90, and their sum is 63. Find them.

assert (reduce(gcd, [36, 60, 84]), reduce(lcm, [36, 60, 84])) == (12, 1260)
assert reduce(lcm, [12, 15, 20]) + 7 == 67
assert len(factors(720)) == 30 and len([d for d in factors(720) if int(d ** 0.5) ** 2 == d]) == 6
assert pow(5, 30, 13) == 12                                              # 5^4 = 625 = 1 (mod 13), so 5^30 = (5^4)^7 * 5^2 = 25 = 12
assert pow(4326, 125, 10) * pow(3, 47, 10) % 10 == 2                     # a power of a number ending in 6 ends in 6; 3^47 ends in 7; 6 * 7 = 42
assert len([n for n in range(1, 1001) if n % 6 == 0 or n % 15 == 0]) == 199     # 166 + 66 - 33
assert trailing_zeros(50) == 12                                          # 10 + 2
assert [(a, b) for a in range(1, 64) for b in range(a, 64) if a + b == 63 and gcd(a, b) == 9 and lcm(a, b) == 90] == [(18, 45)]

Answers: 1) HCF 12, LCM 1260; 2) 67; 3) 30 factors, 6 perfect-square factors; 4) 12; 5) 2; 6) 199; 7) 12; 8) 18 and 45 (write them as $9x$ and $9y$ with $xy=10$ and $x+y=7$).