Number System: Divisibility, HCF, LCM, Unit Digits and Remainders

• Natural numbers: 1, 2, 3, ... Whole numbers: 0, 1, 2, ... Integers: ..., -2, -1, 0, 1, 2, ...

• Rational numbers: can be written as p/q with q not zero. Irrational numbers: cannot (the square root of 2, pi).

• Prime numbers: have exactly two factors, 1 and themselves. 2 is the only even prime. 1 is neither prime nor composite.

• Composite numbers: have more than two factors.

• Co-prime numbers: two numbers whose HCF is 1 (they need not be prime themselves, for example 8 and 15).

• Twin primes: primes differing by 2, such as (3, 5), (11, 13), (17, 19).

• Perfect numbers: equal to the sum of their proper factors, such as 6, 28, 496, 8128.

• Even and odd: even + even = even, odd + odd = even, even + odd = odd, odd x odd = odd, any even factor makes the product even.

• The 25 primes below 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.

• Primality test: to check whether n is prime, divide it by every prime up to the square root of n. If none divides it, it is prime.

For a composite divisor, test its co-prime factors (for example 36 = 4 x 9, 72 = 8 x 9). Testing 2 and 6 together does not prove divisibility by 12, because 2 and 6 are not co-prime.

• If N = p^a x q^b x r^c (prime factorisation), then:

  • Number of factors = (a + 1)(b + 1)(c + 1)

  • Sum of factors = [(p^(a+1) - 1)/(p - 1)] x [(q^(b+1) - 1)/(q - 1)] x ...

  • A number is a perfect square only if every power in its factorisation is even.

• Example: 36 = 2 squared x 3 squared has (2+1)(2+1) = 9 factors, and the sum of factors is (7) x (13) = 91.

• HCF (GCD): greatest number that divides all the given numbers. LCM: smallest number divisible by all of them.

• Methods: prime factorisation (HCF takes the lowest powers of common primes; LCM takes the highest powers of all primes) or the division method.

• For two numbers: HCF x LCM = product of the two numbers. This does not work for three numbers.

• For fractions: HCF = HCF of numerators / LCM of denominators; LCM = LCM of numerators / HCF of denominators.

• LCM of co-prime numbers is their product; HCF of two consecutive integers is 1; HCF of two consecutive even numbers is 2.

• Largest number that divides a, b, c leaving remainders r1, r2, r3: HCF of (a - r1), (b - r2), (c - r3). If the same remainder r remains in all, subtract r from each number.

• Smallest number that leaves remainder r when divided by a, b, c: LCM(a, b, c) + r.

• Smallest number exactly divisible by a, b, c: LCM(a, b, c).

• Events repeating together (bells ringing, lights flashing, runners meeting): use the LCM of the intervals.

• Largest tile or equal-length piece that fits several lengths exactly: use the HCF.

The last digit of powers repeats in a cycle. Divide the power by the cycle length and use the remainder; if the remainder is 0, use the last number in the cycle.

• Product rule: remainder of (a x b) divided by n equals remainder of (r_a x r_b) divided by n, where r_a and r_b are the remainders of a and b. Sums and differences work the same way.

• Casting out nines: the remainder of a number divided by 9 equals the remainder of its digit sum divided by 9. The same works for 3.

• Trailing zeros in n factorial: count the factors of 5, that is, floor(n/5) + floor(n/25) + floor(n/125) + ... For 100! this is 20 + 4 = 24 zeros.

• Two-digit numbers: a number with digits a and b equals 10a + b. The number plus its reverse is 11(a + b); the difference between the number and its reverse is 9(a - b).

Example 1. Find the HCF and LCM of 24, 36 and 60.

• 24 = 2^3 x 3, 36 = 2^2 x 3^2, 60 = 2^2 x 3 x 5.

• HCF = 2^2 x 3 = 12. LCM = 2^3 x 3^2 x 5 = 360.

Example 2. The largest number that divides 245 and 1029 leaving remainder 5 in each case.

• Subtract the remainder: 240 and 1024. HCF(240, 1024) = 16.

• The divisor must exceed the remainder 5, and 16 does, so the answer is 16.

Example 3. The smallest number that leaves remainder 5 when divided by 12, 15 and 20.

• LCM(12, 15, 20) = 60. The number is 60 + 5 = 65.

Example 4. Three bells ring every 12, 15 and 18 minutes and ring together at 9:00 am. When do they next ring together?

• LCM(12, 15, 18) = 180 minutes = 3 hours. They next ring together at 12:00 noon.

Example 5. Two numbers have HCF 6 and LCM 180. One of them is 30. Find the other.

• Other number = (6 x 180)/30 = 36.

Example 6. Find the unit digit of 7^123.

• The cycle for 7 is 7, 9, 3, 1 (length 4). 123 divided by 4 leaves remainder 3, so the unit digit is the third entry, 3.

Example 7. Is 2431 divisible by 11?

• Digits at odd places (1st, 3rd) are 2 and 3, giving 5. Digits at even places are 4 and 1, giving 5.

• The difference is 0, so yes, 2431 = 11 x 221.

Example 8. Find the remainder when 7^100 is divided by 6.

• 7 leaves remainder 1 when divided by 6, so 7^100 leaves remainder 1^100 = 1.

• Use LCM when something repeats together; use HCF when you cut or pack equally.

• Digit-sum checks (divisibility by 3 and 9) quickly test the answer to any multiplication or addition.

• Reduce the power first in unit-digit and remainder problems; never compute the full number.

• Reduce the base first: replace a large number by its remainder (or by -1 when it is one less than the divisor) before raising it to a power.

• Using HCF x LCM = product for three numbers.

• Forgetting to add (not subtract) the remainder when finding the smallest number leaving remainder r.

• Treating 1 as a prime number.

• Testing 12 with the factors 2 and 6, or 24 with 4 and 6, which are not co-prime; use 3 and 4 (or 3 and 8) instead.