StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q9RE

Expert-verifiedFound in: Page 307

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

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

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

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

(c)

${g}{c}{d}{(}{}{1234567}{,}{7654321}{)}$

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

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

(d)

${\mathrm{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.

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

role="math" localid="1668500714009" ${=}{{2}}^{min(3,9)}{{3}}^{min(5,7)}{{5}}^{min(7,5)}{{7}}^{min(9,3)}{{11}}^{min(1,0)}{{13}}^{min(1,0)}\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}$

94% of StudySmarter users get better grades.

Sign up for free