Integer d > 0 is the Greatest common divisor of a and b, d = gcd(a,b), iff
d|a and d|b
(divisor)for c|a and c|b, then c ≤ d
(greatest)For a = bq + r, then gcd(a,b) = gcd(b,r)
Very useful for calculating GCDs, and proving values of GCDs. Repeated use becomes Euclidean Algorithm.
If d is a common divisor of a and b and ax + by = d has an integer solution, then d=gcd(a,b)
This shows that any combination of a and b can only be equal to multiples of the gcd.
If d = gcd(a,b), then there exist x,y s.t. ax + by = d
Useful for rewriting gcds in equations
a and b are coprime if gcd(a,b)=1. If c|(a•b), then c|a or c|b
If p is prime, and p|ab, then p|a or p|b
gcd(a,b)=1 iff there exists x and y with ax + by = 1
GCD CT for d = 1.
if d = gcd(a,b) then gcd(a/d, b/d) = 1
If this wasn't the case, then there would be a larger common divisor than d
An integer p > 1 is prime iff its only divisors are 1 and p.
By induction, there are infinitely many primes.
Every integer can be uniquely expressed as a product of primes.