Book edition 7th

Author(s) Kenneth H. Rosen

Pages 808 pages

ISBN 9780073383095

Answers without the blur.

Just sign up for free and you're in.

Short Answer

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 and 7, 654, 321$ .
d) Find the greatest common divisor of $2^{3} 3^{5} 5^{7} 7^{9} 11 and 2^{9} 3^{7} 5^{5} 7^{3} 13$ .

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

$d | a and d | b$
For all integer c , if $c | a and c | b$ , then $c \leq d$ .

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

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

See the step by step solution

Step by Step Solution

TABLE OF CONTENTS :

TABLE OF CONTENTS

Step 1

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

$d | a and d | b$ .
For all integer c , if $c | a and c | b$ , then $c \leq 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 $a = p_{1}^{a_{1}} p_{2}^{a_{12}} . . . p_{n}^{a_{n}}$ and $b = p_{1}^{b_{1}} p_{2}^{b_{2}} . . . p_{n}^{b_{n}}$ with $p_{1}, p_{2}, . . . p_{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 (a_{1}, b_{1})} p_{2}^{min (a_{2}, b_{2})} \dots p_{n}^{min (a_{n}, b_{n})}$

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 (a, b) = \gcd (b, a 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 ).

Step 3

(c)

$g c d (1234567, 7654321)$

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

$1234567 mod 7654321 = 1234567 \Rightarrow \gcd (1234567, 7654321) = \gcd (7654321, 1234567) 7654321 mod 1234567 = 246919 \Rightarrow \gcd (1234567, 7654321) = \gcd (1234567, 246919) 1234567 mod 246919 = 246891 \Rightarrow \gcd (1234567, 7654321) = \gcd (246919, 246891) 246919 mod 246891 = 28 \Rightarrow \gcd (1234567, 7654321) = \gcd (246891, 28) 246891 mod 28 = 15 \Rightarrow \gcd (1234567, 7654321) = \gcd (28, 15) 28 mod 15 = 13 \Rightarrow \gcd (1234567, 7654321) = \gcd (15, 13) 15 mod 13 = 2 \Rightarrow \gcd (1234567, 7654321) = \gcd (13, 2) 13 mod 2 = 1 \Rightarrow \gcd (1234567, 7654321) = \gcd (2, 1) 2 mod 1 = 0 \Rightarrow \gcd (1234567, 7654321) = \gcd (1)$

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" $= 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$

Find Study Materials for

Create Study Materials

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

Step by Step Solution

Step 1

Step 2

Step 3

Step 4

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

Step by Step Solution

Step 1

Step 2

Step 3

Step 4

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Decision Maths

Calculus

Probability and Statistics

Statistics

Mechanics Maths

Geometry

Pure Maths