Solutions to two Bézout equations solve a third one Let $p$ and $q$ be relatively prime integers, and let $a, b, c, d$ be the minimal solutions of
$$\begin{align}
ap - bq & = 1 \\
cq - dp & = 1. 
\end{align}
$$
Then I want to show that $$ac - bd = 1.$$
The obvious strategy of mashing on the algebra might work, but I haven't been able to make it work. For example, multiplying the first equation by $d$, the second by $a$, and adding, yields $(ac-bd)q = a+d$, which looks promising, and if I could show that $a+d=q$, I would be done. But…
 A: Let's assume $p, q > 1$ (I'll leave the other cases to you).
The solutions of $x p - y q = 1$ are of the form $x = a + m q$, $y = b + m p$ for integers $m$, where $(a, b)$ is one solution.  If we choose $a$ with
$0 \le a < q$, then $b = (a p - 1)/q$ with $-1/q \le b < p - 1/q$, and thus
$0 \le b < p$.  Moreover, it's easy to see they can't be $0$.
This is the "minimal solution": $a$ is the integer with 
$0 < a < q$ and $a \equiv p^{-1} \mod q$, and $b$ is the integer with
$0 < b < p$ and $b \equiv -q^{-1} \mod p$.  Similarly, $c$ is the integer with
$0 < c < p$ and $c \equiv q^{-1} \mod p$, and $d$ is the integer with
$0 < d < q$ and $d \equiv -p^{-1} \mod q$.
  Now $a + d \equiv 0 \mod q$, and since $0 < a+d < 2q$ the only possibility is $a+d=q$.
A: I have a way to prove it but it seems roundabout, involving properties of Farey sequences:
The first two Bézout relations show that that $\frac ba,\frac pq, \frac cd$ are consecutive terms in a Farey sequence, I think.  But then we know that $\frac ba, \frac cd$ are consecutive in the previous Farey sequence which omits $\frac pq$, and the third relation, $ac- bd = 1$,  follows from this.
Or if you prefer, once we have the Farey sequence, $a+d = q$  (and $b+c = p$) because $\frac pq$ is the mediant of $\frac ba$ and $\frac cd$, and, as I observed in the question, once we have $a+d=q$, we win.
But I feel that there should be some more direct proof,  not involving Farey sequences explicitly, or coming from the same place that the Farey sequence properties came from in the first place.
A: Hint $\ $ If $\rm\:(x,y) = (a,b)\:$ solves $\rm\:p\, x\! -\! q\, y\, =\, 1\:$ and is minimal $\rm\ 0 \le a < q,\:$ then the minimal solution with opposite signs is  "neighbor"
$\rm\ (d,c)\, =\, -((a,b)-(q,p))\, =\, (q\!-\!a,p\!-\!b).\:$ Thus
$$\rm ac-bd\ =\ \left|\begin{array}{cc}\rm a &\rm b\\ \rm d & \rm c\end{array}\right|\ =\ \left|\begin{array}{cc}\rm a &\rm b\\ \rm q\!-\!a \!&\! \rm p\!-\!b\end{array}\right|\ =\ \left|\begin{array}{cc}\rm a &\rm b\\ \rm q & \rm p\end{array}\right|\ =\ ap-bq = 1\quad\ {\bf QED}$$ 
A: Consider your first equation in $\mathbb{Z}_q$, you get that $a = p^{-1}$, and that is unique (modulo $q$). From the second one it is $-d = p^{-1}$, so $a \equiv -d \pmod q$, and similarly $b \equiv -c \pmod p$. Writing $d = -a + r q$ and $c = -b + s p$, and substituting into the second equation:
$$
\begin{align*}
(b + s p) q - (a + r q) p &= 1 \\
-b q + a p                &= 1 - s p q + r p q \\
1                         &= 1 + p q (r - s)  \\
0                         &= p q (r - s) \\
r                         &= s
\end{align*}
$$
So $d = - a + r q$, $c = - b + r p$.
Thus, $a c - b d = a (- b + r p) - b (- a + r q) = (a p - b q) r = r$.
A: In general (even in other Euclidean rings) the Bézout coefficients of $p,q$ are unique only modulo $\def\lcm{\operatorname{lcm}}\lcm(p,q)/p=q/\gcd(p,q)$ respectively modulo $\lcm(p,q)/q=p/\gcd(p,q)$, since
$$
  sa+tb=s'p+t'q\iff (s-s')p+(t-t')q=0
$$
and minimal nonzero solutions (in terms of divisibility) $x,y$ to $xa+yb=0$ are $x=\lcm(p,q)/p,y=-\lcm(p,q)/q$. In case $\gcd(p,q)=1$ this simplifies to $x=q,y=-p$.
Assume $p,q>0$.
Now if $$s=a,\quad t=-b$$ give a solution of $sp+tq=1$ with $s$ minimal subject to $s>0$, then $$s=a-q,\quad t=-b+p$$ give another solution, with $s$ maximal subject to $s\leq0$.
Note that $ap-bq=1$ implies $b\geq0$, and $(a-q)p+(p-b)q=1$ with $a-q\leq0$ implies $p-b>0$, so $t=-b$ is also maximal subject to $t\leq0$ and $t=p-b$ is minimal subject to $t>0$.
This means we've also got our other minimal pair, namely $c=p-b$ and $d=q-a$. But then $ac-bd=a(p-b)-b(q-a)=ap-bq=1$.
