Denominators of fractions are closed under gcd (vector gcds)

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.

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

• To those wondering why this answer got so many downvotes please refer to this meta question posted by the OP. Commented May 15, 2022 at 9:24

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{aligned} (a + c)(a - c) & = (d + b)(d - b) \\ (ng)(ke) & = (nh)(kf) \\ ge & = hf \end{aligned}\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}$$

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

• The endgame reflects the analogy between the $\gcd$, $\mathrm{lcm}$ and $\min$, $\max$. The product of the former pair being equal to the actual product, and the sum of the latter pair being equal to the actual sum. Commented Apr 26, 2022 at 5:32
• There were a number of obvious typos. Hopefully fixed now. Commented Apr 26, 2022 at 11:43
• In reply to your prior comment, I reorganized and expanded my answer to explain some advantages of using distributivity, e.g. it yields a proof that also works for ideals, which can't be done as above. Commented Apr 26, 2022 at 18:39