• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon

### Select your language

Suggested languages for you:

Americas

Europe

Q9RE

Expert-verified
Found in: Page 307

### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095

# 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}$.

(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}$

See the 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:

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

with that ${c}{}{m}{o}{d}{}{d}{=}{0}$ and this would then imply ${g}{c}{d}{\left(}{}{a}{,}{b}{\right)}{=}{g}{c}{d}{\left(}{}{c}{,}{d}{\right)}{=}{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)

${g}{c}{d}{\left(}{}{1234567}{,}{7654321}{\right)}$

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

${1234567}{mod}{7654321}{=}{1234567}{⇒}{\mathrm{gcd}}{}{\left(}{1234567}{,}{7654321}{\right)}{=}{\mathrm{gcd}}{}{\left(}{7654321}{,}{1234567}{\right)}\phantom{\rule{0ex}{0ex}}{7654321}{mod}{1234567}{=}{246919}{⇒}{\mathrm{gcd}}{}{\left(}{1234567}{,}{7654321}{\right)}{=}{\mathrm{gcd}}{}{\left(}{1234567}{,}{246919}{\right)}\phantom{\rule{0ex}{0ex}}{1234567}{mod}{246919}{=}{246891}{⇒}{\mathrm{gcd}}{}{\left(}{1234567}{,}{7654321}{\right)}{=}{\mathrm{gcd}}{}{\left(}{246919}{,}{246891}{\right)}\phantom{\rule{0ex}{0ex}}{246919}{mod}{246891}{=}{28}{⇒}{\mathrm{gcd}}{}{\left(}{1234567}{,}{7654321}{\right)}{=}{\mathrm{gcd}}{}{\left(}{246891}{,}{28}{\right)}\phantom{\rule{0ex}{0ex}}{246891}{mod}{28}{=}{15}{⇒}{\mathrm{gcd}}{}{\left(}{1234567}{,}{7654321}{\right)}{=}{\mathrm{gcd}}{}{\left(}{28}{,}{15}{\right)}\phantom{\rule{0ex}{0ex}}{28}{mod}{15}{=}{13}{⇒}{\mathrm{gcd}}{}{\left(}{1234567}{,}{7654321}{\right)}{=}{\mathrm{gcd}}{}{\left(}{15}{,}{13}{\right)}\phantom{\rule{0ex}{0ex}}{15}{mod}{13}{=}{2}{⇒}{\mathrm{gcd}}{}{\left(}{1234567}{,}{7654321}{\right)}{=}{\mathrm{gcd}}{}{\left(}{13}{,}{2}{\right)}\phantom{\rule{0ex}{0ex}}{13}{mod}{2}{=}{1}{⇒}{\mathrm{gcd}}{}{\left(}{1234567}{,}{7654321}{\right)}{=}{\mathrm{gcd}}{}{\left(}{2}{,}{1}{\right)}\phantom{\rule{0ex}{0ex}}{2}{mod}{1}{=}{0}{⇒}{\mathrm{gcd}}{}{\left(}{1234567}{,}{7654321}{\right)}{=}{\mathrm{gcd}}{}{\left(}{1}{\right)}$

## Step 4

(d)

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

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.

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

role="math" localid="1668500714009" ${=}{{2}}^{min\left(3,9\right)}{{3}}^{min\left(5,7\right)}{{5}}^{min\left(7,5\right)}{{7}}^{min\left(9,3\right)}{{11}}^{min\left(1,0\right)}{{13}}^{min\left(1,0\right)}\phantom{\rule{0ex}{0ex}}{=}{{2}}^{{3}}{{3}}^{{5}}{{5}}^{{7}}{{7}}^{{9}}{{11}}^{{1}}{{13}}^{{0}}\phantom{\rule{0ex}{0ex}}{=}{{2}}^{{3}}{{3}}^{{5}}{{5}}^{{5}}{{7}}^{{3}}\phantom{\rule{0ex}{0ex}}{=}{2}{,}{083}{,}{725}{,}{000}$