2
$\begingroup$

Suppose $\frac{p}{q}$ and and $\frac{r}{s}$ are rationals in lowest terms (so $\gcd (p,q) = \gcd(r,s) = 1$) and $\frac{p^2}{q^2} + \frac{r^2}{s^2} = 1$; i.e. $p^2s^2+r^2q^2=q^2s^2$. Then exactly one of $p$ and $r$ is even, and $q$ and $s$ (and one of $p,r$) are odd.

Mainly, how do we find a contradiction when both numerators ($p$ and $r$) are odd and both denominators ($q$ and $s$) are even?


This section deals with all the other cases besides the one described in the previous sentence.

Suppose $p,r$ are both even. Then $qs$ must be even based on $(ps)^2+(rq)^2=(qs)^2$. But then $\gcd(p,q) \geq 2$ or $\gcd(r,s) \geq 2$. Therefore, $p$ and $r$ cannot both be even.

Suppose both $p$ and $r$ are odd. If both $q$ and $s$ are odd, then the left side of $(ps)^2+(rq)^2=(qs)^2$ will be even, and the right side will be odd. If exactly one of $q,s$ is even, then the left side of $(ps)^2+(rq)^2=(qs)^2$ will be odd, and the right side will be even.

The last case is when exactly one of $p,r$ is even. Since these fractions are in lowest terms, the denominator dividing the even numerator (dividing $p$ or $r$) must be odd. Suppose the other denominator (dividing the odd numerator) is even, so one of our two rationals $\frac{p}{q}$ and $\frac{r}{s}$ is $\frac{even}{odd}$, and the other is $\frac{odd}{even}$. But then the left side of $(ps)^2+(rq)^2=(qs)^2$ will be odd (it has an $even \cdot even$ term summed with an $odd \cdot odd$ term), and the right side will be even. So in this case, both $q$ and $s$ must be odd, as desired.


This question relates to a proof in D. R. Woodall, "Distances realized by sets covering the plane" (https://www.sciencedirect.com/science/article/pii/0097316573900204). This proposition helps prove that you can color $\mathbb{Q}^2$ with two colors such that no two points distance $1$ apart have the same color (the "chromatic number of the rational plane" is $2$). The chromatic number of $\mathbb{R}^2$, on the other hand, is $5,6$, or $7$.

$\endgroup$
2
$\begingroup$

For a complete proof, I'll do all cases . . .

Clearing denominators, we get $$ p^2s^2+r^2q^2=q^2s^2\qquad(*) $$ First suppose exactly one of $q,s$ is even.

If $q$ is even and $s$ is odd, then by rewriting $(*)$ as $$ p^2s^2=q^2(s^2-r^2) $$ it follows that $p^2s^2$ is even, so $p^2$ must be even, hence $p$ is even, contrary to $\gcd(p,q)=1$.

If $s$ is even and $q$ is odd, then by rewriting $(*)$ as $$ r^2q^2=s^2(q^2-p^2) $$ it follows that $r^2q^2$ is even, so $r^2$ must be even, hence $r$ is even, contrary to $\gcd(r,s)=1$.

Hence it can't be the case that exactly one of $q,s$ is even.

Next suppose $q,s$ are both even.

Then since $\gcd(p,q)=1$, it follows that $p$ is odd, and since $\gcd(r,s)=1$, it follows that $r$ is odd.

Thus $p,r$ are both odd.

Let $d=\gcd(q,s)$.

Since $q,s$ are both even, $d$ is even.

Since $d=\gcd(q,s)$ we can write $$ \left\lbrace \begin{align*} q&=dq_1\\[4pt] s&=ds_1\\[4pt] \end{align*} \right. $$ where $q_1,s_1$ are integers such that $\gcd(q_1,s_1)=1$.

Rewriting $(*)$ as $$ p^2s_1^2=q_1^2(s^2-r^2) $$ we get $q_1^2{\,\mid\,}(p^2s_1^2)$, but $p,q_1$ are relatively prime since $\gcd(p,q)=1$, hence we must have $q_1^2{\,\mid\,}s_1^2$.

Similarly, by rewriting $(*)$ as $$ r^2q_1^2=s_1^2(q^2-p^2) $$ we get $s_1^2{\,\mid\,}(r^2q_1^2)$, but $r,s_1$ are relatively prime since $\gcd(r,s)=1$, hence we must have $s_1^2{\,\mid\,}q_1^2$.

Since we have both $q_1^2{\,\mid\,}s_1^2$ and $s_1^2{\,\mid\,}q_1^2$, it follows that $q_1^2=s_1^2$, but then since $\gcd(q_1,s_1)=1$, it follows that $q_1^2$ and $p_1^2$ are both equal to $1$.

Then from $$ \left\lbrace \begin{align*} q&=dq_1\\[4pt] s&=ds_1\\[4pt] \end{align*} \right. $$ we get $q^2=d^2$ and $s^2=d^2$, so $(*)$ becomes $$ p^2d^2+r^2d^2=d^4 $$ or equivalently $$ p^2+r^2=d^2 $$ Since $d$ is even, the $\text{RHS}$ of the above equation is a multiple of $4$.

But since $p,r$ are odd, and odd squares are congruent to $1$ mod $4$, the $\text{LHS}$ of the above equation is congruent to $2$ mod $4$, contradiction.

Hence it can't be the case that $q,s$ are both even, and since we know that it can't be the case that exactly one of $q,s$ is even, it follows that $q,s$ are both odd.

Thus we have $q^2\equiv 1\;(\text{mod}\;2)$ and $s^2\equiv 1\;(\text{mod}\;2)$,$\;$so \begin{align*} & p^2s^2+r^2q^2=q^2s^2\\[4pt] \implies\;& p^2s^2+r^2q^2\equiv q^2s^2\;(\text{mod}\;2)\\[4pt] \implies\;& p^2{\,\cdot\,}1+r^2{\,\cdot\,}1\equiv 1{\,\cdot\,}1\;(\text{mod}\;2)\\[4pt] \implies\;& p^2+r^2\equiv 1\;(\text{mod}\;2)\\[4pt] \end{align*} hence one of $p,r$ is even and the other is odd.

This completes the proof.

$\endgroup$
  • $\begingroup$ How do you prove $p^2s^2+r^2q^2 \equiv q^2s^2 \mod 2$ implies $p^2 + r^2 \equiv 1 \mod 2$? My understanding is that you implicitly wrote $[p^2][1]+[r^2][1] = [1][1]$, so $[p^2] + [r^2] = [1]$ in $\mathbb{Z}_2$ modular arithmetic. $\endgroup$ – jskattt797 Jul 10 '20 at 5:40
  • 1
    $\begingroup$ @jskattt797: Just substitute $q^2=1$ and $s^2=1$ in the congruence $p^2s^2+r^2q^2\equiv q^2s^2\;(\text{mod}\;2)$. I'll edit that in to make it more explicit. $\endgroup$ – quasi Jul 10 '20 at 5:55
3
$\begingroup$

I will be using the following fact

$$k^2 \equiv {0,1\mod 4} $$

For any natural number $k$ ( this is easily seen using binomial theorem and taking cases for odd and even)

Now, you have

$$p^2s^2 + r^2q^2 = q^2s^2$$

Now, from the above, we can already see that we only have that either all the above are even, or that exactly one term on the LHS is even and the other odd ( if both are odd then it would add to form remainder 2, which would not be a perfect square)

But if all are even, then the gcd would be 2. Because they are co-prime, we have to have that exactly one of LHS is odd and the other even.

Can you continue from here?

EDIT

For any natural number $n$, it can be written as either $2k$ or $2k+1$

$$n^2 = \begin{cases}4k^2 \\ 4k^2 + 4k + 1\end{cases}$$

So any square number would be either of the form $4k$ or $4k+1$

When I mentioned remainder 2, I meant modulo 4

$\endgroup$
  • $\begingroup$ How does the $k^2$ congruence fact follow from the binomial theorem? Another proof is $[k^2] \in \{[0^2], [1^2], [2^2], [3^2] \} = \{[0], [1] \}$ in $\mathbb{Z}_4$ modular arithmetic. I am also confused about "if both are odd then they would add to form remainder 2." Remainder 2 mod 4? I get $2i + 1 + 2j + 1 = 2(i + j) + 2$. If $i + j$ is even, then the left hand side is indeed $\in [2]$. But what if $i + j$ is odd? $\endgroup$ – jskattt797 Jul 10 '20 at 4:35
  • $\begingroup$ What do you mean by "But if all are even, then the gcd would be 2. Because they are coprime..."? What are you referring to with "all", "the gcd" (of what), and "they"? $\endgroup$ – jskattt797 Jul 10 '20 at 4:54
1
$\begingroup$

Clearing denominators gives

$$ (ps)^2 + (qr)^2 = (qs)^2. $$

Suppose $q,s$ are both even. Write $q=2^am$, $s=2^bn$, where $a \ge 1$, $b \ge 1$, and $m,n$ are both odd. Assume, without loss of generality, that $a \le b$.

For positive integer $N$, let ${\nu}_2\,(N)$ is the highest power of $2$ dividing $N$. Thus, ${\nu}_2\,\big((qs)^2\big)=2(a+b)$.

Note that $q,s$ both even implies $p,r$ must both be odd. Thus, ${\mu}_2\,\big((ps)^2\big)=2a$ and ${\nu}_2\,\big((qr)^2\big)=2b$.

If $a<b$, then ${\mu}_2\,\big((ps)^2+(qr)^2\big)=2a<2(a+b)$.

If $a=b$, then $(ps)^2+(qr)^2=2^{2a}\big((mr)^2+(np)^2\big)$. Since $mr,np$ are both odd, $(mr)^2+(np)^2 \equiv 2\pmod{4}$, and so ${\mu}_2\,\big((ps)^2+(qr)^2\big)=2a+1<2(a+b)$.

Thus, at most one of $q,s$ is even.

Without loss of generality, suppose $q$ is even and $s$ is odd. Then $p$ must be odd, and so $ps$ is odd. But then $(ps)^2+(qr)^2$ is odd while $(qs)^2$ is even.

We have shown that $qs$ is odd.

Since $x^2 \equiv x\pmod{2}$, we have

$$ 1 \equiv (qs)^2 = (ps)^2 + (qr)^2 \equiv ps+qr \equiv p+r \pmod{2}. $$

This implies $p,r$ are of opposite parity. $\blacksquare$

$\endgroup$
  • $\begingroup$ Assuming the $\mu_2$ has the same meaning as $\nu_2$, can you provide more detail why $\nu_2((ps)^2+(qr)^2) = 2a$? I see that we can factor out a $2^{2a}$ from the expression. But why can't a higher power of $2$ divide $(ps)^2+(qr)^2$ when $a < b$? $\endgroup$ – jskattt797 Jul 10 '20 at 17:48
  • $\begingroup$ Similarly, when $a=b$, we have $2^{2a}((mr)^2+(np)^2)$, and $(mr)^2+(np)^2 = odd + odd = even$, so we can pull out a $2^{2a + 1}$. But why can't we pull out a $2^{2a + 2}$? $\endgroup$ – jskattt797 Jul 10 '20 at 17:52
  • $\begingroup$ The only difference between a $\mu$ and a $\nu$ is a single letter that are not only next to each other in the English alphabet but also on the standard keyboard. Thanks for spotting that. I have now corrected that slip. $\endgroup$ – AT1089 Jul 10 '20 at 19:41
  • 1
    $\begingroup$ Suppose $a<b$. Then $(ps)^2+(qr)^2=2^{2a}(mr)^2+2^{2b}(np)^2=2^{2a}\big((mr)^2+2^{2b-2a}(np)^2\big)$. Since $2b-2a>0$, and $p,r,m,n$ are all odd, it follows that $(mr)^2+2^{2b-2a}(np)^2$ is odd. Thus, ${\nu}_2$ equals $2a$ in this case. $\endgroup$ – AT1089 Jul 10 '20 at 19:45
  • 1
    $\begingroup$ Suppose $a=b$. Then $(ps)^2+(qr)^2=2^{2a}\big((mr)^2+(np)^2\big)$, and $(mr)^2+(np)^2 \equiv 1+1 \equiv 2\pmod{4}$. Thus, ${\nu}_2$ equals $2a+1$ in this case. $\endgroup$ – AT1089 Jul 10 '20 at 19:47

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.