Course outline
Module 1
Module 1: Introduction to Number Theory
Introduction to Number Theory
Knowledge check
Q1. What is the smallest prime number?
Why: 2 is the smallest prime number because it is the only even prime number and it has exactly two distinct positive divisors: 1 and itself.
Q2. Which of the following is a composite number?
- A. 11
- B. 13
- C. 15 ✓
- D. 17
Why: 15 is a composite number because it has more than two distinct positive divisors (1, 3, 5, and 15).
Q3. What is the greatest common divisor (GCD) of 12 and 18?
Why: The GCD of 12 and 18 is 6 because 6 is the largest number that divides both 12 and 18 without leaving a remainder.
Q4. What is the least common multiple (LCM) of 4 and 6?
Why: The LCM of 4 and 6 is 12 because 12 is the smallest number that both 4 and 6 divide into without leaving a remainder.
Q5. Which of the following numbers is divisible by 5?
- A. 23
- B. 35 ✓
- C. 47
- D. 53
Why: 35 is divisible by 5 because it ends in 5, and any number ending in 0 or 5 is divisible by 5.
Module 2
Module 2: Divisibility and Prime Numbers
Divisibility and Prime Numbers
Module 3
Module 3: The Euclidean Algorithm
The Euclidean Algorithm
Knowledge check
Q1. What is the greatest common divisor (GCD) of 24 and 36?
Why: The GCD of 24 and 36 is found by dividing both numbers by their common factors until no more common factors exist. The largest common factor is 6.
Q2. Which of the following is a step in the Euclidean Algorithm?
- A. Add the two numbers
- B. Subtract the smaller number from the larger one ✓
- C. Multiply the two numbers
- D. Divide the smaller number by the larger one
Why: The Euclidean Algorithm involves repeatedly subtracting the smaller number from the larger one until the remainder is zero.
Q3. What is the GCD of 17 and 51?
Why: Since 17 divides 51 exactly, the GCD of 17 and 51 is 17.
Q4. Using the Euclidean Algorithm, what is the first step to find GCD(84, 36)?
- A. Divide 84 by 36 ✓
- B. Divide 36 by 84
- C. Add 84 and 36
- D. Subtract 36 from 84
Why: The first step in the Euclidean Algorithm is to divide the larger number by the smaller one.
Q5. What is the GCD of 100 and 25?
- A. 25 ✓
- B. 50
- C. 100
- D. 250
Why: Since 25 divides 100 exactly, the GCD of 100 and 25 is 25.
Module 4
Module 4: Modular Arithmetic
Modular Arithmetic
Knowledge check
Q1. What is 7 mod 3?
Why: 7 divided by 3 gives a remainder of 1.
Q2. What is the value of 15 mod 4?
Why: 15 divided by 4 gives a remainder of 3.
Q3. Which of the following is congruent to 10 mod 7?
Why: 10 divided by 7 gives a remainder of 3.
Q4. What is the result of 12 mod 5?
Why: 12 divided by 5 gives a remainder of 2.
Q5. Which of the following is congruent to 18 mod 6?
Why: 18 divided by 6 gives a remainder of 0.
Module 5
Module 5: Fermat's Little Theorem
Module 6
Module 6: Euler's Theorem
Euler's Theorem
Knowledge check
Q1. What is Euler's totient function φ(n) primarily used for?
- A. To find the number of divisors of n
- B. To find the number of integers less than n that are coprime to n ✓
- C. To find the prime factors of n
- D. To find the square root of n
Why: Euler's totient function φ(n) counts the number of positive integers less than n that are coprime to n.
Q2. What is φ(1)?
Why: φ(1) is 1 because the only number less than or equal to 1 is 1 itself, and it is coprime to itself.
Q3. What is φ(7)?
Why: φ(7) = 6 because 7 is a prime number and φ(p) = p - 1 for any prime p.
Q4. According to Euler's Theorem, if a and n are coprime, then a^φ(n) ≡ ? (mod n)
Why: Euler's Theorem states that if a and n are coprime, then a^φ(n) ≡ 1 (mod n).
Q5. What is φ(8)?
Why: φ(8) = 4 because the numbers less than 8 that are coprime to 8 are 1, 3, 5, and 7.
Module 7
Module 7: Applications of Number Theory
Applications of Number Theory