Well Ordering Principle

Division Algorithm

Let a and b be integers with b > 0.

 Then there exist unique integers q and r with the property that 

a = bq + r,      where      0 ≤ r < b. 

GCD is a linear combination

For any nonzero integers a and b, there exist integers

s and t for which gcd(a,b) = as + bt.

Furthermore, gcd(a,b) is the smallest positive integer of the form as + bt.

Euclid’s Lemma

(Euclidean Algorithm)

For a prime p, if  p | ab  then

p | a  or  p | b.

Fundamental Theorem of Arithmetic

• Every integer greater than 1 is a prime or a product of primes. 
• This product is unique, except for the order in which factors appear.