a) Define the greatest common divisor of two integers.
b) Describe at least three different ways to find the greatest common divisor of two integers. When does each method work best?
c) Find the greatest common divisor of .
d) Find the greatest common divisor of .
(a)The greatest common divisor of is the integer that satisfies the following two properties:
(b) Using prime factorizations, Euclidean algorithm, exhaustive method.
(a) The greatest common divisor of is the integer that satisfies the following two properties:
First method: using prime factorizations.
Determine the greatest common divisor by determining the prime factorization of each integer.
If the prime factorizations are and with prime numbers, non-negative integers, then the greatest common divisor of are:
Obviously, this method will work best when the prime factorizations have been given or when the integers are small and easy to factorize.
Second method: Euclidean algorithm.
Determine the greatest common divisor by using until
with that and this would then imply .
This method is best used when the integers are large and hard to factorize.
Third method: Exhaustive method.
Determine all divisors of the two integers a and b. Their greatest common divisor is then the largest possible integer q such that q divides a and q divides b.
This method is the least effective and only works best when both integers are prime numbers (as then we know that the greatest common divisor is 1 ).
To determine , we let . We return b if c=0 and we return .
The prime factorization of the greatest common divisors then has the same primes as the two integers, while the powers are the minimum of the powers in the prime factorizations of the two integers.
94% of StudySmarter users get better grades.Sign up for free