« Divisibility

Corollary. [0039]

Let with the gcd of and equal to 1, and . Then .

Proof. From Bezout's Lemma there exists integers with . Multiply by to get . Since and by hypothesis, it follows that .

Backlinks

Lemma. Euclid's Lemma [0050]

Let and prime with then or .

Proof. We only need to show the case where . Because is prime, it has exactly the divisors . does not divide so their only common divisor is . Thus . We are done by applying this corollary.