Number Theory - CXC/CSEC Mathematics

1. Introduction to Number Theory

Number Theory is one of the oldest branches of pure mathematics that deals with the properties and relationships of numbers, especially integers. For your CXC/CSEC Mathematics examination, understanding number theory fundamentals is essential for problem-solving across various mathematical domains.

1.1. What is Number Theory?

Number Theory is the study of the integers and their properties. It focuses on:

Properties of whole numbers, integers, and natural numbers
Patterns and relationships between numbers
Divisibility and prime factorization
Number systems and their operations

1.2. Number Systems in the CXC/CSEC Syllabus

The CXC/CSEC Mathematics syllabus requires understanding of the following number systems:

Natural Numbers (ℕ): 1, 2, 3, 4, ...
Whole Numbers (W): 0, 1, 2, 3, ...
Integers (ℤ): ..., -3, -2, -1, 0, 1, 2, 3, ...
Rational Numbers (ℚ): Numbers that can be expressed as a fraction of integers
Irrational Numbers: Numbers that cannot be expressed as fractions
Real Numbers (ℝ): All rational and irrational numbers

2. Factors, Multiples, and Divisibility

2.1. Factors and Multiples

Factors are numbers that divide evenly into another number with no remainder. Multiples are the products of a number and any integer.

Example: The factors of 12 are 1, 2, 3, 4, 6, and 12.

Example: The multiples of 3 are 3, 6, 9, 12, 15, ...

2.2. Divisibility Rules

Divisibility rules help us quickly determine if a number is divisible by another without actually performing division:

Divisible by 2: Last digit is even (0, 2, 4, 6, or 8)
Divisible by 3: Sum of all digits is divisible by 3
Divisible by 4: Last two digits form a number divisible by 4
Divisible by 5: Last digit is 0 or 5
Divisible by 6: Divisible by both 2 and 3
Divisible by 8: Last three digits form a number divisible by 8
Divisible by 9: Sum of all digits is divisible by 9
Divisible by 10: Last digit is 0

Example: Is 342 divisible by 3?

Sum of digits: 3 + 4 + 2 = 9

9 is divisible by 3, so 342 is divisible by 3.

3. Prime Numbers and Composite Numbers

3.1. Prime Numbers

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

The first few prime numbers are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...

3.2. Composite Numbers

A composite number is a natural number greater than 1 that has positive divisors other than 1 and itself.

The first few composite numbers are: 4, 6, 8, 9, 10, 12, 14, 15, 16, ...

3.3. Sieve of Eratosthenes

The Sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to a specified limit:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

The only even prime number is 2. All other even numbers are composite as they are divisible by 2.

4. Prime Factorization

4.1. Prime Factorization Definition

Prime factorization is the process of expressing a composite number as a product of prime numbers.

Example: The prime factorization of 60

60 = 2 × 2 × 3 × 5 = 2² × 3 × 5

4.2. Finding Prime Factorization

To find the prime factorization of a number:

Start by dividing the number by the smallest prime number (typically 2).
If it divides evenly, write down the prime factor and continue with the quotient.
If it doesn't divide evenly, try the next prime number.
Repeat until you reach a prime number as the quotient.

Example: Find the prime factorization of 84

84 ÷ 2 = 42

42 ÷ 2 = 21

21 ÷ 3 = 7

7 is a prime number

Therefore, 84 = 2 × 2 × 3 × 7 = 2² × 3 × 7

4.3. Using Prime Factorization

Prime factorization is useful for finding:

Greatest Common Divisor (GCD)
Least Common Multiple (LCM)
Simplifying fractions
Solving number theory problems

5. Highest Common Factor (HCF) / Greatest Common Divisor (GCD)

5.1. Definition of HCF/GCD

The Highest Common Factor (HCF), also known as Greatest Common Divisor (GCD), of two or more integers is the largest positive integer that divides each of the numbers without a remainder.

5.2. Finding HCF using Prime Factorization

To find the HCF using prime factorization:

Find the prime factorization of each number.
Identify the common prime factors.
Multiply the common prime factors, using the lowest power that appears in all factorizations.

Example: Find the HCF of 36 and 48

36 = 2² × 3²

48 = 2⁴ × 3

Common prime factors: 2² × 3 = 12

Therefore, HCF(36, 48) = 12

5.3. Finding HCF using the Euclidean Algorithm

The Euclidean Algorithm is an efficient method for finding the GCD of two numbers:

Divide the larger number by the smaller number.
If the remainder is 0, the smaller number is the GCD.
If the remainder is not 0, replace the larger number with the smaller number and the smaller number with the remainder.
Repeat steps 1-3 until the remainder is 0.

Example: Find the HCF of 48 and 18 using the Euclidean Algorithm

48 = 18 × 2 + 12

18 = 12 × 1 + 6

12 = 6 × 2 + 0

Therefore, HCF(48, 18) = 6

6. Lowest Common Multiple (LCM)

6.1. Definition of LCM

The Lowest Common Multiple (LCM) of two or more integers is the smallest positive integer that is divisible by all the given numbers without a remainder.

6.2. Finding LCM using Prime Factorization

To find the LCM using prime factorization:

Find the prime factorization of each number.
Create a product using each prime factor with its highest power from any of the factorizations.

Example: Find the LCM of 12 and 18

12 = 2² × 3¹

18 = 2¹ × 3²

Taking the highest powers: 2² × 3² = 36

Therefore, LCM(12, 18) = 36

6.3. Using the HCF to find LCM

For two numbers a and b, the following relationship holds:

LCM(a, b) × HCF(a, b) = a × b

Example: Find the LCM of 24 and 36 using their HCF

HCF(24, 36) = 12

LCM(24, 36) = (24 × 36) ÷ 12 = 864 ÷ 12 = 72

7. Applications in Number Theory

7.1. Word Problems with HCF and LCM

Common applications of HCF include:

Finding the largest possible equal groups
Finding the largest square tiles to cover a rectangular floor
Simplifying ratios and fractions

Common applications of LCM include:

Finding when repeating events coincide
Finding the smallest quantity that can be divided equally
Adding or subtracting fractions

Example: A red light flashes every 18 seconds and a green light flashes every 12 seconds. If both lights flash together at a given moment, after how many seconds will they flash together again?

We need to find the LCM of 18 and 12:

18 = 2 × 3²

12 = 2² × 3

LCM = 2² × 3² = 36

Therefore, they will flash together again after 36 seconds.

7.2. Number Puzzles

Number theory principles are frequently tested through puzzles in the CXC/CSEC Mathematics examination:

Example: The sum of the digits of a two-digit number is 9. When the digits are reversed, the new number is 9 more than the original number. Find the original number.

Let's say the original number is 10a + b, where a and b are single digits.

Given: a + b = 9

When reversed, the number becomes 10b + a

Given: 10b + a - (10a + b) = 9

Simplifying: 10b + a - 10a - b = 9

Simplifying further: 9b - 9a = 9

Dividing by 9: b - a = 1

With a + b = 9 and b - a = 1, we can solve:

a + b = 9

b - a = 1

2b = 10

b = 5, a = 4

Therefore, the original number is 45.

8. Special Number Properties

8.1. Perfect Numbers

A perfect number is a positive integer that is equal to the sum of its proper divisors (all divisors excluding the number itself).

Example: 6 is a perfect number because its proper divisors are 1, 2, and 3, and 1 + 2 + 3 = 6.

The first few perfect numbers are 6, 28, 496, and 8128.

8.2. Amicable Numbers

Two numbers are amicable if each is equal to the sum of the proper divisors of the other.

Example: 220 and 284 are amicable numbers.

The proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, and 110, and their sum is 284.

The proper divisors of 284 are 1, 2, 4, 71, and 142, and their sum is 220.

8.3. Square Numbers and Cube Numbers

Square numbers are numbers that can be expressed as the product of an integer with itself:

1, 4, 9, 16, 25, 36, 49, 64, 81, 100, ...

Cube numbers are numbers that can be expressed as the product of an integer with itself three times:

1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, ...

9. Modular Arithmetic (CXC-CSEC 2024-2025)

9.1. Introduction to Modular Arithmetic

Modular arithmetic is a system of arithmetic for integers where numbers "wrap around" after reaching a certain value—the modulus.

9.2. Congruence Modulo n

We say that a is congruent to b modulo n, written as a ≡ b (mod n), if a - b is divisible by n.

Example: 17 ≡ 5 (mod 12)

Because 17 - 5 = 12, which is divisible by 12.

9.3. Applications of Modular Arithmetic

Modular arithmetic has many practical applications:

Determining the day of the week for any date
Check digits in identification numbers
Cryptography and computer security

Example: What is the remainder when 3⁷ is divided by 5?

We need to find 3⁷ (mod 5)

3¹ ≡ 3 (mod 5)

3² = 9 ≡ 4 (mod 5)

3³ = 27 ≡ 2 (mod 5)

3⁴ = 81 ≡ 1 (mod 5)

3⁵ = 243 ≡ 3 (mod 5)

3⁶ = 729 ≡ 4 (mod 5)

3⁷ = 2187 ≡ 2 (mod 5)

Therefore, the remainder when 3⁷ is divided by 5 is 2.

10. Number Bases

10.1. Decimal System (Base 10)

Our standard number system uses base 10, with digits 0-9:

123₁₀ = 1 × 10² + 2 × 10¹ + 3 × 10⁰ = 100 + 20 + 3 = 123

10.2. Binary System (Base 2)

The binary system uses base 2, with digits 0 and 1:

110₂ = 1 × 2² + 1 × 2¹ + 0 × 2⁰ = 4 + 2 + 0 = 6₁₀

10.3. Converting Between Number Bases

To convert from decimal to another base:

Divide the decimal number by the target base.
Record the remainder.
Divide the quotient by the target base.
Repeat until the quotient is 0.
Read the remainders from bottom to top.

Example: Convert 25₁₀ to binary

25 ÷ 2 = 12 remainder 1

12 ÷ 2 = 6 remainder 0

6 ÷ 2 = 3 remainder 0

3 ÷ 2 = 1 remainder 1

1 ÷ 2 = 0 remainder 1

Reading the remainders from bottom to top: 11001₂

To convert from another base to decimal:

Multiply each digit by its place value.
Add all the products.

Example: Convert 101101₂ to decimal

1 × 2⁵ + 0 × 2⁴ + 1 × 2³ + 1 × 2² + 0 × 2¹ + 1 × 2⁰

32 + 0 + 8 + 4 + 0 + 1 = 45₁₀

11. Number Patterns and Sequences

11.1. Arithmetic Sequences

An arithmetic sequence is a sequence where the difference between consecutive terms is constant.

For an arithmetic sequence with first term a and common difference d:

n^th term: a_n = a + (n - 1)d

Sum of first n terms: S_n = n/2[2a + (n - 1)d] = n/2(a + a_n)

Example: Find the 15^th term and the sum of the first 15 terms of the arithmetic sequence 3, 9, 15, 21, ...

First term a = 3

Common difference d = 9 - 3 = 6

15^th term: a₁₅ = 3 + (15 - 1)6 = 3 + 84 = 87

Sum of first 15 terms: S₁₅ = 15/2(3 + 87) = 15/2 × 90 = 675

11.2. Geometric Sequences

A geometric sequence is a sequence where the ratio between consecutive terms is constant.

For a geometric sequence with first term a and common ratio r:

n^th term: a_n = ar^n-1

Sum of first n terms: S_n = a(1 - rⁿ)/(1 - r) (for r ≠ 1)

Example: Find the 8^th term and the sum of the first 8 terms of the geometric sequence 5, 10, 20, 40, ...

First term a = 5

Common ratio r = 10 ÷ 5 = 2

8^th term: a₈ = 5 × 2^8-1 = 5 × 2⁷ = 5 × 128 = 640

Sum of first 8 terms: S₈ = 5(1 - 2⁸)/(1 - 2) = 5(1 - 256)/(-1) = 5 × 255 = 1275

11.3. Fibonacci Sequence

The Fibonacci sequence is a famous sequence where each number is the sum of the two preceding ones:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

Formula: F_n = F_n-1 + F_n-2

Initial values: F₀ = 0, F₁ = 1

The ratio of consecutive Fibonacci numbers approaches the golden ratio (approximately 1.618) as the sequence progresses.

12. Linear Diophantine Equations

12.1. Definition

A linear Diophantine equation is an equation of the form ax + by = c, where a, b, and c are integers, and we seek integer solutions for x and y.

12.2. Existence of Solutions

A linear Diophantine equation ax + by = c has integer solutions if and only if c is divisible by the GCD of a and b.

Proof sketch:

Let d = gcd(a, b)

Then a = da' and b = db' for some integers a' and b'

If ax + by = c has integer solutions, then d must divide c

12.3. Finding Solutions

To find solutions to ax + by = c:

Find gcd(a, b) and check if it divides c
Find one particular solution (x₀, y₀)
Generate all solutions using the formula:

x = x₀ + (b/d)t

y = y₀ - (a/d)t

where t is any integer and d = gcd(a, b)

Example: Find all integer solutions to 3x + 5y = 11

First, check if gcd(3, 5) divides 11

gcd(3, 5) = 1, which divides 11

Finding a particular solution using the Extended Euclidean Algorithm:

We can find that x₀ = 2 and y₀ = 1 is a solution because 3(2) + 5(1) = 11

Therefore, all solutions are given by:
x = 2 + 5t
y = 1 - 3t
where t is any integer

13. Advanced Number Theory Topics for CXC

13.1. Mathematical Induction

Mathematical induction is a method of proof used to establish that a statement is true for all natural numbers:

Base case: Prove the statement is true for the first value (usually n = 1)
Inductive step: Assume the statement is true for n = k, and prove it for n = k + 1

Example: Prove that 1 + 2 + 3 + ... + n = n(n+1)/2 for all positive integers n

Base case: For n = 1, we have 1 = 1(1+1)/2 = 1, which is true

Inductive step: Assume that 1 + 2 + ... + k = k(k+1)/2 is true

We need to prove that 1 + 2 + ... + k + (k+1) = (k+1)(k+2)/2

1 + 2 + ... + k + (k+1) = k(k+1)/2 + (k+1) = (k+1)(k/2 + 1) = (k+1)(k+2)/2

Therefore, the statement is true for all positive integers n

13.2. Indices (Exponents) and Their Properties

Important properties of indices that you need to know:

a^m × aⁿ = a^m+n
a^m ÷ aⁿ = a^m-n
(a^m)ⁿ = a^m×n
(ab)ⁿ = aⁿbⁿ
a⁰ = 1 (for a ≠ 0)
a^-n = 1/aⁿ
a^1/n = ⁿ√a
a^m/n = (ⁿ√a)^m

14. Number Theory in the CXC/CSEC Examination

14.1. Common Question Types

In the CXC/CSEC Mathematics examination, number theory questions often involve:

Finding HCF and LCM
Working with prime numbers and factorization
Solving number puzzles
Converting between number bases
Working with arithmetic and geometric sequences
Applying modular arithmetic
Using divisibility rules

14.2. Examination Strategies

When tackling number theory problems in the CXC/CSEC examination:

Always show your working clearly
Use prime factorization when dealing with HCF and LCM
Check your answers using divisibility rules
For sequence problems, identify the pattern and the common difference or ratio
Draw diagrams when helpful
Double-check your calculations

15. Glossary of Number Theory Terms

Arithmetic Sequence: A sequence where the difference between consecutive terms is constant.
Composite Number: A positive integer greater than 1 that has positive divisors other than 1 and itself.
Congruence Modulo n: A relationship between numbers where their difference is divisible by n, written as a ≡ b (mod n).
Diophantine Equation: An equation where only integer solutions are sought.
Divisibility: An integer a is divisible by a non-zero integer b if there exists an integer c such that a = bc.
Factor: An integer that divides another integer exactly (without a remainder).
Fibonacci Sequence: A sequence where each number is the sum of the two preceding ones, starting from 0 and 1.
Geometric Sequence: A sequence where the ratio between consecutive terms is constant.
Greatest Common Divisor (GCD): The largest positive integer that divides two or more integers without a remainder.
Highest Common Factor (HCF): Another term for the Greatest Common Divisor.
Integer: A whole number (positive, negative, or zero).
Irrational Number: A real number that cannot be expressed as a ratio of integers.
Least Common Multiple (LCM): The smallest positive integer that is divisible by two or more integers without a remainder.
Modular Arithmetic: A system of arithmetic for integers where numbers "wrap around" after reaching a certain value (the modulus).
Multiple: The product of a given number and any integer.
Natural Number: A positive integer (1, 2, 3, ...).
Perfect Number: A positive integer that is equal to the sum of its proper divisors.
Prime Factorization: The process of expressing a composite number as a product of prime numbers.
Prime Number: A natural number greater than 1 that is not divisible by any natural number other than 1 and itself.
Rational Number: A number that can be expressed as a ratio of two integers, with the denominator not equal to zero.
Real Number: Any rational or irrational number.
Relatively Prime: Two integers are relatively prime if their greatest common divisor is 1.
Sieve of Eratosthenes: An ancient algorithm for finding all prime numbers up to a specified limit.
Whole Number: A non-negative integer (0, 1, 2, 3, ...).

16. Self-Assessment Questions

Section A: Multiple Choice

1. What is the HCF of 36, 48, and 60?

4
6
12
24

2. What is the LCM of 12, 18, and 24?

36
72
144
216

3. Which of the following numbers is NOT a prime number?

23
29
51
83

4. What is the prime factorization of 420?

2² × 3 × 5 × 7
2² × 3² × 5 × 7
2² × 3 × 5² × 7
2³ × 3 × 5 × 7

5. If 15 ≡ x (mod 4), then x =

3
4
11
19

Section B: Short Answer Questions

6. Find the HCF and LCM of 54 and 72 using prime factorization.

7. Convert 173₁₀ to binary.

8. Convert 10110₂ to decimal.

9. Find the 10th term of the arithmetic sequence: 5, 11, 17, 23, ...

10. Find the sum of the first 8 terms of the geometric sequence: 3, 6, 12, 24, ...

Section C: Problem-Solving Questions

11. Three bells ring at intervals of 12 seconds, 18 seconds, and 30 seconds, respectively. If they all ring together at 9:00 AM, at what time will they next ring together?

12. A rectangular floor measures 240 cm by 180 cm. Find the largest square tiles that can be used to cover the floor without cutting any tiles, and determine how many such tiles are needed.

13. Prove that for any three consecutive integers, one of them is always divisible by 3.

14. Solve the linear Diophantine equation 15x + 26y = 13 for integer solutions.

15. What is the remainder when 7⁹⁹ is divided by 10?

Answers:

Section A:

1. B (The HCF of 36, 48, and 60 is 12)

2. B (The LCM of 12, 18, and 24 is 72)

3. C (51 = 3 × 17 is composite)

4. A (420 = 2² × 3 × 5 × 7)

5. A (15 divided by 4 gives a remainder of 3)

Section B:

6. 54 = 2 × 3³, 72 = 2³ × 3²
HCF = 2 × 3² = 18
LCM = 2³ × 3³ = 216

7. 173₁₀ = 10101101₂
173 ÷ 2 = 86 remainder 1
86 ÷ 2 = 43 remainder 0
43 ÷ 2 = 21 remainder 1
21 ÷ 2 = 10 remainder 1
10 ÷ 2 = 5 remainder 0
5 ÷ 2 = 2 remainder 1
2 ÷ 2 = 1 remainder 0
1 ÷ 2 = 0 remainder 1

8. 10110₂ = 1×2⁴ + 0×2³ + 1×2² + 1×2¹ + 0×2⁰ = 16 + 0 + 4 + 2 + 0 = 22₁₀

9. First term a = 5, common difference d = 6
10th term = a + (10-1)d = 5 + 9×6 = 5 + 54 = 59

10. First term a = 3, common ratio r = 2
Sum of first 8 terms = a(1-r⁸)/(1-r) = 3(1-2⁸)/(1-2) = 3(1-256)/(-1) = 3×255 = 765

Section C:

11. We need to find the LCM of 12, 18, and 30:
12 = 2² × 3
18 = 2 × 3²
30 = 2 × 3 × 5
LCM = 2² × 3² × 5 = 180 seconds
180 seconds = 3 minutes
They will next ring together at 9:03 AM

12. The largest square tile size is given by the HCF of 240 and 180:
240 = 2⁴ × 3 × 5
180 = 2² × 3² × 5
HCF = 2² × 3 × 5 = 60 cm
Number of tiles = (240 × 180) ÷ (60 × 60) = 43200 ÷ 3600 = 12 tiles

13. Let the three consecutive integers be n, n+1, and n+2.
Case 1: If n is divisible by 3, then n is the required integer.
Case 2: If n leaves remainder 1 when divided by 3, then n = 3k + 1 for some integer k.
Then n+2 = 3k + 3 = 3(k+1), which is divisible by 3.
Case 3: If n leaves remainder 2 when divided by 3, then n = 3k + 2 for some integer k.
Then n+1 = 3k + 3 = 3(k+1), which is divisible by 3.
Therefore, in all cases, one of the three consecutive integers is divisible by 3.

14. First, we check if gcd(15, 26) divides 13:
gcd(15, 26) = 1, which divides 13.
Using the Extended Euclidean Algorithm or trial and error, we find that x = 5, y = -4 is a particular solution.
All solutions are given by:
x = 5 + 26t
y = -4 - 15t
where t is any integer.

15. We need to find the pattern of remainders when powers of 7 are divided by 10:
7¹ ≡ 7 (mod 10)
7² = 49 ≡ 9 (mod 10)
7³ = 343 ≡ 3 (mod 10)
7⁴ = 2401 ≡ 1 (mod 10)
The pattern repeats with period 4.
99 ÷ 4 = 24 remainder 3
So 7⁹⁹ ≡ 7³ ≡ 3 (mod 10)
The remainder is 3.