Divisibility, Primes, and the Euclidean Algorithm

GRE Math Subject · Axiom Academy

LESSON Divisibility, Primes, and the Euclidean Algorithm The foundations of number theory and fast GCD computation Key properties of divisibility: Linear combinations: and implies for all The division algorithm is the engine behind the Euclidean algorithm and modular arithmetic. Prime Numbers and Unique Factorization Key properties of primes (used constantly on the GRE): Euclid's Lemma: If and is prime, then or There are infinitely many primes (Euclid's proof) To test if is prime, check divisibility by primes up to GCD and LCM via prime factorizations: The Euclidean algorithm finds by repeated division. It is far faster than prime factorization for large numbers. The last nonzero remainder is 18 , so . GRE Speed Tip: You can often spot the GCD by inspection for small numbers. Use the algorithm only when the numbers are large or the answer is not obvious. Expressing GCD as a Linear Combination Finding : Back-substitute through the Euclidean algorithm. Problem 2: Find all integers such that . Problem 4: Does have integer solutions?

This is the written version of the interactive lesson above. See the full GRE Math Subject course.