Chapter 31, Problem 1P

(a)

Program Plan Intro

To prove that if both a and b are even, then $\gcd (a,b)=2\times \gcd (\frac{a}{2},\frac{b}{2})$

Explanation of Solution

If $\text{a and b}$ are both even, then it can be written that $\text{a }=\text{ 2}\left(\frac{\text{a}}{2}\right)\text{ and b }=\text{ 2}\left(\frac{b}{2}\right)$ , such that all the factors stated are integers. Therefore by using $\text{BATCH}-\text{POLLARD}-\text{RHO}\left(\text{n},\text{B}\right)$ ,which states that common factor 2 from both factors can be taken out of the whole function, it can be proved that $\gcd (a,b)=2\times \gcd (\frac{a}{2},\frac{b}{2})$ .

(b)

Program Plan Intro

To prove that if a is odd and b is even, then $\gcd (a,b)=\gcd (a,\frac{b}{2})$

Explanation of Solution

If b is even and a is odd, then it can be written $\text{b }=\text{ 2}\left(\frac{b}{2}\right)$ , where $\left(\frac{b}{2}\right)$ is an integer. As, it is known that a is not divisible by 2 (a is odd), the extra factor of 2 which is in b can’t be part of $\text{gcd}$ of the given both numbers. It states that $\text{gcd}\left(\text{a},\text{ b}\right)=\text{ gcd}\left(\text{a},\frac{\text{b}}{2}\right)$ . Now imagine $\text{d }=\text{ gcd}\left(\text{a},\text{ b}\right)$ . As d is the common divisor, a must be divisible by d , therefore, d shouldn’t contain even factors. Which states that d also divides $\text{a and }\frac{\text{b}}{\text{2}}$ . This states that $\gcd (a,b)\le \gcd (a,\frac{b}{2})$ . This inequality holds true even for the reverse procedure. As, the inequalities hold both ways, it results in equality $\gcd (a,b)=\gcd (a,\frac{b}{2})$ .

(c)

Program Plan Intro

To prove that if both a and b are odd, then $\gcd (a,b)=\gcd (\frac{a-b}{2},b)$

Explanation of Solution

if both a and b are odd, therefore $\text{a - b, where a > b}$ is also an odd number. Therefore, $\text{gcd}\left(\text{a},\text{ b}\right)=\text{ gcd}\left(\text{a }-\text{ b},\text{ b}\right)$ . Let

  $\begin{array}{l}\text{d = gcd}\left(\text{a},\text{ b}\right)\\ \text{d'}=\text{ gcd}\left(\text{a }-\text{ b},\text{ b}\right)\end{array}$ .

Then, there exists ${\text{n}}_{\text{1}},{\text{ n}}_{\text{2}}$ such that ${\text{n}}_{\text{1}}\text{a}+{\text{n}}_{\text{2}}\text{b }=\text{ d}$ . It can be rewritten as ${\text{n}}_{\text{1}}\left(\text{a}-\text{b}\right)+\left({\text{n}}_{\text{1}}+{\text{n}}_{\text{2}}\right)\text{b}=\text{d}$ . Therefore, $\text{d}\ge \text{d}\text{'}$ . To compute reverse, let ${\text{n'}}_{\text{1}}\text{a}+{\text{n'}}_{\text{2}}\text{b }=\text{ d'}$ so that $\text{n}{\text{'}}_{\text{1}}\left(\text{a}-\text{b}\right)+{\text{n'}}_{\text{2}}\text{b}=\text{d'}$ . It can be rewritten as $\text{n}{\text{'}}_{\text{1}}\text{a}+\left({\text{n'}}_{\text{2}}-{\text{n'}}_{\text{1}}\right)\text{b}=\text{d}\text{'}$ , therefore $\text{d'}\ge \text{d}$ . This means that $\text{gcd}\left(\text{a},\text{ b}\right)=\text{ gcd}\left(\text{a }-\text{ b},\text{ b}\right)=\text{ gcd}\left(\text{b},\text{ a }-\text{ b}\right)$ . This inequality holds true even for the reverse procedure. As, the inequalities hold both ways, it results in equality. Therefore, $\gcd (a,b)=\gcd (\frac{a-b}{2},b)$ .

(d)

Program Plan Intro

To design an efficient binary $\text{gcd}$ algorithm for integers a and b where $a\ge b$ and runs in $O(\lg a)$ time.

Explanation of Solution

  $\text{BINARY}-\text{GCD}\left(\text{a},\text{b}\right)$

if $\text{a mod 2 }\equiv \text{ 1}$ then

if $\text{b mod 2 }\equiv \text{ 1}$ then

return $\text{BINARY}-\text{GCD}\left(\frac{\left(\text{a }-\text{ b}\right)}{2},\text{ b}\right)$

else return $\text{BINARY}-\text{GCD}\left(\text{a},\frac{\text{b}}{2}\right)$

end if

else

  $\text{if b mod 2 }\equiv \text{ 1}$ then

return $\text{BINARY}-\text{GCD}\left(\frac{\text{a}}{2},\text{ b}\right)$

else

return $\text{2 }\times \text{BINARY}-\text{GCD}\left(\frac{\text{a}}{2},\frac{\text{b}}{2}\right)$

end if

end if