- Practice
- About 18 min
- 5 practice questions
Fundamental Theorem of Arithmetic and modular arithmetic
Use the unique prime factorisation of a number to find HCF and LCM and answer 'can it end in…' questions, then work with congruence modulo n: remainders, sums and products modulo n, simple congruences, and clock and calendar problems.
If something looks wrong, please tell us.
By the end of this lesson you can
- State the Fundamental Theorem of Arithmetic and use prime factorisation for HCF, LCM and divisibility questions.
- Explain a ≡ b (mod n) and reduce numbers, sums, products and powers modulo n.
- Solve simple congruences and time and day problems with modulo 24 and modulo 7.
Prime numbers are the building blocks of all positive integers, the way atoms make up molecules. The first half of this lesson uses that idea. The second half meets modular arithmetic, the arithmetic of clocks and calendars, developed by Carl Friedrich Gauss, where numbers 'wrap around' after reaching a fixed value.
The Fundamental Theorem of Arithmetic
Every positive integer greater than 1 can be written as a product of primes in exactly one way, apart from the order of the factors.
However you start splitting 2520 (as 252 × 10, or 36 × 70, or 8 × 315), you always end with the same primes: 2520 = 2³ × 3² × 5 × 7. Check: 8 × 9 = 72 and 72 × 35 = 2520. In general a composite number N can be written uniquely as N = p₁^q₁ × p₂^q₂ × … × pₙ^qₙ with primes p₁ < p₂ < … and natural-number powers.
- If a prime p divides a product ab, then p divides a or p divides b.
- This is false for composite numbers: 6 divides 4 × 9 = 36, but 6 divides neither 4 nor 9.
Worked example 1: HCF and LCM from prime factors
Find the HCF and LCM of 360 and 756. Working: 360 = 2³ × 3² × 5 and 756 = 2² × 3³ × 7. HCF = product of common primes with the smaller powers = 2² × 3² = 36. LCM = every prime with the greater power = 2³ × 3³ × 5 × 7 = 216 × 35 = 7560. Check: HCF × LCM = 36 × 7560 = 272160 = 360 × 756.
Worked example 2: questions answered by uniqueness
- Can 4ⁿ end with the digit 0? 4ⁿ = 2²ⁿ. A number ending in 0 is divisible by 10 = 2 × 5, so its factorisation must contain 5. By uniqueness, 2²ⁿ has no 5, so 4ⁿ never ends in 0.
- Is 5 × 7 × 11 + 7 composite? It equals 7 × (5 × 11 + 1) = 7 × 56, so it has factors other than 1 and itself: composite.
- Find a and b if aᵇ × bᵃ = 72. 72 = 2³ × 3², which is 2³ × 3² = aᵇ × bᵃ with a = 2, b = 3. So a = 2, b = 3.
Congruence modulo n
Two integers a and b are congruent modulo n if they differ by a multiple of n: a − b = kn for some integer k. We write a ≡ b (mod n) and call n the modulus. Equivalently, a and b leave the same remainder when divided by n. For example 38 ≡ 3 (mod 7), because 38 − 3 = 35 = 7 × 5. Linking with Euclid: if n = mq + r, then n ≡ r (mod m). So working modulo m we may replace every number by its remainder 0, 1, …, m − 1.
Counting modulo 4 wraps around like a clock
- 0 4, 8, 12, … land here
- 1 5, 9, 13, … land here
- 2 6, 10, 14, … land here
- 3 7, 11, 15, … land here; the next step returns to 0
Then back to step 1: 0
Modulo operations: if a ≡ b (mod m) and c ≡ d (mod m), then a + c ≡ b + d, a − c ≡ b − d and a × c ≡ b × d (mod m). Also ac ≡ bc and a ± c ≡ b ± c (mod m) for any integer c. So you may reduce first and calculate afterwards.
Worked example 3: remainders without long division
- 23 ≡ 2 and 30 ≡ 2 (mod 7). So 23 + 30 ≡ 4 (mod 7): indeed 53 = 49 + 4. And 23 × 30 ≡ 2 × 2 = 4 (mod 7): indeed 690 = 686 + 4.
- Remainder of 3¹⁰ on division by 7: 3² = 9 ≡ 2, so 3⁴ ≡ 2² = 4, 3⁸ ≡ 4² = 16 ≡ 2, and 3¹⁰ = 3⁸ × 3² ≡ 2 × 2 = 4 (mod 7). Check: 3¹⁰ = 59049 = 7 × 8435 + 4.
Worked example 4: solving congruences
- Least positive x with 47 + x ≡ 3 (mod 6). Then 44 + x must be a multiple of 6. The next multiple of 6 after 44 is 48, so x = 4.
- Find d with 26 ≡ 2 (mod d). 26 − 2 = 24 = kd, so d divides 24. As the remainder 2 must be less than d, d = 3, 4, 6, 8, 12 or 24.
- Solve 5x ≡ 3 (mod 7). Try x = 0, 1, …, 6: 5 × 2 = 10 ≡ 3. So x ≡ 2 (mod 7): x = 2, 9, 16, 23, … A congruence has infinitely many solutions, unlike a polynomial equation.
Worked example 5: clocks and calendars
(i) A bus leaves at 9 a.m. and the journey takes 50 hours. Working modulo 24: 50 = 2 × 24 + 2, so it arrives 2 days later at 9 + 2 = 11 a.m. (ii) Today is Thursday. Number the days Sunday = 0, Monday = 1, …, Saturday = 6, so Thursday = 4. In 100 days: 100 = 14 × 7 + 2, so 4 + 100 ≡ 4 + 2 = 6 (mod 7): Saturday.
Key takeaways: prime factorisation is unique, which gives HCF (smaller powers of common primes), LCM (greater powers of all primes) and quick answers about last digits. a ≡ b (mod n) means n divides a − b. Reduce numbers to remainders before adding, multiplying or raising to powers. Use mod 24 for hours and mod 7 for days.
Check your understanding
-
1. If 2ᵃ × 3ᵇ = 1296, what is a + b?
- 6
- 8
- 10
- 7
Show answer
Answer: B. 1296 = 36 × 36 = (2² × 3²)² = 2⁴ × 3⁴. By uniqueness of prime factorisation a = 4 and b = 4, so a + b = 8.
-
2. What is the LCM of 2³ × 3 × 5² and 2² × 3³ × 5?
- 2² × 3 × 5
- 2⁵ × 3⁴ × 5³
- 2³ × 3³ × 5²
- 2³ × 3 × 5
Show answer
Answer: C. The LCM takes every prime with its greatest power: 2³ (from the first), 3³ (from the second) and 5² (from the first). So LCM = 2³ × 3³ × 5². The product 2⁵ × 3⁴ × 5³ is the product of the two numbers, not the LCM.
-
3. What is the remainder when 17 × 23 + 31 is divided by 5?
- 2
- 4
- 1
- 3
Show answer
Answer: A. Reduce modulo 5: 17 ≡ 2, 23 ≡ 3 and 31 ≡ 1. So 17 × 23 + 31 ≡ 2 × 3 + 1 = 7 ≡ 2 (mod 5). Check: 391 + 31 = 422 = 5 × 84 + 2.
-
4. Today is Wednesday. Which day of the week will it be 60 days from today?
- Saturday
- Monday
- Tuesday
- Sunday
Show answer
Answer: D. 60 = 8 × 7 + 4, so 60 ≡ 4 (mod 7). Four days after Wednesday is Thursday, Friday, Saturday, Sunday: the day is Sunday.
-
5. What is the smallest positive integer x with 3x ≡ 5 (mod 7)?
- 2
- 3
- 4
- 6
Show answer
Answer: C. Try values: 3 × 1 = 3, 3 × 2 = 6, 3 × 3 = 9 ≡ 2, 3 × 4 = 12 ≡ 5 (mod 7). So x = 4 (and also 11, 18, …).
Sign in to keep track of the lessons you finish.