Question

a) Show that if aand bare positive integers with a > b, then

$\begin{array}{r}\mathbf{gcd}\mathbf{}\mathbf{(}\mathbf{a}\mathbf{,}\mathbf{b}\mathbf{)}\mathbf{=}\mathbf{a}\mathbf{\text{if}}\mathbf{a}\mathbf{=}\mathbf{b}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\\ \mathbf{gcd}\mathbf{}\mathbf{(}\mathbf{a}\mathbf{,}\mathbf{b}\mathbf{)}\mathbf{=}\mathbf{2}\mathbf{gcd}\mathbf{}\mathbf{(}\mathbf{a}\mathbf{/}\mathbf{2}\mathbf{,}\mathbf{b}\mathbf{/}\mathbf{2}\mathbf{)}\mathbf{\text{if}}\mathbf{a}\mathbf{\text{and}}\mathbf{b}\mathbf{\text{are even}}\\ \mathbf{gcd}\mathbf{}\mathbf{(}\mathbf{a}\mathbf{,}\mathbf{b}\mathbf{)}\mathbf{=}\mathbf{2}\mathbf{gcd}\mathbf{}\mathbf{(}\mathbf{a}\mathbf{,}\mathbf{b}\mathbf{/}\mathbf{2}\mathbf{)}\mathbf{\text{if}}\mathbf{a}\mathbf{\text{is even and}}\mathbf{b}\mathbf{\text{is odd, and}}\\ \mathbf{gcd}\mathbf{}\mathbf{(}\mathbf{a}\mathbf{,}\mathbf{b}\mathbf{)}\mathbf{=}\mathbf{gcd}\mathbf{}\mathbf{(}\mathbf{a}\mathbf{-}\mathbf{b}\mathbf{,}\mathbf{b}\mathbf{)}\mathbf{\text{if both}}\mathbf{a}\mathbf{\text{and}}\mathbf{b}\mathbf{\text{are odd.}}\end{array}$

b) Explain how to use (a) to construct an algorithm for computing the greatest common divisor of two positive integers that uses only comparisons, subtractions, and shifts of binary expansions, without using any divisions.

c) Find using this algorithm

Short answer

• It is shown that
• $\begin{array}{r}\gcd (\mathrm{a},\mathrm{b})=\mathrm{a}\text{if}\mathrm{a}=\mathrm{b}\\ \gcd (\mathrm{a},\mathrm{b})=2\gcd (\mathrm{a}/2,\mathrm{b}/2)\text{if}\mathrm{a}\text{and}\mathrm{b}\text{are even}\\ \gcd (\mathrm{a},\mathrm{b})=2\gcd (\mathrm{a},\mathrm{b}/2)\text{if}\mathrm{a}\text{is even and}\mathrm{b}\text{is odd, and}\\ \gcd (\mathrm{a},\mathrm{b})=\gcd (\mathrm{a}-\mathrm{b},\mathrm{b})\text{if both}\mathrm{a}\text{and}\mathrm{b}\text{are odd.}\end{array}$

• Algorithm for finding greatest common divisor is constructed.

• gcd (1202,4848) = 2

Step-by-step solution

Greatest common divisor

Letaand bbe integers, not both zero. The largest integer such that aand is called the greatest common divisorof aand b. It is denoted by gcd (a,b) .

(a) Step 2: Proving part (a)

It is given that

aand bare positive integers and a > b

• If a = b

then and , we know the greatest common divisor of and cannot be greater than a and b, because divisor cannot be greater than the number itself, this implies thatis common divisor of a and b

gcd (a,b) = a

• If a and b are even.

Since both and are even then both have a common multiple of 2, therefore 2 is the common factor in the prime factorization of both.

Since prime factorization of greatest common divisors of a and b contains all the primes factorization of a and b, therefore prime factorization of contain a common factor of 2.

Therefore,

gcd (a,b) = gcd (a/2, b/2

• If a is even and b is odd.

Since a is even it has a factor of 2, but since b is odd it does not have a multiple of 2.

Since prime factorization of greatest common divisors of a and b contains all the primes factorization of a and b therefore prime factorization of does not contain a factor of 2.

Since 2 is not a common factor in the prime factorization

Therefore,

gcd (a,b) = gcd (a/2 , b)

• If bothaandare odd.

Let x = gcd (a,b), and there exists two integers y and z such that

d = ya + zb

We can also write

$\begin{array}{r}\mathrm{d}=\mathrm{ya}+\mathrm{zb}\\ \mathrm{d}=\mathrm{ya}-\mathrm{yb}+\mathrm{yb}+\mathrm{zb}\\ \mathrm{d}=\mathrm{y}(\mathrm{a}-\mathrm{b})+(\mathrm{y}+\mathrm{z})\mathrm{b}\end{array}$

Since y and z are integers therefore

d = gcd (a - b, b)

Therefore, gcd (a,b) = gcd (a - b, b)

(b) Step 3: Constructing algorithm without using division

Suppose and are two given integers, and we need to determine gcd (a,b)

let greatest common divisor is and initially d = 1

• If a and b are both equal, then gcd (a,b) = a

if a and b are even then we determine the gcd (a/2,b/2) = a and multiple it by 2.

$\begin{array}{r}a:=a/2\\ b:=b/2\\ d:=2d\end{array}$

• If ais even and bis odd, then

a := a/2

• if both a and b are odd.

a := a - b

• In each step of the algorithm, we will check the condition a = b

and if a = b then gcd (a,b) = a

 (c) Step 4: Finding using algorithm

Since we need to find gcd(1202,4848)

a = 1202 , b = 4848 initially d = 1

Since both, the numbers are even

therefore

a := a/2

b := b/2

c := 2d

Implies’

a := 601

b := 2424

c := 2

So, we need to determine gcd(601,2424)

Now a is odd and b is even

b := b/2

b := 1212

d := 2

So, we need to determine gcd(601,1212)

Again, a is odd and b is even

b := b/2

b := 303

d := 2

So, we need to determine gcd(601,303)

Now a and b both are odd

a:= a/2

a := 149

d := 2

So, we need to determine gcd(149,303)

Now both a and b are odd

b := b - a

b := 303 - 149 = 154

d := 2

So, we need to determine gcd(149,154)

Now a is odd b is even

b := b /2

b := 77

d := 2

So, we need to determine gcd(149,77)

Now both a and b are odd. So, we need to determine gcd (72,77) and d := 2

Now a is even and b is odd. So, we need to determine gcd (36,77) and d := 2

Now a is even and b is odd. So, we need to determine gcd (18,77) and d := 2

Now a is even and b is odd. So, we need to determine gcd (9,77) and d := 2

Now both a and b are odd. So, we need to determine gcd (9,68) and d := 2

Now a is odd and b is even. So, we need to determine gcd (9,34) and d := 2

Now a is odd and b is even. So, we need to determine gcd (9,17) and d := 2

Now both a and b are odd. So, we need to determine gcd (9,8) and d := 2

Now a is odd and b is even. So, we need to determine gcd (9,4) and d := 2

Now a is odd and b is even. So, we need to determine gcd (9,2) and d := 2

Now a is odd and b is even. So, we need to determine gcd (9,1) and d := 2

Now both a and b are odd. So, we need to determine gcd (8,1) and d := 2

Now a is even and b is odd. So, we need to determine gcd (4,1) and d := 2

Now a is even and b is odd. So, we need to determine gcd (2,1) and d := 2

Now a is even and b is odd. So, we need to determine gcd (1,1) and d := 2

Therefore, the greatest common divisor is equal to the value of d := 2

Hence gcd (1202 , 4848) = 2