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$).

  • $\begingroup$ Thanks, would try to find where such simple condition ($ps - qr = 1$) is imposed. Also, this would help in understanding higher order equalities also. $\endgroup$ – jiten Dec 9 '17 at 8:39
  • $\begingroup$ @jiten : The simple condition is imposed as "$ps-qr = \pm 1$". It has the added advantage of forcing $\gcd(p,q) = \gcd(r,s) = 1$. $\endgroup$ – Eric Towers Dec 9 '17 at 19:49
  • $\begingroup$ If I am not wrong, you are having circular reasoning. May be my answer asks, where else such condition, i.e. $ps - qr = \pm 1$, is generated. If possible, specify literature or online sources for that. $\endgroup$ – jiten Dec 10 '17 at 8:09
  • $\begingroup$ What does the Extended Euclidean algorithm tell you about the gcd of $p$ and $q$ if there exist $r$ and $s$ giving $ps - qr = \pm 1$? This is not a property from the literature. This is something all students working with gcds are expected to learn so they can recognize it immediately. $\endgroup$ – Eric Towers Dec 10 '17 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.