Lecture 8 - Integer Properties (Part 2)

Flashcards covering key definitions and theorems related to integer properties, modular arithmetic, and factorization from the lecture notes.

Modular arithmetic (mod n)

A system of arithmetic for integers where numbers "wrap around" when reaching a certain value n, where n is greater than or equal to 1.

Modulus (n)

The specific value in modular arithmetic (mod n) where values wrap around.

Congruence (a  (mod n))

For integers a and b, and a positive integer n, a is congruent to b mod n if a mod n = b mod n.

Fundamental Theorem of Arithmetic

Every positive integer other than 1 can be written uniquely as a prime number or as the product of its prime factors where the prime factors are written in non-decreasing order.

Prime factorization

The unique product of the prime factors of a positive integer, written in non-decreasing order.

Least Common Multiple (lcm(a, b))

For positive integers a and b, the smallest integer that is a multiple of both a and b.

Greatest Common Divisor (gcd(a, b))

For positive integers a and b, the largest integer that divides both a and b.

Relatively prime

Two positive integers a and b are relatively prime if their greatest common divisor (gcd(a, b)) is 1.

Euclidelps Algorithm

An efficient method to calculate the greatest common divisor of two integers, especially for large numbers where prime factorization is difficult.

LCM formula (using GCD)

If the greatest common divisor of a and b is known, the least common multiple can be found using the formula: lcm(a, b) = (a * b) / gcd(a, b).