# What is the worst case for the Euclidean algorithm in $\mathbb Z[i]$?

As you know, the worst case for the Euclidean algorithm in $$\mathbb Z$$ is two consecutive Fibonacci numbers. As any online GCD calculator that shows the steps of the Euclidean algorithm will demonstrate, computing $$\gcd(F_n, F_{n + 1})$$ results in a listing in descending order of the Fibonacci numbers from $$F_{n - 1}$$ all the way down to 0 (assuming $$n$$ is positive to begin with, some of the online calculators refuse to do anything with negative numbers like $$-89$$ or $$-144$$).

What is the worst case for $$\mathbb Z[i]$$, the Euclidean domain of Gaussian integers?

The first thing I tried was $$\gcd(F_n i, F_{n + 1})$$, but it pretty much boils down to the same thing as in $$\mathbb Z[i]$$.

The second thing I tried was Googling. First result was Wikipedia. Ugh.

That's when I decided to ask the question here. I'm getting a warning that this question "appears subjective and is likely to be closed."

But I think there is an objective criterion here for what constitutes a bad case for the Euclidean algorithm.

• This question is indeed probably far more objective than most questions beginning "What is the worst..." – Misha Lavrov Oct 14 '18 at 23:38
• A few thoughts: clearly(?) you're going to need every partial quotient to be a unit; elsewise you can get 'closer' while still maintaining the same number of steps. At the same time, you should be able to follow the usual proof by induction that if $\gcd(s_n, s_{n+1})$ is a unit and $s_{n+2}=\alpha s_{n+1}+\beta s_{n+2}$ then $\gcd(s_{n+1}, s_{n+2})$ is also a unit. At the same time, you need to control the sequence of units chosen such that e.g. no other (unit) multiple of $s_{n+1}$ can be subtracted from $s_{n+2}$ to yield a smaller magnitude than $s_n$. – Steven Stadnicki Oct 15 '18 at 0:54
• I wonder whether the Fibonacci polynomials are the worst case for the Euclidean algorithm in $\mathbb Q[x]$. It seems so... – lhf Oct 15 '18 at 1:43