The Properties of Integers
Number theory is a branch of pure mathematics devoted primarily to the study of the integers.
Primes and Composites
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. (e.g., 2, 3, 5, 7, 11, ...)
A composite number is a natural number greater than 1 that is not prime; it can be formed by multiplying two smaller natural numbers. (e.g., 4, 6, 8, 9, 10, ...)
The Fundamental Theorem of Arithmetic states that every integer greater than 1 is either a prime number itself or can be represented as a unique product of prime numbers (prime factorization).
Example: 12 = 2 × 2 × 3 = 2² × 3
GCD and LCM
Greatest Common Divisor (GCD): The largest positive integer that divides two or more integers without a remainder. To find the GCD using prime factorization, take the lowest power of each common prime factor and multiply them.
Least Common Multiple (LCM): The smallest positive integer that is a multiple of two or more integers. To find the LCM using prime factorization, take the highest power of each prime factor present in any of the numbers and multiply them.
Example: Find the GCD and LCM of 12 (2² × 3) and 18 (2 × 3²).
GCD: Common primes are 2 and 3. Lowest power of 2 is 2¹. Lowest power of 3 is 3¹. GCD = 2¹ × 3¹ = 6.
LCM: Primes are 2 and 3. Highest power of 2 is 2². Highest power of 3 is 3². LCM = 2² × 3² = 4 × 9 = 36.
Modular Arithmetic
Modular arithmetic is a system of arithmetic for integers, where numbers 'wrap around' upon reaching a certain value—the modulus.
We say that a is congruent to b modulo n, written a ≡ b (mod n), if their difference (a - b) is an integer multiple of n.
A simpler way to think about it is that b is the remainder when a is divided by n.
Example: What is 17 mod 5?
17 divided by 5 is 3 with a remainder of 2.
So, 17 ≡ 2 (mod 5).
This is often called 'clock arithmetic'. On a 12-hour clock, 15 o'clock is 3 o'clock (15 ≡ 3 mod 12).