Question

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 $1,234,567\mathrm{and}7,654,321$.

d) Find the greatest common divisor of $2^3{3}^5{5}^7{7}^{9}11\mathrm{and}{2}^9{3}^7{5}^5{7}^{3}13$.

Short answer

(a)The greatest common divisor of $a\mathrm{and}\mathrm{b}$is the integer that satisfies the following two properties:

• $\mathrm{d}|\mathrm{a}\mathrm{and}\mathrm{d}|\mathrm{b}$
• For all integer c , if $\mathrm{c}|\mathrm{a}\mathrm{and}\mathrm{c}|\mathrm{b}$, then $\mathrm{c}\le \mathrm{d}$.

(b) Using prime factorizations, Euclidean algorithm, exhaustive method.

(c) 1.

(d)$2^3{3}^5{5}^5{7}^3\mathrm{or}2,083,725,000$

Step-by-step solution

Step 1

(a) The greatest common divisor of $\mathrm{a}\mathrm{and}\mathrm{b}$is the integer that satisfies the following two properties:

• $\mathrm{d}|\mathrm{a}\mathrm{and}\mathrm{d}|\mathrm{b}$.
• For all integer c , if $\mathrm{c}|\mathrm{a}\mathrm{and}\mathrm{c}|\mathrm{b}$, then $\mathrm{c}\le \mathrm{d}$.

Step 2

(b)

First method: using prime factorizations.

Determine the greatest common divisor by determining the prime factorization of each integer.

If the prime factorizations are $\mathrm{a}={\mathrm{p}}_1^{{\mathrm{a}}_1}{\mathrm{p}}_2^{{\mathrm{a}}_{12}}...{\mathrm{p}}_{\mathrm{n}}^{{\mathrm{a}}_{\mathrm{n}}}$and $\mathrm{b}={\mathrm{p}}_1^{{\mathrm{b}}_1}{\mathrm{p}}_2^{{\mathrm{b}}_2}...{\mathrm{p}}_{\mathrm{n}}^{{\mathrm{b}}_{\mathrm{n}}}$with ${\mathrm{p}}_1,{\mathrm{p}}_2,...{\mathrm{p}}_{\mathrm{n}}$prime numbers, $a_1,a_2,...a_n,b_1,b_2,...b_n$non-negative integers, then the greatest common divisor of $a_1,a_2,...a_n,b_1,b_2,...b_n$are:

$gcd(a,b)=p_1^{min\left(a_1,b_1\right)}{p}_2^{min\left(a_2,b_2\right)}\dots p_n^{min\left(a_n,b_n\right)}$

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 $\gcd (\mathrm{a},\mathrm{b})=\gcd (\mathrm{b},\mathrm{a}\mathrm{modb})$until $gcd(a,b)=gcd(c,d)$

with that $cmodd=0$and this would then imply $gcd(a,b)=gcd(c,d)=d$.

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 ).

Step 3

(c)

$gcd(1234567,7654321)$

To determine $gcd(a,b)$, we let $\mathrm{c}=\mathrm{a}\mathrm{modb}$. We return b if c=0 and we return $\ne 0$.

$$\begin{gathered} 1234567mod7654321=1234567\Rightarrow \gcd (1234567,7654321)=\gcd (7654321,1234567) \\ 7654321mod1234567=246919\Rightarrow \gcd (1234567,7654321)=\gcd (1234567,246919) \\ 1234567mod246919=246891\Rightarrow \gcd (1234567,7654321)=\gcd (246919,246891) \\ 246919mod246891=28\Rightarrow \gcd (1234567,7654321)=\gcd (246891,28) \\ 246891mod28=15\Rightarrow \gcd (1234567,7654321)=\gcd (28,15) \\ 28mod15=13\Rightarrow \gcd (1234567,7654321)=\gcd (15,13) \\ 15mod13=2\Rightarrow \gcd (1234567,7654321)=\gcd (13,2) \\ 13mod2=1\Rightarrow \gcd (1234567,7654321)=\gcd (2,1) \\ 2mod1=0\Rightarrow \gcd (1234567,7654321)=\gcd \left(1\right) \end{gathered}$$

Step 4

(d)

$\gcd (2^3{3}^5{5}^7{7}^{9}11,2^9{3}^7{5}^5{7}^{3}13)$

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.

$\gcd (2^3{3}^5{5}^7{7}^{9}11,2^9{3}^7{5}^5{7}^{3}13)$

role="math" localid="1668500714009" $$\begin{gathered} =2^{min(3,9)}{3}^{min(5,7)}{5}^{min(7,5)}{7}^{min(9,3)}{11}^{min(1,0)}{13}^{min(1,0)} \\ =2^3{3}^5{5}^7{7}^9{11}^1{13}^0 \\ =2^3{3}^5{5}^5{7}^3 \\ =2,083,725,000 \end{gathered}$$