GCD

Definition

Given is defined as the greatest integer and

Properties

Theorem

1. is prime or
2. If , ,
3. , , ,
4. If is a common divisor of
5. and
6. , ,
7. and
8. and and

Theorem

Proof: TODO

Theorem

Proof: Let . By definition and . So has to be a common divisor of and . And , by definition, is the greatest number that satisfies that. Therefore .

This theorem is very common and useful and is used in Euclid’s Division Lemma.

Theorem

This is very useful and is effectively dividing out the in the . A very common case of this theorem is when then it simplifies to . The intuition is that we first consider “What primes contributes to the “. Then can only “contribute” from what is left being .

Proof: We will go prime by prime. Fix a prime . Then let . The power of in is . We can make this power of with . So we get .

Proof: Let then with . Then

Then let and with we must have hence . Substituting that in and writing as we get as required.