Computation and Number Theory

What you'll learn

This topic covers fundamental properties of integers including divisibility rules, prime and composite numbers, greatest common divisor (GCD), least common multiple (LCM), and basic modular arithmetic. You'll learn systematic methods for factorization, computing GCD and LCM, and solving problems involving remainders. These techniques form the foundation for algebraic manipulation and problem-solving across Additional Mathematics.

Key terms and definitions

Prime number — A positive integer greater than 1 that has exactly two distinct positive divisors: 1 and itself (e.g., 2, 3, 5, 7, 11).

Composite number — A positive integer greater than 1 that has more than two positive divisors (e.g., 4, 6, 8, 9, 10).

Greatest Common Divisor (GCD) — The largest positive integer that divides two or more integers without remainder; also called highest common factor (HCF).

Least Common Multiple (LCM) — The smallest positive integer that is divisible by two or more given integers.

Modular arithmetic — A system of arithmetic for integers where numbers "wrap around" upon reaching a certain value called the modulus; expressed as a ≡ b (mod n).

Euclidean algorithm — A systematic procedure for finding the GCD of two integers by repeatedly applying division with remainder.

Prime factorization — The expression of a positive integer as a product of prime numbers in the form p₁^a₁ × p₂^a₂ × ... × pₙ^aₙ.

Divisibility — An integer a is divisible by an integer b if there exists an integer k such that a = bk, written as b|a.

Core concepts

Divisibility rules and tests

Understanding divisibility rules allows quick determination of factors without long division. These rules are essential for simplification and factorization.

Divisibility by 2: A number is divisible by 2 if its last digit is even (0, 2, 4, 6, or 8).

Divisibility by 3: A number is divisible by 3 if the sum of its digits is divisible by 3.

• Example: 1,236 → 1 + 2 + 3 + 6 = 12, and 12 ÷ 3 = 4, so 1,236 is divisible by 3.

Divisibility by 4: A number is divisible by 4 if the number formed by its last two digits is divisible by 4.

• Example: 3,728 → 28 ÷ 4 = 7, so 3,728 is divisible by 4.

Divisibility by 5: A number is divisible by 5 if its last digit is 0 or 5.

Divisibility by 6: A number is divisible by 6 if it is divisible by both 2 and 3.

Divisibility by 9: A number is divisible by 9 if the sum of its digits is divisible by 9.

Divisibility by 11: A number is divisible by 11 if the difference between the sum of digits in odd positions and the sum of digits in even positions is divisible by 11 (including 0).

• Example: 2,728 → (2 + 2) - (7 + 8) = 4 - 15 = -11, which is divisible by 11.

Prime factorization and factor trees

Every composite number can be expressed uniquely as a product of prime factors. This fundamental theorem of arithmetic is crucial for computing GCD and LCM.

Method: Factor tree

1. Start with the given number
2. Express it as a product of two factors
3. Continue factoring each composite factor until only primes remain
4. Write the result in exponential form

Example: Find the prime factorization of 360.

• 360 = 36 × 10
• 36 = 6 × 6 = 2 × 3 × 2 × 3
• 10 = 2 × 5
• Therefore: 360 = 2³ × 3² × 5

Method: Division by primes

1. Divide by the smallest prime (2) repeatedly until no longer divisible
2. Move to the next prime (3, 5, 7, ...) and repeat
3. Continue until the quotient is 1

This method is particularly efficient for larger numbers and ensures no prime factors are missed.

Greatest Common Divisor (GCD) and Least Common Multiple (LCM)

Computing GCD using prime factorization:

1. Express each number as a product of prime factors
2. Identify common prime factors
3. For each common prime, take the lowest power
4. Multiply these together

Example: Find GCD(84, 126)

• 84 = 2² × 3 × 7
• 126 = 2 × 3² × 7
• Common factors: 2¹ × 3¹ × 7¹ = 42
• GCD(84, 126) = 42

Computing LCM using prime factorization:

1. Express each number as a product of prime factors
2. Identify all prime factors that appear in either number
3. For each prime, take the highest power
4. Multiply these together

Example: Find LCM(84, 126)

• 84 = 2² × 3 × 7
• 126 = 2 × 3² × 7
• All factors with highest powers: 2² × 3² × 7 = 252
• LCM(84, 126) = 252

Relationship between GCD and LCM:

For any two positive integers a and b: GCD(a, b) × LCM(a, b) = a × b

This relationship provides a quick check for calculations and an alternative method when one value is known.

The Euclidean algorithm

The Euclidean algorithm finds the GCD without requiring prime factorization, making it efficient for large numbers.

Procedure:

1. Divide the larger number by the smaller number
2. Replace the larger number with the smaller number
3. Replace the smaller number with the remainder from step 1
4. Repeat until the remainder is 0
5. The last non-zero remainder is the GCD

Example: Find GCD(546, 234)

• 546 = 234 × 2 + 78
• 234 = 78 × 3 + 0
• GCD(546, 234) = 78

For three or more numbers, apply the algorithm repeatedly: GCD(a, b, c) = GCD(GCD(a, b), c)

Modular arithmetic and congruence

Congruence notation: a ≡ b (mod n) means a and b leave the same remainder when divided by n, or equivalently, n divides (a - b).

Properties of congruence:

• If a ≡ b (mod n) and c ≡ d (mod n), then:
  • a + c ≡ b + d (mod n)
  • a - c ≡ b - d (mod n)
  • a × c ≡ b × d (mod n)

Computing remainders:

To find the remainder when a large number is divided by n:

1. Break the calculation into manageable parts
2. Apply modular arithmetic properties
3. Simplify at each step

Example: Find the remainder when 5⁸ is divided by 7.

• 5¹ ≡ 5 (mod 7)
• 5² ≡ 25 ≡ 4 (mod 7)
• 5⁴ ≡ (5²)² ≡ 4² ≡ 16 ≡ 2 (mod 7)
• 5⁸ ≡ (5⁴)² ≡ 2² ≡ 4 (mod 7)
• Remainder is 4

Applications in problem-solving

Scheduling and cycles: When events repeat at different intervals, LCM determines when they coincide.

Example: At a port in Kingston, cargo ships from Miami arrive every 12 days and ships from Santo Domingo arrive every 18 days. If both arrive today, when will they next arrive on the same day?

• LCM(12, 18) = 36 days

Distribution problems: When items must be divided equally into groups, GCD determines the maximum group size.

Example: A cocoa farmer has 168 kg of cocoa beans and 252 kg of coffee beans to pack into identical boxes with no remainder. What is the maximum weight each box can contain?

• GCD(168, 252) = 84 kg

Remainder problems: Using modular arithmetic to solve problems involving cyclic patterns or division remainders.

Worked examples

Example 1: Prime factorization and GCD/LCM (6 marks)

Question: A telecommunications company is installing network towers. Tower A broadcasts a signal every 72 hours and Tower B broadcasts every 108 hours.

(a) Express 72 and 108 as products of prime factors. [2 marks] (b) Find the GCD of 72 and 108. [2 marks] (c) If both towers broadcast simultaneously today, after how many hours will they next broadcast simultaneously? [2 marks]

Solution:

(a) 72:

• 72 = 8 × 9 = 2³ × 3²

108:

• 108 = 4 × 27 = 2² × 3³

[1 mark for each correct factorization]

(b) Common prime factors with lowest powers:

• GCD = 2² × 3² = 4 × 9 = 36

[2 marks for correct GCD with working]

(c) They broadcast simultaneously at intervals equal to their LCM.

• LCM = 2³ × 3³ = 8 × 27 = 216 hours

Alternatively, using GCD × LCM = a × b:

• 36 × LCM = 72 × 108
• LCM = 7776 ÷ 36 = 216 hours

[2 marks: 1 for identifying LCM needed, 1 for correct answer]

Example 2: Modular arithmetic (5 marks)

Question:

(a) Prove that 7 divides (n³ - n) for all positive integers n. [3 marks] (b) Find the remainder when 13¹⁵ is divided by 11. [2 marks]

Solution:

(a) n³ - n = n(n² - 1) = n(n - 1)(n + 1)

This is the product of three consecutive integers.

Among any three consecutive integers:

• At least one is divisible by 2
• Exactly one is divisible by 3
• Therefore, the product is divisible by 6

For divisibility by 7, check remainders when n is divided by 7:

• If n ≡ 0 (mod 7), then n³ - n ≡ 0 (mod 7) ✓
• If n ≡ 1 (mod 7), then n³ - n ≡ 1 - 1 ≡ 0 (mod 7) ✓
• If n ≡ 2 (mod 7), then n³ - n ≡ 8 - 2 ≡ 6 (mod 7)... need different approach

Better: n³ - n = n(n - 1)(n + 1) contains three consecutive integers. In any set of 7 consecutive integers, at least one is divisible by 7. Since we cycle through all remainders, 7 | n³ - n for all n.

[3 marks: 1 for factorization, 2 for complete proof]

(b) 13 ≡ 2 (mod 11)

• 13¹⁵ ≡ 2¹⁵ (mod 11)
• 2⁴ ≡ 16 ≡ 5 (mod 11)
• 2⁸ ≡ 5² ≡ 25 ≡ 3 (mod 11)
• 2¹⁵ = 2⁸ × 2⁴ × 2³ ≡ 3 × 5 × 8 ≡ 120 ≡ 10 (mod 11)

Remainder = 10

[2 marks: 1 for method, 1 for correct answer]

Example 3: Euclidean algorithm (4 marks)

Question: Use the Euclidean algorithm to find the GCD of 1,326 and 882. [4 marks]

Solution:

Step 1: 1,326 = 882 × 1 + 444 [1 mark]

Step 2: 882 = 444 × 1 + 438 [1 mark]

Step 3: 444 = 438 × 1 + 6 [1 mark]

Step 4: 438 = 6 × 73 + 0

The last non-zero remainder is 6.

Therefore, GCD(1,326, 882) = 6 [1 mark]

Common mistakes and how to avoid them

Confusing GCD and LCM: Remember that GCD finds the largest common divisor (always less than or equal to the smaller number), while LCM finds the smallest common multiple (always greater than or equal to the larger number). Use context: "maximum group size" suggests GCD, "next simultaneous occurrence" suggests LCM.

Incomplete prime factorization: Always continue factoring until only prime numbers remain. Check: 6 is NOT prime (6 = 2 × 3), neither is 9 (9 = 3²). The only even prime is 2; don't forget to include it.

Taking wrong powers in GCD/LCM: For GCD, take the minimum power of each common prime factor. For LCM, take the maximum power of each prime that appears in any number. A systematic table helps prevent errors.

Arithmetic errors in modular arithmetic: When computing with large exponents, break calculations into steps and reduce modulo n at each stage to keep numbers manageable. Don't wait until the end to apply the modulus.

Forgetting to verify divisibility proofs: When proving divisibility, check edge cases (like n = 1, n = 2) and ensure your logic covers all possible remainders. A proof must work for ALL integers in the specified range.

Misapplying the Euclidean algorithm: Always divide the larger number by the smaller one, and continue until the remainder is exactly zero. The GCD is the last non-zero remainder, not the final quotient.

Exam technique for Computation and Number Theory

Show systematic working: Even for questions worth 1-2 marks, examiners award method marks. Write down factor trees, division steps, or the stages of the Euclidean algorithm clearly. Partial credit is available if your method is sound.

Identify command words: "Express as a product of prime factors" requires full factorization in exponential form (e.g., 2³ × 3²), not just listing factors. "Find" or "Calculate" requires a numerical answer. "Prove" or "Show that" requires logical reasoning with complete justification.

Use relationships strategically: If you've found GCD(a,b), use the formula GCD × LCM = a × b to find LCM quickly, saving time and reducing calculation errors. Examiners accept this shortcut.

Check reasonableness: Your GCD cannot exceed the smaller of two numbers. Your LCM cannot be less than the larger of two numbers. A quick reasonableness check catches calculation errors before you submit.

Quick revision summary

Number theory involves divisibility, prime factorization, GCD, LCM, and modular arithmetic. Use divisibility tests for quick checks. Express numbers as products of primes using factor trees or systematic division. Find GCD by taking minimum powers of common primes or using the Euclidean algorithm. Find LCM by taking maximum powers of all primes present. Remember: GCD × LCM = a × b for any two numbers. Apply modular arithmetic by reducing remainders at each calculation step. In problems, GCD relates to maximum equal distribution, LCM to simultaneous cycles. Always show clear working and verify answers for reasonableness.