From Concrete Mathematics, problem 4.35.
Let $I(m,n)$ be function that satisfies the relation
$$I(m,n)m+I(n,m)n=\gcd(m,n)$$
when $m,n\in \Bbb N$ with $m\neq n$. Thus, $I(m,n)=m′$ and $I(n,m)=n′$ in (4.5). The value of $I(m,n)$ is an inverse of $m$ with respect to $n$.
Find a recurrence that defines $I(m,n)$.
The (4.5) is just $m′m+n′n=\gcd(m,n)$.
I have no idea what I should do to solve the problem. What could I do with the condition "The value of $I(m,n)$ is an inverse of $m$ with respect to $n$". Is it useful to get the result?
$$I(m,n)m+I(n,m)n=\gcd(m,n)\qquad\qquad(*)$$
By the symmetry of this equation we can assume WLOG that $m\lt n$.
To find the recurrence relation for $I$, we can use the logic that follows equation (4.5) in the text (Knuth, "Concrete Mathematics").
If $m=0$ then we can have $I(0,n)=0$ and $I(n,0)=1$ to satisfy $(*)$ since $\gcd(0,n)=n$.
So assume now that $m\gt 0$. Letting $m_1=n-\left\lfloor\frac{n}{m}\right\rfloor m\;$ and $\;n_1=m,\;$ we have $\;m_1 \lt n_1$ and $m_1,n_1\in\mathbb{N}$. Therefore, function $I$ must satisfy: \begin{eqnarray*} I(m_1,n_1)m_1 + I(n_1,m_1)n_1 &=& \gcd(m_1,n_1) \\ && \\ \therefore\quad I(m_1,n_1)\left(n-\left\lfloor\frac{n}{m}\right\rfloor m\right) + I(n_1,m_1)m &=& \gcd(m,n) \\ && \\ \therefore\quad \left(I(n_1,m_1) - \left\lfloor\frac{n}{m}\right\rfloor I(m_1,n_1)\right)m + I(m_1,n_1)n &=& \gcd(m,n). \end{eqnarray*}
Comparing this with $(*)$ we see that:
\begin{eqnarray*} I(m,n) &=& I(n_1,m_1) - \left\lfloor\frac{n}{m}\right\rfloor I(m_1,n_1) \qquad\text{and} \\ I(n,m) &=& I(m_1,n_1). \end{eqnarray*}
So our recurrence relation for $I$, with $m\lt n$ is:
\begin{eqnarray*} I(0,n) &=& 0 \\ I(n,0) &=& 1 \\ I(m,n) &=& I(m,n-\left\lfloor\frac{n}{m}\right\rfloor m) - \left\lfloor\frac{n}{m}\right\rfloor I(n-\left\lfloor\frac{n}{m}\right\rfloor m,m) \\ I(n,m) &=& I(n-\left\lfloor\frac{n}{m}\right\rfloor m,m). \end{eqnarray*}
$$\\$$ $$\\$$ We illustrate using the example from the text, where $m=12, n=18$:
\begin{eqnarray*} I(12,18) &=& I(12, 18 - \left\lfloor\frac{18}{12}\right\rfloor 12) - \left\lfloor\frac{18}{12}\right\rfloor I(18 - \left\lfloor\frac{18}{12}\right\rfloor 12, 12) \\ && \\ &=& I(12,6) - I(6,12) \\ && \\ &=& \left[I(12- \left\lfloor\frac{12}{6}\right\rfloor 6,6)\right] - \left[I(6,12 - \left\lfloor\frac{12}{6}\right\rfloor 6) - \left\lfloor\frac{12}{6}\right\rfloor I(12 - \left\lfloor\frac{12}{6}\right\rfloor 6,6)\right] \\ && \\ &=& I(0,6) - I(6,0) + 2I(0,6) \\ && \\ &=& 0-1 + 2\times 0 = -1. \\ && \\ I(18,12) &=& I(18 - \left\lfloor\frac{18}{12}\right\rfloor 12, 12) \\ && \\ &=& I(6,12) \\ && \\ &=& I(6, 12 - \left\lfloor\frac{12}{6}\right\rfloor 6) - \left\lfloor\frac{12}{6}\right\rfloor I(12 - \left\lfloor\frac{12}{6}\right\rfloor 6, 6) \\ && \\ &=& I(6,0) - 2I(0,6) \\ && \\ &=& 1-2\times 0 = 1. && \\ && \\ \text{So we have} && -1\times m + 1\times n = \gcd(m,n) \\ && \\ \text{i.e.} && -1\times 12 + 1\times 18 = 6. \qquad\checkmark \end{eqnarray*}
Note: The text's remark about the inverse, I honestly can't make sense of that. But it doesn't seem necessary to the question anyway.