Skip to content

2. Fundamental Concepts in Number Theory

Session Preparation:

Brooks: Chapter 2.

Session Material:

Session notes

Session Resources

Topic Description

In this session, we delve into the foundational aspects of number theory, which is essential for understanding the mathematical underpinnings of algorithms and data structures in software engineering. We will start by exploring different types of numbers, such as natural numbers, integers, rational numbers, irrational numbers, and real numbers.

Next, we will cover the process of prime factorisation and its significance, along with the Fundamental Theorem of Arithmetic. Modular arithmetic will also be introduced.

Key Concepts

  • Overview of number types
  • Prime factorisation
  • Highest and least common factors
  • Fundamental Theorem of Arithmetic
  • Divisors and remainders
  • Modular arithmetic

Exercises for recitation:

Notes from recitation

Exercise 1: Divisors

Find all the divisors of the following numbers:

a. \(10\) (1)

  1. \(1,2,5,10\)

b. \(11\) (1)

  1. \(1,11\)

c. \(12\)(1)

  1. \(1,2,3,4,6,12\)

d. \(99\) (1)

  1. \(1,3,9,11,33,99\)

e. \(100\) (1)

  1. \(1,2,4,5,10,20,25,50,100\)

Exercise 2: Prime Numbers

a. Which of the following statements about primes are true?

i) A prime is a number that only has one divisor.(1)

  1. False

ii) A prime is a number that has exactly two divisors.(1)

  1. True

iii) All primes are odd.(1)

  1. False

iv) There are 9 primes smaller than 20.(1)

  1. False

Which of the following numbers are primes?

b. \(1\)(1)

  1. Not prime

c. \(2\)(1)

  1. Prime

d. \(21\)(1)

  1. Not prime

e. \(31\) (1)

  1. Prime

f. \(499\)(1)

  1. Prime

g. \(512\)(1)

  1. Not prime

Exercise 3: Prime Factorization

Find the prime factorization of

a. \(120\)(1)

  1. \(2^3 \cdot 3 \cdot 5\)

b. \(375\) (1)

  1. \(3 \cdot 5^3\)

c. \(47\)(1)

  1. \(47\)

d. \(2860\)(1)

  1. \(2^2 \cdot 5 \cdot 11 \cdot 13\)

Exercise 4: Greatest Common Divisor

Use Exercise 1 or Exercise 3 to find the greatest common divisor.

a. \(\gcd(10,12)\).(1)

  1. \(2\)

b. \(\gcd(11,12)\)(1)

  1. \(1\)

c. \(\gcd(10,100)\)(1)

  1. \(10\)

d. \(\gcd(120,375)\)(1)

  1. \(15\)

e. \(\gcd(120,2860)\)(1)

  1. \(20\)

Exercise 5: Least Common Multiple

Find the least common multiple.

a. \(\text{lcm}(6,9)\)(1)

  1. \(18\)

b. \(\text{lcm}(20,50)\)(1)

  1. \(100\)

c. \(\text{lcm}(120,375)\) (1)

  1. \(3000\)

d. Calculate the product \(120 \cdot 375\).(1)

  1. \(45000\)

Exercise 6: Modulo Arithmetic

Find the remainder after division.

a. \(10\mod 4\)(1)

  1. \(2\)

b. \(10\mod 5\)(1)

  1. \(0\)

c. \(53\mod 4\)(1)

  1. \(1\)

d. \(55\mod 4\)(1)

  1. \(3\)

e. \(332\mod 12\)(1)

  1. \(8\)

Exercise 7: Modulo Arithmetic

What time does a 12-hour clock read

a. 80 hours after it reads 11:00 AM?(1)

  1. 7 PM

b. 40 hours after it reads 12:00 PM?(1)

  1. 4:00 AM

c. 100 hours after it reads 6:00 AM?(1)

  1. 10:00 AM