00-08 — Basic Number Theory
Phase: 0 — Arithmetic & Number Foundations Subject: 00-08 Prerequisites: 00-01 — Whole Number Arithmetic, 00-02 — Fractions, 00-03 — Decimals, 00-04 — Percentages, 00-05 — Integers and Directed Numbers, 00-06 — Powers and Roots, 00-07 — Ratios, Rates, and Proportions Next subject: 01-01 — Algebraic Expressions
Learning Objectives
By the end of this subject, you will be able to:
- Apply divisibility rules for 2, 3, 4, 5, 6, 8, 9, 10, and 11 to quickly test whether one number divides another
- Perform modular arithmetic (clock arithmetic) and find remainders efficiently
- Use the Euclidean algorithm to compute the GCD of any two integers
- Compute LCM from GCD using the relationship LCM(a,b) × GCD(a,b) = |a × b|
- Test small numbers for primality using trial division up to √n and understand why this works
Core Content
1. What Is Number Theory?
Number theory is the study of the integers — their properties, relationships, and patterns. It's one of the oldest branches of mathematics, dating back to the ancient Greeks.
⚠️ THIS IS CRITICAL — Number theory is the foundation of modern cryptography (RSA encryption secures your online banking and messaging). Modular arithmetic, divisibility, and primality testing are essential building blocks for computer science, coding theory, and much of advanced mathematics.
In this subject, we build on concepts from Subject 00-01 (factors, multiples, primes, GCF, LCM) and extend them into more powerful tools.
2. Divisibility — Formal Definition
We say that an integer a divides an integer b (written a | b) if there exists an integer k such that:
b = a × k
In other words, b ÷ a gives an integer with NO remainder.
Examples: - 3 | 12 because 12 = 3 × 4 ✓ - 5 | 35 because 35 = 5 × 7 ✓ - 6 ∤ 20 because 20 ÷ 6 = 3 remainder 2 (∤ means "does not divide") - 1 divides EVERY integer (since n = 1 × n) - Every non-zero integer divides 0 (since 0 = a × 0)
Key terminology: - a is a divisor (or factor) of b - b is a multiple of a
3. Divisibility Rules
Divisibility rules let you test whether one number divides another WITHOUT doing the full division. These are computational shortcuts.
Rule for 2: A number is divisible by 2 if its last digit is even (0, 2, 4, 6, 8).
Example: 3,746 ends in 6 (even) → divisible by 2 ✓ Example: 8,953 ends in 3 (odd) → not divisible by 2 ✗
Why it works: Every number can be written as 10×q + r where r is the last digit. Since 10 is divisible by 2, 10×q is divisible by 2. So the whole number is divisible by 2 exactly when the last digit r is.
Rule for 3: A number is divisible by 3 if the sum of its digits is divisible by 3.
Example: 8,472 → 8+4+7+2 = 21 → 21 is divisible by 3 → 8,472 is divisible by 3 ✓ Check: 8,472 ÷ 3 = 2,824 (no remainder)
Example: 5,281 → 5+2+8+1 = 16 → 16 is NOT divisible by 3 → 5,281 is not divisible by 3
Why it works (for 3-digit numbers): Any 3-digit number abc = 100a + 10b + c = 99a + a + 9b + b + c = (99a + 9b) + (a + b + c) = 9(11a + b) + (a + b + c)
Since 9(11a + b) is divisible by 3 (9 is a multiple of 3), the whole number is divisible by 3 exactly when (a + b + c) is divisible by 3.
For larger numbers, continue summing digits until you get a single digit or a recognizable multiple of 3.
Rule for 4: A number is divisible by 4 if its last two digits form a number divisible by 4.
Example: 7,324 → last two digits: 24 → 24 ÷ 4 = 6 → divisible by 4 ✓ Example: 9,518 → last two digits: 18 → 18 ÷ 4 = 4.5 → not divisible by 4 ✗
Why it works: 100 = 4 × 25, so any multiple of 100 is divisible by 4. Only the last two digits matter.
Rule for 5: A number is divisible by 5 if its last digit is 0 or 5.
Example: 1,275 ends in 5 → divisible by 5 ✓ Example: 8,290 ends in 0 → divisible by 5 ✓
Why it works: 10 and all multiples of 10 are divisible by 5. Only the last digit matters.
Rule for 6: A number is divisible by 6 if it is divisible by BOTH 2 AND 3.
Example: 1,782 → ends in 2 (divisible by 2 ✓), sum = 1+7+8+2 = 18 (divisible by 3 ✓) → divisible by 6 ✓
Why it works: If a number is divisible by both 2 and 3, and 2 and 3 are coprime (GCF = 1), then it is divisible by 2×3 = 6.
Rule for 8: A number is divisible by 8 if its last three digits form a number divisible by 8.
Example: 5,136 → last three digits: 136 → 136 ÷ 8 = 17 → divisible by 8 ✓
Why it works: 1000 = 8 × 125, so any multiple of 1000 is divisible by 8.
Rule for 9: A number is divisible by 9 if the sum of its digits is divisible by 9.
Example: 7,281 → 7+2+8+1 = 18 → 18 ÷ 9 = 2 → divisible by 9 ✓ Check: 7,281 ÷ 9 = 809
Why it works: Same derivation as the rule for 3, but 9 divides 99, 999, etc., so only the digit sum matters.
Rule for 10: A number is divisible by 10 if its last digit is 0.
Example: 3,450 ends in 0 → divisible by 10 ✓
Rule for 11: Alternating sum of digits.
For a number, compute: (sum of digits in odd positions) − (sum of digits in even positions). If the result is divisible by 11 (including 0), the number is divisible by 11.
Example: 13,574 Odd positions (1st, 3rd, 5th from right): 4 + 5 + 1 = 10 Even positions (2nd, 4th): 7 + 3 = 10 10 − 10 = 0 → divisible by 11 ✓ Check: 13,574 ÷ 11 = 1,234
Example: 9,482 Odd: 2 + 4 + 9 = 15 Even: 8 15 − 8 = 7 → not divisible by 11 ✗
4. Modular Arithmetic (Clock Arithmetic)
Modular arithmetic is the mathematics of remainders. Instead of thinking about numbers on a line, we think about them on a circle — like a clock.
The Basic Idea
When we say "a mod n", we mean "the remainder when a is divided by n."
17 mod 5 = 2 (because 17 = 3×5 + 2) 38 mod 12 = 2 (because 38 = 3×12 + 2)
On a 12-hour clock: 14:00 → 2:00. That's 14 mod 12 = 2. If it's 10:00 now, what time will it be in 7 hours? 10 + 7 = 17, 17 mod 12 = 5 → 5:00.
Congruence Notation
We write:
a ≡ b (mod n)
This means "a and b have the same remainder when divided by n" — equivalently, n divides (a − b).
Examples: - 17 ≡ 2 (mod 5) — both leave remainder 2 when divided by 5 - 38 ≡ 14 (mod 12) — both have remainder 2 (38−14 = 24, divisible by 12) - 7 ≡ 7 (mod 3) — the definition is reflexive; any number is congruent to itself - −3 ≡ 2 (mod 5) — because −3 = −1×5 + 2 → remainder 2
⚠️ THIS IS CRITICAL — In modular arithmetic, negative numbers wrap around too. −3 mod 5 = 2 because going 3 counterclockwise on a 5-hour clock from 0 lands at 2.
Addition, Subtraction, and Multiplication Mod n
The beauty of modular arithmetic: you can do operations on the remainders and get the same result.
Addition: (a mod n) + (b mod n) ≡ (a + b) mod n
Example: What is the last digit of 7 + 8? 7 + 8 = 15 → last digit 5 7 mod 10 = 7, 8 mod 10 = 8, (7 + 8) mod 10 = 15 mod 10 = 5 ✓
Multiplication: (a mod n) × (b mod n) ≡ (a × b) mod n
Example: What is the last digit of 7 × 8? 7 × 8 = 56 → last digit 6 7 mod 10 = 7, 8 mod 10 = 8, (7 × 8) mod 10 = 56 mod 10 = 6 ✓
Practical use: What is (3⁵ × 7³) mod 5?
Instead of computing 3⁵ × 7³ = 243 × 343 = 83,349 then dividing by 5, we reduce first: 3 mod 5 = 3 7 mod 5 = 2
3⁵ mod 5: 3² = 9 ≡ 4 (mod 5), 3³ ≡ 4×3 = 12 ≡ 2, 3⁴ ≡ 2×3 = 6 ≡ 1, 3⁵ ≡ 1×3 = 3 So 3⁵ mod 5 = 3
2³ mod 5 = 8 mod 5 = 3
3 × 3 = 9 ≡ 4 (mod 5)
So (3⁵ × 7³) mod 5 = 4 ✓ (check: 243 × 343 = 83,349, 83,349 ÷ 5 = 16,669 remainder 4)
5. The Euclidean Algorithm for GCD
Recall from Subject 00-01: the GCD (greatest common divisor) can be found using prime factorization. But for large numbers, factorization is slow. The Euclidean algorithm is much faster.
The Key Insight
GCD(a, b) = GCD(b, a mod b)
If we divide a by b and get remainder r, then any divisor of both a and b also divides r, and any divisor of both b and r also divides a. So GCD(a,b) = GCD(b,r).
The Algorithm (Step by Step)
To find GCD(a, b) where a > b:
- Divide a by b: get quotient q and remainder r (a = qb + r, 0 ≤ r < b)
- If r = 0, then GCD(a, b) = b
- If r ≠ 0, set a = b, b = r, and repeat from step 1
Worked Example: GCD(48, 18)
$Step 1: 48 ÷ 18 = 2 remainder 12 → GCD(48, 18) = GCD(18, 12) Step 2: 18 ÷ 12 = 1 remainder 6 → GCD(18, 12) = GCD(12, 6) Step 3: 12 ÷ 6 = 2 remainder 0 → GCD(12, 6) = 6 $
Answer: GCD(48, 18) = 6
Check: 48 = 6 × 8, 18 = 6 × 3, GCF(8, 3) = 1 ✓
Another Example: GCD(252, 105)
$Step 1: 252 ÷ 105 = 2 remainder 42 Step 2: 105 ÷ 42 = 2 remainder 21 Step 3: 42 ÷ 21 = 2 remainder 0 $
Answer: GCD(252, 105) = 21
Check: 252 = 21 × 12, 105 = 21 × 5 ✓
The Euclidean Algorithm in Compact Form
$GCD(252, 105) → 252 = 2×105 + 42 GCD(105, 42) → 105 = 2×42 + 21 GCD(42, 21) → 42 = 2×21 + 0 GCD = 21 (the last non-zero remainder) $
6. LCM from GCD
Recall the fundamental relationship from 00-01:
GCD(a, b) × LCM(a, b) = a × b (for positive integers)
This means you can compute the LCM using the GCD:
LCM(a, b) = (a × b) ÷ GCD(a, b)
Example: LCM(48, 18)
First find GCD(48, 18) = 6 (from above) LCM = (48 × 18) ÷ 6 = 864 ÷ 6 = 144
Check using prime factorization: 48 = 2⁴ × 3, 18 = 2 × 3² LCM = 2⁴ × 3² = 16 × 9 = 144 ✓
Why this relationship holds:
Let a = GCD × a', b = GCD × b', where a' and b' are coprime (they share no common factors beyond 1). Then:
- GCD(a, b) = GCD
- LCM(a, b) = GCD × a' × b' (the product of all distinct prime powers)
- a × b = GCD² × a' × b'
- GCD × LCM = GCD² × a' × b' = a × b ✓
7. Primality Testing (Basic)
A prime number is an integer > 1 with exactly two positive divisors: 1 and itself. Testing whether a number is prime is fundamental to number theory and cryptography.
The Key Theorem
If n is composite (not prime), then n has a divisor d such that 2 ≤ d ≤ √n.
Why? If n = a × b and both a and b are greater than √n, then a × b > √n × √n = n, contradiction. So at least one factor is ≤ √n.
⚠️ THIS IS CRITICAL — To test if n is prime, you only need to check divisors up to √n. This saves enormous work for large numbers.
Trial Division Algorithm
To test if n is prime:
- If n < 2, not prime
- If n = 2, prime (the only even prime)
- If n > 2 is even, not prime
- For odd d from 3 to √n, test if d divides n
- If no d divides n, then n is prime
Optimization: You only need to test PRIME divisors up to √n (since if a composite divides n, its prime factors do too).
Example: Is 97 prime?
√97 ≈ 9.85, so we test primes ≤ 9: 2, 3, 5, 7
- 97 ÷ 2: no (odd)
- 97 ÷ 3: 97 = 3×32 + 1 → remainder 1 → no
- 97 ÷ 5: ends in 7 → no
- 97 ÷ 7: 7×13 = 91, 7×14 = 98 → 97 between → no
No divisor found → 97 is prime ✓
Example: Is 221 prime?
√221 ≈ 14.87, test primes ≤ 13: 2, 3, 5, 7, 11, 13
- 2, 3, 5: no (quick checks)
- 7: 7×31 = 217, remainder 4 → no
- 11: 11×20 = 220, remainder 1 → no
- 13: 13×17 = 221 → yes!
So 221 = 13 × 17 is composite.
Common Primes Under 100
For primality testing, memorize these primes:
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
Trick: For numbers under 100, you only ever need to check divisibility by 2, 3, 5, and 7. Why? Because √100 = 10, and the primes ≤ 10 are 2, 3, 5, and 7.
8. Common Misconceptions
Misconception 1: "All odd numbers are prime." - Wrong! 9 = 3×3, 15 = 3×5, 21 = 3×7, 25 = 5×5 are all odd but composite.
Misconception 2: "If a number passes the divisibility test for 2 and 3, it's prime." - Wrong! Divisibility by 2 AND 3 means divisible by 6 — the OPPOSITE of being prime (except that 6 itself passes but 6 = 2×3 is composite).
Misconception 3: "Modular arithmetic is just remainders, nothing deeper." - Wrong! Modular arithmetic is a complete number system with rich structure. It's the foundation for group theory, cryptography, hashing, and error-correcting codes.
Misconception 4: "1 is prime." - Wrong! By definition, a prime must have exactly two distinct positive divisors. 1 has only one (itself). So 1 is neither prime nor composite.
Key Terms
- Divisibility rules
- Euclidean algorithm
- LCM is computed from GCD
- Modular arithmetic
- Number theory
- Primality testing by trial division
- The Euclidean algorithm
Worked Examples
Example 1: Applying Multiple Divisibility Rules
Problem: Which of these numbers are divisible by 6: 2,394, 5,672, 9,048, 7,215?
Solution:
A number is divisible by 6 if divisible by 2 AND 3.
2,394: ends in 4 (even ✓), digit sum = 2+3+9+4 = 18 (divisible by 3 ✓) → divisible by 6
5,672: ends in 2 (even ✓), digit sum = 5+6+7+2 = 20 (not divisible by 3 ✗) → not divisible by 6
9,048: ends in 8 (even ✓), digit sum = 9+0+4+8 = 21 (divisible by 3 ✓) → divisible by 6
7,215: ends in 5 (odd ✗) → not divisible by 6 (don't need to check 3)
Answer: 2,394 and 9,048 are divisible by 6.
Example 2: Euclidean Algorithm for Large Numbers
Problem: Find GCD(945, 651) using the Euclidean algorithm.
Solution:
$Step 1: 945 ÷ 651 = 1 remainder 294 Step 2: 651 ÷ 294 = 2 remainder 63 Step 3: 294 ÷ 63 = 4 remainder 42 Step 4: 63 ÷ 42 = 1 remainder 21 Step 5: 42 ÷ 21 = 2 remainder 0 $
GCD = 21 (the last non-zero remainder)
Answer: GCD(945, 651) = 21
Check using the LCM relationship: LCM = (945 × 651) ÷ 21 = 615,195 ÷ 21 = 29,295 Check: 29,295 ÷ 945 = 31, 29,295 ÷ 651 = 45 ✓
Example 3: Modular Arithmetic Computation
Problem: Find the last digit of 7^100 (7 to the power 100).
Solution:
"Last digit" means computing 7^100 mod 10.
Let's find the pattern of 7^n mod 10: 7¹ mod 10 = 7 7² mod 10 = 49 mod 10 = 9 7³ mod 10 = 9 × 7 mod 10 = 63 mod 10 = 3 7⁴ mod 10 = 3 × 7 mod 10 = 21 mod 10 = 1 7⁵ mod 10 = 1 × 7 mod 10 = 7 ← pattern repeats!
The pattern cycles every 4: 7, 9, 3, 1, 7, 9, 3, 1, ...
Now, 100 mod 4 = 0 (100 is divisible by 4). When the remainder is 0, we take the 4th element in the cycle: 1.
Answer: The last digit of 7^100 is 1.
Verification: 7⁴ = 2401 (ends in 1), 7⁸ = 2401² ends in 1 (since 1×1 = 1). 100 is a multiple of 4, so 7^100 ends in 1.
Example 4: Comprehensive Primality Test
Problem: Determine whether 323 is prime.
Solution:
√323 ≈ 17.97. We need to test prime divisors up to 17: 2, 3, 5, 7, 11, 13, 17.
- 2: 323 is odd → no
- 3: 3+2+3 = 8, not divisible by 3 → no
- 5: doesn't end in 0 or 5 → no
- 7: 7×46 = 322, remainder 1 → no
- 11: alternating sum = 3−2+3 = 4, not divisible by 11 → no
- 13: 13×24 = 312, remainder 11 → no
- 17: 17×19 = 323 → yes!
So 323 = 17 × 19 is composite.
Answer: 323 is NOT prime.
Practice Problems
(Answers are below. Try each problem before checking.)
Problem 1: Test whether 1,728 is divisible by 3, 4, 8, and 9.
Problem 2: Find GCD(570, 741) using the Euclidean algorithm.
Problem 3: Find LCM(570, 741) using the GCD you found.
Problem 4: Compute 2^50 mod 7. (Hint: find the pattern of 2^n mod 7.)
Problem 5: Determine whether 149 is prime. Show your work.
Problem 6: What is (3^7 × 4^5) mod 5?
Problem 7: Find GCD(1001, 286) and then LCM(1001, 286).
Answers (click to expand)
**Problem 1:** - Divisible by 3? 1+7+2+8 = 18 → divisible by 3 ✓ - Divisible by 4? Last two: 28 ÷ 4 = 7 → divisible by 4 ✓ - Divisible by 8? Last three: 728 ÷ 8 = 91 → divisible by 8 ✓ - Divisible by 9? 1+7+2+8 = 18 → divisible by 9 ✓ **Problem 2:**$741 ÷ 570 = 1 rem 171 570 ÷ 171 = 3 rem 57 171 ÷ 57 = 3 rem 0 $GCD = **57** **Problem 3:** LCM = (570 × 741) ÷ 57 = 422,370 ÷ 57 = **7,410** **Problem 4:** 2¹ = 2, 2² = 4, 2³ = 8 ≡ 1 (mod 7) 2⁴ ≡ 2, 2⁵ ≡ 4, 2⁶ ≡ 1 → cycle of 3: 2, 4, 1, ... 50 mod 3 = 2 → 2^50 ≡ 2² = **4 (mod 7)** **Problem 5:** √149 ≈ 12.2. Test primes ≤ 11: 2, 3, 5, 7, 11 - 2: odd → no - 3: 1+4+9=14, not div by 3 → no - 5: doesn't end in 0 or 5 → no - 7: 7×21=147, rem 2 → no - 11: 11×13=143, rem 6 → no No divisors found → **149 is PRIME** **Problem 6:** 3⁷ mod 5: 3, 9≡4, 12≡2, 6≡1, 3, 4, 2 → position 7: 2 4⁵ mod 5: 4, 16≡1, 4, 1, 4 → position 5: 4 2 × 4 = 8 ≡ **3 (mod 5)** **Problem 7:** GCD: 1001 ÷ 286 = 3 rem 143 286 ÷ 143 = 2 rem 0 GCD = **143** LCM = (1001 × 286) ÷ 143 = 286,286 ÷ 143 = **2,002**
Summary
- Divisibility rules let you quickly test whether a number divides another without full division: rules exist for 2, 3, 4, 5, 6, 8, 9, 10, and 11
- Modular arithmetic works with remainders: a mod n is the remainder when a is divided by n; operations on remainders give correct remainders of the full result
- The Euclidean algorithm computes GCD(a, b) efficiently by repeatedly replacing (a, b) with (b, a mod b) until the remainder is 0
- LCM is computed from GCD using LCM(a,b) = |a×b| ÷ GCD(a,b) ⚠️ — this relationship is fundamental
- Primality testing by trial division only requires checking prime divisors up to √n; the √n bound follows from the fact that any composite n has a factor ≤ √n
Pitfalls
- Thinking 1 is prime. By definition a prime must have exactly two distinct positive divisors. 1 has only one (itself), so it is neither prime nor composite. This is one of the most frequently misremembered definitions.
- Testing all numbers up to n for primality instead of only up to √n. If n is composite, at least one factor is ≤ √n. Checking every number up to 100 to test primality of 97 wastes enormous effort—you only need to check primes up to √97 ≈ 9.8 (2, 3, 5, 7).
- Confusing modular equality with regular equality. 17 ≡ 2 (mod 5) means 17 and 2 have the same remainder when divided by 5. It does NOT mean 17 = 2. The \"mod n\" part is essential context.
- Stopping the Euclidean algorithm too early. The GCD is the last non-zero remainder, not the first remainder or the quotient. Continue dividing until the remainder is exactly 0, then the GCD is the previous remainder.
- Assuming odd numbers are automatically prime. 9, 15, 21, 25, 27, and 33 are all odd but composite. Being odd only means a number is not divisible by 2; it says nothing about divisibility by 3, 5, 7, etc.
Quiz
Answer each question, then read the explanation for your choice.
Q1: Which divisibility rules confirm that 4,356 is divisible by 4?
A) The sum of its digits is divisible by 4 B) The last digit is divisible by 4 C) The last two digits form a number divisible by 4 D) The last three digits form a number divisible by 4
Answer and Explanations
**Correct: C)** The rule for 4: check the last TWO digits. 56 ÷ 4 = 14 → divisible. - A) Sum of digits = 4+3+5+6 = 18. 18 is NOT divisible by 4. The sum-of-digits rule works for 3 and 9, not 4. - B) Last digit = 6. 6 is NOT divisible by 4. The last digit rule works for 2, 5, and 10. - C) ✓ Correct. Last two digits are 56, and 56 ÷ 4 = 14. - D) Last three = 356. 356 ÷ 4 = 89, so this would also work, but it's overkill — the rule for 8 uses last three digits. This answer isn't wrong in result but doesn't correctly state the standard rule for 4.Q2: What is 47 mod 12?
A) 3 B) 11 C) 4 D) 12
Answer and Explanations
**Correct: B) 11** 47 ÷ 12 = 3 remainder 11, so 47 mod 12 = 11. - A) 3: This is the quotient, not the remainder. 47 = 3×12 + 11. - B) 11: ✓ Correct. - C) 4: 47 − 44 = 3, and you might have done 47 − 43 = 4 by mistake. - D) 12: The remainder when dividing by 12 must be between 0 and 11. 12 is impossible (it would mean the quotient should be one higher).Q3: Using the Euclidean algorithm, find GCD(56, 21).
A) 7 B) 14 C) 3 D) 28
Answer and Explanations
**Correct: A) 7** 56 ÷ 21 = 2 remainder 14 21 ÷ 14 = 1 remainder 7 14 ÷ 7 = 2 remainder 0 GCD = 7 - A) 7: ✓ Correct. - B) 14: 14 divides 56 but does NOT divide 21 (21 ÷ 14 has remainder 7). - C) 3: 3 divides 21 but does NOT divide 56 (56 ÷ 3 has remainder 2). - D) 28: 28 divides 56 but does NOT divide 21.Q4: If GCD(84, 126) = 42, what is LCM(84, 126)?
A) 126 B) 168 C) 252 D) 210
Answer and Explanations
**Correct: C) 252** LCM = (84 × 126) ÷ 42 = 10,584 ÷ 42 = 252. - A) 126: 126 is one of the numbers, but 84 doesn't divide 126. - B) 168: 168 = 84 × 2 but 126 doesn't divide 168. - C) 252: ✓ Correct. 252 ÷ 84 = 3, 252 ÷ 126 = 2. - D) 210: 210 = 84 + 126. The LCM is not the sum of the numbers.Q5: What is 2^10 mod 3?
A) 0 B) 1 C) 2 D) 3
Answer and Explanations
**Correct: B) 1** 2 mod 3 = 2 ≡ −1 (mod 3) 2^10 = (2²)⁵ = 4⁵ ≡ 1⁵ = 1 (mod 3) since 4 ≡ 1 (mod 3) Or: 2¹⁰ = 1024, 1024 ÷ 3 = 341 remainder 1. - A) 0: 1024 ÷ 3 has remainder 1, not 0. Only multiples of 3 give remainder 0. - B) 1: ✓ Correct. - C) 2: 2 mod 3 = 2, but 2^10 mod 3 = 1, not 2. You may have assumed the remainder stays the same. - D) 3: Remainder when dividing by 3 must be 0, 1, or 2. 3 is impossible.Q6: Which of these numbers is prime?
A) 91 B) 117 C) 127 D) 143
Answer and Explanations
**Correct: C) 127** Test each number: - A) 91: 7 × 13 = 91. Composite. - B) 117: 1+1+7 = 9 → divisible by 9 (117 = 9 × 13). Composite. - C) 127: ✓ Prime. √127 ≈ 11.27. Test 2, 3, 5, 7, 11. 127 ÷ 7 = 18 rem 1, 127 ÷ 11 = 11 rem 6. No divisor works. - D) 143: 11 × 13 = 143. Composite.Q7: What is the last digit of 3^25?
A) 3 B) 9 C) 7 D) 1
Answer and Explanations
**Correct: A) 3** Pattern of 3^n mod 10: 3¹=3, 3²=9, 3³=7, 3⁴=1, 3⁵=3 → cycle: 3, 9, 7, 1 25 mod 4 = 1 → position 1 in cycle = 3 - A) 3: ✓ Correct. 25 mod 4 = 1, and the first element in the cycle is 3. - B) 9: This would be 3² or position 2 in the cycle. - C) 7: This would be 3³ or position 3 in the cycle. - D) 1: This would be 3⁴ or position 4 (remainder 0) in the cycle.Q8: A number is divisible by 6 if and only if:
A) It is divisible by 2 B) It is divisible by 3 C) It is divisible by both 2 and 3 D) Its last digit is even and its digit sum is even
Answer and Explanations
**Correct: C)** Since 6 = 2 × 3 and 2 and 3 are coprime, divisibility by both implies divisibility by 6. - A) Insufficient. 4 is divisible by 2 but not 6. - B) Insufficient. 9 is divisible by 3 but not 6. - C) ✓ Correct. Divisible by both 2 and 3 = divisible by 6 (because 2 and 3 are coprime). - D) Tricky but wrong. 14 has even last digit (4) and even digit sum (5 → odd, actually). Counterexample: 21 has even last digit? No, 1 is odd. How about 12: even last digit (2), digit sum = 3 (odd). 12 ÷ 6 = 2 ✓ divisible by 6, but digit sum is odd. Better counterexample: 24 has even last digit (4) and digit sum = 6 (even). 24 ÷ 6 = 4 ✓. Actually the condition is sufficient for many but the proper condition uses "digit sum divisible by 3", not "even digit sum".Q9: How many prime divisors do you need to test to determine whether 101 is prime?
A) All numbers from 2 to 100 B) Primes up to √101 ≈ 10 (2, 3, 5, 7) C) Primes up to 50 (half of 101) D) Only odd numbers up to 101
Answer and Explanations
**Correct: B)** If n is composite, it has a factor ≤ √n. √101 ≈ 10.05, so we only need to test primes ≤ 10: 2, 3, 5, 7 (4 divisors). - A) Testing 2 through 100 is 99 divisions — completely unnecessary. - B) ✓ Correct. The √n bound tells us to test only primes ≤ 10. None divide 101, so 101 is prime. - C) Testing up to 50 is still far more than needed (and wrong — the bound is √n, not n/2). - D) Testing all odd numbers up to 101 is ~50 tests (many redundant, e.g., testing 9 when 3 already failed).Q10: Which statement about modular arithmetic is TRUE?
A) (a × b) mod n = (a mod n) + (b mod n) B) (a + b) mod n = ((a mod n) + (b mod n)) mod n C) a mod n is always less than a D) If a ≡ b (mod n), then a = b
Answer and Explanations
**Correct: B)** Addition in modular arithmetic: compute individual remainders, add them, then take mod n of the result. - A) Wrong operation. (a × b) mod n = ((a mod n) × (b mod n)) mod n, not addition. - B) ✓ Correct. You can add the remainders, then take mod n of the sum. - C) Not always. If a < n (e.g., 3 mod 10 = 3), then a mod n = a. - D) Congruence means same remainder, not equality. 17 ≡ 2 (mod 5) but 17 ≠ 2.Next Steps
Congratulations! You have completed Phase 0 — Arithmetic & Number Foundations.
Move on to Phase 1, Subject 01-01 — Algebraic Expressions to begin your study of algebra: variables, constants, substitution, like terms, expanding brackets, and factorising.
Q5: If GCD(a, b) = 6 and a × b = 216, what is LCM(a, b)?
A) 6 B) 12 C) 36 D) 72
Answer: C) 36
For any two numbers: GCD × LCM = a × b. So LCM = (a × b) ÷ GCD = 216 ÷ 6 = 36.