Denominators of fractions are closed under gcd (vector gcds)

Question

Let $N$ be odd and $N = a^2 + b^2 = c^2 + d^2$, where $a, b, c, d \in \mathbb{N}$ and WLOG let $a, c$ be odd, $b, d$ be even, $a > c$, and $b < d$. Prove that $\frac{a-c}{k}=\frac{d+b}{n}$.

I first began the proof my showing that $k$ and $n$ are positive integers.

Let $k= \gcd(a -c, d-b)$ and $n= \gcd(a + c, d + b)$. If $a$ and $c$ are both odd, then $a\pm c$ is even. Similarly, if $d$ and $b$ are both even, then $b\pm d$ is also even. Thus, $k$ and $n$ are also both even.

Now I wish to show that $\frac{a-c}{k}=\frac{d+b}{n}$.

I first tried to use the fact that $N = a^2 + b^2 = c^2 + d^2$. $$ \begin{align*} a^2 + b^2 &= c^2 + d^2\\ a^2 -c^2 &= d^2-b^2\\ (a+c)(a-c)&=(d+b)(d-b)\\ \end{align*} $$

This seems like I'm getting close but I can't quite see how to finish it. Any hints are appreciated.

Answer 1

This is an instance of the basic fact that possible denominators for a fraction are closed under gcd, i.e. $ $ if a fraction $\,q\,$ is writable with denom's $\,b_1$ and $\,b_2$ then it is writable with denom $\,\gcd(b_1,b_2).\,$ It's a $1$ line $\rm\color{#90f}{Proof}$ from your $\color{#c00}{\rm equality},\:\!$ via $\rm\color{#0a0}{DL}$ = gcd Distributive Law $\,x(y,z)\! =\! (xy,xz)$

$\!\begin{align} {\bf Your\ case}\!:\,\ \ &\ 0 < q\, =\, {\small \color{#c00}{\frac{a\!-\!c}{d\!+\!b}\ =\ \dfrac{d\!-\!b}{a\!+\!c}}} \Rightarrow\ q ={\small \dfrac{(a\!-\!c,d\!-\!b)}{(d\!+\!b,a\!+\!c)} = \frac{k}n,}\ \ \ \text{follows by}\\[.5em] {\bf Lemma}\!:\qquad &\ 0\,<\, q\, =\, \color{#c00}{\dfrac{a_1}{b_1}\ =\ \dfrac{a_2}{b_2}}\ \ \Rightarrow\ q = \dfrac{(a_1,a_2)}{(b_1,b_2)},\ \ \ \ (x,y) :=\gcd(x,y)\\[.5em] {\color{#90f}{\bf Pf\!\!:}}\,\ \ \color{#e80}{a_1}(b_1,b_2) &\!\overset{\rm\color{#0a0}{DL_{\phantom{'}\!}}}= (a_1 b_1, \color{#c00}{a_1 b_2}) = (a_1 b_1,\color{#c00}{a_2 b_1}) \overset{\rm\color{#0a0}{DL_{\phantom{'}\!}}}= \color{#e80}{b_1} (a_1,a_2)\,\Rightarrow\, \color{#e80}{\dfrac{a_1}{b_1}}=\dfrac{(a_1,a_2)}{(b_1,b_2)}\\[.6em] {\bf Example}\!:\qquad\!\!\! &\ \qquad\ q = \dfrac{133}{247} = \dfrac{119}{221}\, \Rightarrow\ q = \dfrac{(133,119)}{(247,221)} = \dfrac{7}{13}\end{align}\qquad$

---

Remark $ $ Though - as usual - we can also give a proof of the Lemma via prime factorizations, the above proof has the advantage that it generalizes more widely since it requires much less - only a distributive law. Namely, if we eliminate use of fractions then the Lemma amounts to

$$a_1b_2 = b_1 a_2\ \Rightarrow\ a_1(b_1,b_2) = b_1(a_1,a_2)\qquad$$

This inference proof works for many other algebraic systems enjoying distributivity, e.g. we can read $\:\!(x,y)\:\!$ as an ideal instead of a gcd and it remains true. More simply, we can read $\:\!(x,y)\:\!$ as $\,x+y\,$ and then the proof shows that the mediant has the same value as two equal fractions, i.e.

$$q\, =\, \color{c00}{\dfrac{a_1}{b_1}\ =\ \dfrac{a_2}{b_2}}\ \Rightarrow\ q = \dfrac{a_1+a_2}{b_1+b_2}\qquad\qquad\qquad\qquad\!\!$$

and similarly for the (multi-)linear form $\,(x,y):= jx+ky$.

The lemma is viewable as a Euclidean descent on equivalent fractions - which often proves handy, e.g. it can be used to efficiently implement the extended Euclidean algorithm in (modular) fraction form, e.g. see here and here.

As explained here, we can also view the Lemma in "order" language, since the least denom of a fraction is its order in $\,\Bbb Q/\Bbb Z.\,$ Then said denominator descent is: $ $ if $\,m,n\,$ are denom's of $\,q\,$ then so too is their gcd $\:\!(n,m),\:\!$ which is an additive analog of the following well-known theorem $${\rm if}\ \ q^m\! = 1 = q^n\ \ {\rm then}\ \ q^{(m,n)}=1,\ \ {\rm by}\ \ {\rm ord}(q)\mid m,n\,\Rightarrow\, {\rm ord}(q)\mid (m,n)\qquad$$

These ideas are abstracted when studying pertinent algebraic structures: $ $ ideals and modules (viz. order ideals and denominator ideals), or annihilator ideals (in PIDs).

Answer 2

We have that

$$k = \gcd(a - c, d - b) \; \; \to \; \; a - c = ke, \; d - b = kf, \; \gcd(e, f) = 1 \tag{1}\label{eq1A}$$

$$n = \gcd(a + c, d + b) \; \; \to \; \; a + c = ng, \; d + b = nh, \; \gcd(g, h) = 1 \tag{2}\label{eq2A}$$

Using \eqref{eq1A} and \eqref{eq2A} with your factorization gives

$$\begin{equation}\begin{aligned} (a + c)(a - c) & = (d + b)(d - b) \\ (ng)(ke) & = (nh)(kf) \\ ge & = hf \end{aligned}\end{equation}\tag{3}\label{eq3A}$$

With \eqref{eq1A} giving $\gcd(e,f) = 1$, then \eqref{eq3A} shows that

$$f \mid g \; \; \to \; \; g = sf, \; s \ge 1 \tag{4}\label{eq4A}$$

Similarly, since $\gcd(g,h) = 1$ from \eqref{eq2A}, then

$$h \mid e \; \to \; e = th, \; t \ge 1 \tag{5}\label{eq5A}$$

Thus, \eqref{eq3A} becomes

$$(sf)(th) = hf \; \; \to \; \; st = 1 \; \; \to \; \; s = t = 1 \tag{6}\label{eq6A}$$

Therefore, using \eqref{eq1A}, \eqref{eq2A}, \eqref{eq5A} and \eqref{eq6A}, we have that

$$e = h \; \; \to \; \; \frac{a - c}{k} = \frac{d + b}{n} \tag{7}\label{eq7A}$$

Answer 3

It seems to me that those sums and differences are there to muddy the waters.

Let's write $A=a+c$, $C=A-c$, $D=d+b$ and $B=d-b$. As you observed, the given equation $a^2+b^2=c^2+d^2$ is equivalent to $$AC=DB.\qquad(*)$$ And the claim is that $(*)$ implies $$\frac C{\gcd(B,C)}=\frac{D}{\gcd(A,D)}.\qquad(\dagger)$$

It is simple to do this one prime factor at a time. So let $p$ be a prime number, and assume that in the prime factorizations we have $p^n$ appearing in $A$, $p^m$ appearing in $C$, $p^r$ in $D$ and $p^s$ in $B$. By uniqueness of factorization $(*)$ implies that $$n+m=r+s.\qquad(**)$$ The claim $(\dagger)$ is then translated to $$ m-\min\{m,s\}=r-\min\{r,n\}.\qquad(\dagger\dagger) $$ This is now easy to see. From $(**)$ it follows that $m-s=r-n$. Hence $\min\{m,s\}=s$ if and only if $\min\{r,n\}=m$ in which case the claim is exactly $m-s=r-n$. In the complementary case $\min\{m,s\}=m$ and $\min\{r,n\}=r$ the claim $(\dagger\dagger)$ reads $0=0$.