If $p,q,r,s$ are integers s.t. $ps - qr = \pm 1$, and $a,b,a{'}, b{'}$ are integers such that : $a{'} = pa + qb, b{'} = ra + sb$. Prove that $(a,b) = (a{'}, b{'})$.
From the equality: $ps - qr = \pm 1$, it can be seen that all four pairs ($(p,q)=(p,r)=(s,q)=(s,r)=1$). Although, need only the following set of two pairs being co-prime: (a) $p,q$, (b) $r,s$; for the problem at hand.
In order to prove, first attempt that $\gcd(a{'}, b{'}) \mid a,b$. This will prove that $\gcd(a{'}, b{'}) \lt a,b$.
Case (i) Prove $\gcd(a{'}, b{'}) \mid a$:
For this need cancel the term with $b$, which can be accomplished by multiplying first equality by $s$ , and second by $q$.
\begin{align*} a' &= pa + qb &\implies sa' &= psa + qsb \\ b' &= ra + sb &\implies qb' &= qra + qsb \\ \end{align*} Subtracting these gives $sa' - qb' = \pm a$. So $\gcd(a',b')$ divides $a$.
Case (ii) Prove $\gcd(a{'}, b{'}) \mid b$:
For this need cancel the term with $a$, which can be accomplished by multiplying first equality by $r$ , and second by $p$.
\begin{align*} a' &= pa + qb &\implies ra' &= pra + qrb \\ b' &= ra + sb &\implies pb' &= pra + psb \\ \end{align*} Subtracting these gives $ra' - pb' = \mp b$. So $\gcd(a',b')$ divides $b$.
Next, need prove the reverse, i.e. $\gcd(a, b) \mid a{'},b{'}$.
Here, it is obvious that $\gcd(a,b) \mid a^{'}$ for integer multiplier as $p,q$ for $a,b$ respectively. Similarly, it is obvious that $\gcd(a,b) \mid b^{'}$ for a different set of integer multiplier as $r,s$ for $a,b$ respectively.
Hence, proved that $\gcd(a,b) = \gcd(a{'}, b{'})$.
But, is there any physical significance attached to the two set of equalitiess;
(i) $ps - qr = \pm 1$; (ii) $a{'} = pa + qb, b{'} = ra + sb$.
It is obvious that in (ii) the two equalities are multiplied on r.h.s. by the co-prime values. Otherwise, the solution finding would not have been possible. I mean that had there been not co-prime integer multipliers, as follows, then not possible to get solution:
(ii) $a{'} = pa + rb, b{'} = qa + sb$.
Is there a special name associated to such set of equalities? If yes, then it would be very easy to dig out how these set of equalities are generated, and in what context.
I hope by knowing how the underlying set of equalities are generated, will give higher level of awareness of the issues involved.
You have $$ \begin{pmatrix} a' \\ b'\end{pmatrix} = \begin{pmatrix} p & q \\ r & s \end{pmatrix} \begin{pmatrix} a \\ b \end{pmatrix} $$ with the condition $$ \left| \det \begin{pmatrix} p & q \\ r & s \end{pmatrix} \right| = |ps-qr| = 1 \text{.} $$
With some work you can convince yourself that the condition on the determinant makes the linear map a bijection (in this setting, from and to $\mathbb{Z}^2$).