Let $f_0$ and $f_1$ be Gaussian Integers such that $f_0 = a + i$ and $f_1 = b + i$. How can I compute $f_0^{-1} mod f_1$ and $f_1^{-1} mod f_0$?
I've been trying to apply the Extended Euclidean algorithm, as I would do in other Finite Field contexts, but the result never converges. Am I missing something?
Because you are strangely reluctant to give examples of your calculations I can only guess.
Possibility 1. When $a$ and $b$ are both odd the computation will automatically fail because in this case they have the common factor $1+i$. Letting $a=2n+1$ we get $$ \begin{aligned} \frac{a+i}{1+i}&=\frac{2n+1+i}{1+i}=\frac{(2n+1+i)(1-i)}{(1+i)(1-i)}\\ &=\frac{2n+1+1-(2n+1)i+i}2\\ &=(n+1)-ni. \end{aligned} $$
Possibility 2. When there are no common divisors you should remember to carefully use a smaller remainder at some step. In a division step involving Gaussian integers, $$a=qb+r,$$ we must make sure that we always have $|r|<|b|$. I find it pedagogically advantageous (though not by any means necessary) to run the extended Euclidean algorithm using augmented matrices. We begin by augmenting an identity matrix with a column of those two numbers (here $a+i$ and $b+i$), and then do elementary row operations, subtracting one row from the other multiplied by "an approximate quotient" $q$. As an example, consider $a=5$, $b=8$, so we want to calculate the modular inverses of $5+i$ and $8+i$ modulo the other: $$ \left(\begin{array}{cc|c}1&0&5+i\\0&1&8+i\end{array}\right) $$ We can first use $q=1$ and write $8+i=1\cdot(5+i)+3$ because $|3|<|5+i|$, so in the first step we subtract the first row from the second $$ \rightarrow\left(\begin{array}{cc|c}1&0&5+i\\-1&1&3\end{array}\right). $$ Then we can use $q=2$ as in $5+i=2\cdot3+(-1+i)$ we have $|-1+i|<|3|$. Subtract the second row multiplied by two from the first $$ \rightarrow\left(\begin{array}{cc|c}3&-2&-1+i\\-1&1&3\end{array}\right). $$ Next we can use $q=-1-i$ because $(-1-i)(-1+i)=2$ and therefore $(3+i)=(-1-i)(-1+i)+1.$ Subtract the first row multiplied by $-1-i$ from the second. Or, rather, add the first row multiplied by $1+i$ to the second $$ \rightarrow\left(\begin{array}{cc|c}3&-2&-1+i\\2+3i&-1-2i&1\end{array}\right). $$ We got a unit (here $1$) remainder to appear in the augmented column, so we know that gcd is equal to one (had we gotten another unit, for example $i$, as a remainder instead, we would then multiply the row by the reciprocal). Whenever our augmented matrix has a row $(a\ b\ |\ c)$ we have the relation $a(5+i)+b(8+i)=c$, so from the last row we can read $$ (2+3i)(5+i)-(1+2i)(8+i)=1 $$ telling us that the inverse of $5+i$ modulo $8+i$ is $(5+i)^{-1}=2+3i$ and that the inverse of $8+i$ modulo $5+i$ is $(8+i)^{-1}=-(1+2i)$.
Of course, you can use representatives of your choice for these cosets. Modulo a Gaussian of the form $a+i$ we can always use integers modulo $a^2+1$ as representatives. Here $$ 2+3i\equiv 2+3i-3(8+i)=-22\equiv-22+65=43\pmod{8+i} $$ (I used $65=(8+i)(8-i)$ to get a positive integer remainder), and $$ -1-2i\equiv-1-2i+2(5+i)=9\pmod{5+i}. $$