Module: Number theory

Number theory, least common multiple (LCM), greatest common divisor (GCD), primes, factorization, congruences, modular arithmetic.

Learning Outcomes

Use number theory to solve problems.

Compute the least common multiple and greatest common divisor.
Apply Euclid’s algorithm
Solve congruence systems using back substitution.

Readings

Rosen Sections 4.1 and 4.3

Divisibility, modular arithmetic, primes, greatest common divisors

Textbook 30 pages

Number theory

Number theory, LCM and GCD, primes and factorization, congruences and modular arithmetic, applications to computer science.

Lecture notes

Divisibility

Screencast on divisibility (Trevor)

Screencast 10 minutes TrevTutor

Modular arithmetic

Screencast on modular arithmetic (Trevor)

Screencast 9 minutes TrevTutor

Primes and GCD

Screencast on primes and greatest common divisor (Trevor)

Screencast 9 minutes TrevTutor

Euclidean algorithm

Screencast on Euclid’s algorithm (Trevor)

Screencast 10 minutes TrevTutor

Experiential Learning

Divisibility and modular arithmetic

Modular arithmetic (Rosen Section 4.1)

Problems

Divisibility and modular arithmetic

Modular arithmetic (Rosen Section 4.1)

Solutions

Primes and greatest common divisors

Prime factorization, greatest common divisor, least common multiple, Euclidean algorithm (Rosen Section 4.3)

Problems

Primes and greatest common divisors

Prime factorization, greatest common divisor, least common multiple, Euclidean algorithm (Rosen Section 4.3)

Solutions