# Finding significance of equalities involved in proving $\gcd(a,b) = \gcd(a{'}, b{'})$.

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$).
• Thanks, would try to find where such simple condition ($ps - qr = 1$) is imposed. Also, this would help in understanding higher order equalities also. – jiten Dec 9 '17 at 8:39
• @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$. – Eric Towers Dec 9 '17 at 19:49
• 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. – jiten Dec 10 '17 at 8:09
• 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. – Eric Towers Dec 10 '17 at 16:48