[proofplan] We prove the stronger assertion that the standard Euclidean algorithm computes the gcd in polynomial time. The algorithm first replaces the inputs by their absolute values, then repeatedly replaces a pair $(x,y)$ with $(y, x \bmod y)$ until the second coordinate is $0$. Correctness follows from the invariant that the set of common divisors is unchanged by the replacement $(x,y) \mapsto (y,x \bmod y)$, and polynomial running time follows from the fact that the smaller entry drops by at least a factor of $2$ every two iterations while each division with remainder on binary integers of input-size bit length is polynomial-time computable. [/proofplan] [step:Define the Euclidean algorithm on signed binary inputs] Let $\ell: \mathbb{Z} \to \mathbb{N}$ denote the signed binary length function, an element of $\operatorname{Map}(\mathbb{Z},\mathbb{N})$. Define $\ell(0)=1$ and, for each nonzero integer $n \in \mathbb{Z}$, let $\ell(n)$ be the number of bits needed to encode the sign and the binary expansion of $|n|$. Define $N := \ell(a) + \ell(b)$. We define the algorithm $E: \{(u,v) \in \mathbb{Z}^2 : u \neq 0 \text{ and } v \neq 0\} \to \mathbb{Z}_{\geq 0}$ from pairs of nonzero signed binary integers to nonnegative integers represented in signed binary encoding. On input $(a,b)$, set $x_0 := \max\{|a|,|b|\}$ and $y_0 := \min\{|a|,|b|\}$. Since $a$ and $b$ are nonzero, $x_0,y_0 \in \mathbb{N}$. For each index $i \geq 0$ with $y_i \neq 0$, let $q_i,r_i \in \mathbb{Z}$ be the quotient and remainder determined by Euclidean division, so that $x_i = q_i y_i + r_i$ and $0 \leq r_i < y_i$. Then set $x_{i+1} := y_i$ and $y_{i+1} := r_i$. When $y_t = 0$ for the first time, the algorithm returns $x_t$. [/step] [step:Prove the gcd invariant for one Euclidean step] Fix an index $i \geq 0$ with $y_i \neq 0$. We prove that $\gcd(x_i,y_i)=\gcd(y_i,r_i)$. Let $d \in \mathbb{N}$ be any positive integer. If $d$ divides both $x_i$ and $y_i$, then $d$ divides $x_i-q_i y_i=r_i$. Hence $d$ divides both $y_i$ and $r_i$. Conversely, if $d$ divides both $y_i$ and $r_i$, then $d$ divides $q_i y_i+r_i=x_i$. Hence $d$ divides both $x_i$ and $y_i$. Thus the positive common divisors of $(x_i,y_i)$ and $(y_i,r_i)$ are exactly the same set. Their largest positive elements are therefore equal, so $\gcd(x_i,y_i)=\gcd(y_i,r_i)$. [guided] The key point is that replacing $x_i$ by its remainder after division by $y_i$ does not change which positive integers divide both entries. Since $y_i \neq 0$, Euclidean division gives integers $q_i$ and $r_i$ satisfying $x_i = q_i y_i + r_i$ and $0 \leq r_i < y_i$. Now take an arbitrary positive integer $d \in \mathbb{N}$. Suppose first that $d$ is a common divisor of $x_i$ and $y_i$. Then $d$ divides every integer linear combination of $x_i$ and $y_i$, in particular $x_i-q_i y_i = r_i$. Thus $d$ divides both $y_i$ and $r_i$. Conversely, suppose that $d$ divides both $y_i$ and $r_i$. Then $d$ divides the integer linear combination $q_i y_i+r_i = x_i$. Thus $d$ divides both $x_i$ and $y_i$. We have proved equality of the two sets of positive common divisors: $\{d \in \mathbb{N}: d \mid x_i \text{ and } d \mid y_i\} = \{d \in \mathbb{N}: d \mid y_i \text{ and } d \mid r_i\}$. Since the gcd is the largest positive common divisor, the two gcds are equal: $\gcd(x_i,y_i)=\gcd(y_i,r_i)$. [/guided] [/step] [step:Conclude that the returned integer is the gcd] By the invariant from the previous step, each replacement $(x_i,y_i) \mapsto (x_{i+1},y_{i+1})$ preserves the gcd. Therefore, for every index $i$ before termination, $\gcd(x_i,y_i)=\gcd(x_0,y_0)$. At termination, $y_t=0$ and $x_t \in \mathbb{N}$. Since the positive common divisors of $x_t$ and $0$ are exactly the positive divisors of $x_t$, we have $\gcd(x_t,0)=x_t$. Therefore the algorithm returns $x_t=\gcd(x_t,0)=\gcd(x_0,y_0)=\gcd(|a|,|b|)=\gcd(a,b)$, where the final equality uses the standard convention that $\gcd(a,b)$ is the nonnegative gcd and is unchanged by replacing inputs by absolute values. [/step] [step:Bound the number of Euclidean iterations by a linear function of the input bit length] We prove that every two Euclidean iterations reduce the second coordinate by at least a factor of $2$. Fix an index $i$ with $y_i>0$. Write $r_i:=y_{i+1}$. If $r_i \leq y_i/2$, then after one iteration the new second coordinate already satisfies $y_{i+1}\leq y_i/2$. If instead $r_i>y_i/2$, then the next step divides $y_i$ by $r_i$, and its remainder is $y_{i+2}=y_i-r_i$, because $r_i<y_i<2r_i$. Hence $y_{i+2}<y_i/2$. Thus after every two iterations the positive second coordinate is less than half of its value two iterations earlier. Since $1 \leq y_0 \leq \min\{|a|,|b|\}$, the number of iterations is at most $2\lfloor \log_2 y_0 \rfloor + 2$. Because $y_0$ has binary length at most $N$, we have $\lfloor \log_2 y_0 \rfloor +1 \leq N$, so the number of iterations is at most $2N$. [/step] [step:Convert the iteration bound into polynomial bit complexity] During the algorithm all entries are nonnegative integers bounded above by $x_0=\max\{|a|,|b|\}$, so every integer appearing in the computation, including a possible zero remainder, has signed binary length at most $N$ by the definition of $\ell$ above. The preliminary operations of taking absolute values, comparing the two inputs, and swapping them are polynomial-time operations in $N$. At each Euclidean iteration the algorithm performs one integer division with remainder on integers of at most $N$ bits. By the standard binary long-[division algorithm](/theorems/725), fix a polynomial $P: \mathbb{N} \to \mathbb{N}$ such that one division with remainder on signed binary encodings of length at most $N$ is computable in time at most $P(N)$. Likewise, fix a polynomial $P_0: \mathbb{N} \to \mathbb{N}$ such that the preliminary operations of taking absolute values, comparing the two inputs, swapping them, and the final encoding step are computable in time at most $P_0(N)$. Since there are at most $2N$ iterations, the total running time is bounded by $2N \cdot P(N) + P_0(N)$, which is a polynomial in $N$. Therefore the Euclidean algorithm is a deterministic [polynomial-time algorithm](/page/Polynomial-Time%20Algorithm) which takes signed binary encodings of nonzero integers $a,b$ and returns the nonnegative integer $\gcd(a,b)$. This proves the theorem. [/step]