Let . The greatest common divisor of and is where and are the DivisorsDivisors of and , respectively.
Theorem
Let . If there are such that , then Proof:
Let . We then have since , hence .
Theorem: Bézout's identity
Let , and . Then there exists integers such that Proof:
By repeating the theorem above, we get since it must end somewhere since the 's are strictly decreasing. This means that . Thus we have that and we can keep doing this until we get the form which means