5
$\begingroup$

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.

$\endgroup$
0

3 Answers 3

5
$\begingroup$

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 OP\ case}\ \ \quad &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}\quad\ \ \ &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 Proof}}\qquad\ \ &a_1(b_1,b_2) \overset{\rm\color{#0a0}{DL}}= (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}}= b_1 (a_1,a_2)\\[.6em] {\bf Example}\ \ \ \ &\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 is simply that

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

The $1$ line proof works for many other algebraic systems enjoying distributivity, e.g. we can read $\:\!(x,y)\:\!$ as an ideal instead of a gcd and the above 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$$

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

The lemma can be viewed 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 terms of "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 will be clarified when one studies the pertinent algebraic structures: $ $ ideals and modules (viz. order ideals and denominator ideals), or annihilator ideals (in PIDs).

$\endgroup$
1
  • $\begingroup$ To those wondering why this answer got so many downvotes please refer to this meta question posted by the OP. $\endgroup$ May 15 at 9:24
2
$\begingroup$

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

$\endgroup$
0
2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Apr 26 at 5:32
  • $\begingroup$ There were a number of obvious typos. Hopefully fixed now. $\endgroup$ Apr 26 at 11:43
  • $\begingroup$ 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. $\endgroup$ Apr 26 at 18:39

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.