How to find the inverse of an algebraic integer mod q Let $K = \mathbb{Q}[i]$ and $\mathcal{O}_K = \mathbb{Z}[i]$. Suppose $a = 1 + 2i$ and $q = 7$. Since $a$ and $q$ are coprime algebraic integer, then there must exists $b \in \mathcal{O}_K $ s.t. $a * b = 1 \pmod{q} $. 
Is there an algorithm for finding that for a general number field $K$?
 A: Algorithm would be a bit exaggerated for a simple observation. In general, $z=u+iv$ in a unit mod $7$ in $\mathbf Z[i]$ if and only if its norm $N(z)=u^2+v^2$ is a unit in $\mathbf Z/7\mathbf Z$, and its inverse is $N(z)^{-1}\bar z$.
Hence, all you have to do is proceed with the extended Euclidean algorithm in $\mathbf Z$ for $N(z)$.
In the present case, $N(1+2i)=5$, its inverse mod. $7$ is $3$, hence
$$(1+2i)^{-1} \bmod 7=3(1-2i)=3+i.$$
A: If I understood correctly, you need
$$(1+2i)(a+bi)=1+7m\;,\;\;a,b,m\in\Bbb Z\implies a-2b+(2a+b)i=1+7m\iff$$
$$\begin{cases}a-2b=1+7m\\{}\\2a+b=0\end{cases}\;\;\;\implies5a=1+7m\implies a=3\pmod 7\;,\;\;b=-2a=1\pmod7$$
Thus, for example, with $\;3+i\;$:
$$(3+i)(1+2i)=1+7i=1\pmod7$$
But you could pick as well $\;10+8i\;$  say , since
$$(10+8i)(1+2i)=-6+28i=1\pmod7$$
A: No. Consider $K=\Bbb Q[\sqrt{-5}]$. Let $a=1+\sqrt{-5}$, $q=2$.
Suppose that there exists $b,c\in \Bbb Z[\sqrt{-5}]$ such that $ab+cq=1$. But now note that
$$3q=(1-\sqrt{-5})a$$
that is,
$$3bq=(1-\sqrt{-5})ab=(1-\sqrt{-5})(1-cq)$$
therefore,
$$q(3b+(1-\sqrt{-5})c)=1-\sqrt{-5}$$
which is clearly a contradiction.
In general, we can say that if the equation $ax\equiv 1\pmod m$ is solvable on some integral domain $R$ when $a$ and $m$ are coprime, then $R$ is an Unique Factorization Domain. But rings like $\Bbb Z[\sqrt d]$ where $d$ is a non square integer are not always UFD.
For those such rings that are Euclidean domains, the Euclidean algorithm works and you can use it to find inverses, just like in $\Bbb Z$.
A: In the specific case I would proceed as follows.
Since $7\equiv 3\bmod 4$ one knows that $7{\cal O}_K$ is a prime ideal and
$$
{\cal O}_K/7{\cal O}_K\simeq{\Bbb F}_7[i]
$$
is the field with $7^2$ elements.
Then one can solve $(1+2i)(x+2y)=1$ in ${\Bbb F}_7[i]$ which gives rise to a linear system in $\Bbb F_7^2$ pretty much as in DonAntonio's answer (which came out as I'm writing this).
It gives the solution
$$
x+2y\equiv 3-6i\equiv 3+i\bmod 7{\cal O}_K.
$$
I guess that one can tackle the general problem along the same lines as long as the ideal $q{\cal O}_K$ is maximal.
If not, one has to preliminary find the decomposition $q{\cal O}_K=\prod_i\wp_i^{e_i}$ in ${\cal O}_K$ where the $\wp_i$ are maximal. Then your starting element $a$ will be invertible modulo $q$ if and only if it is invertible modulo each and every $\wp_i^{e_i}$ by the Chinese Remainder Theorem.
Of course in the rare event where ${\cal O}_K$ is euclidean, one can use the division algorithm to explicit the Bezout identity.
