Hints

$(1)$

For the input $a$ and $b$ , we define $c(a, b) = n_a + n_b$ . Observe that after in each recursive call, this quantity deceases strictly. So, it is enough to prove the algorithm by induction on $c(a, b)$ , which is easy.

$(2)$

Two observations

• there is at most $n_a + n_b$ recursive calls.
• each recursive call is either terminal or leads to another recursive call plus at most 3 operations in ${\mathbb{Z}}$ : multiplication by 2, division by $2$ , subtraction. Each of these operations in ${\mathbb{Z}}$ amounts to a number of word-operations which is linear in the size of the arguments.

Therefore, the algorithm runs in $O(n_a + n_b)$ operations in ${\mathbb{Z}}$ and in $O((n_a + n_b)^2)$ word operations.

$(3)$

Algorithm in ${\mbox{${\mathbb{Z}}$}}/2{\mbox{${\mathbb{Z}}$}}[x]$ :

 
${\gcd}(a,b)$
 == 


1 		 		 if $a = b$
 then return $a$
 


2 		 		 if $a(0)=0$
 and $b(0)=0$
 then return 
$x \ {\gcd}(a/x, b/x)$
 


3 		 		 if $a(0)=0$
 and $b(0)=1$
 then return 
${\gcd}(a/x, b)$
 


3 		 		 if $a(0)=1$
 and $b(0)=0$
 then return 
${\gcd}(a, b/x)$
 


4 		 		 if 
${\deg} a > {\deg} b$
 then return 
${\gcd}((a-b)/x,b)$
 else  return 
${\gcd}((b-a)/x,a)$