1

I am having some trouble starting off this proof. I am not sure if I need to prove by the contrapositive or if it is a direct proof.

Prove: If $x, y,$ and $z$ are natural numbers such that $x^2+y^2=z^2$ and $gcd(x,y,z)=1$*, then exactly one of the natural numbers $x$ and $y$ is odd.

*$gcd$ is the greatest common divisor

I got that the contrapositive was: If it is not the case that exactly one of $x,y$ are odd, then $x^2+y^2\neq z^2$ or $gcd(x,y,z)=1$. Still not sure if I need to use the contrapositive in order to prove this

Thanks for any help!!

user111702
  • 109
  • 1
    "Exactly one" $=$ "at least one" $\land$ "not both" $=$ (first $\land$ $\lnot$ second) $\lor$ ($\lnot$ first $\land$ second). – xavierm02 Dec 07 '13 at 00:29
  • So it would be the second one in that case? – user111702 Dec 07 '13 at 00:31
  • What are $r$ and $s$ for you? – xavierm02 Dec 07 '13 at 00:33
  • $r$ would be that x is odd and $s$ would be that y is odd – user111702 Dec 07 '13 at 00:37
  • That wouldn't work. You need more properties than that. $\forall x,y,z \in \Bbb N, x^2+y^2=z^2\land gcd(x,y,z)=1\implies (2\mid x \land 2\not\mid y)\lor (2\not\mid x \land 2 \mid y)$ – xavierm02 Dec 07 '13 at 00:58
  • Let me see if I understand.

    $p\Rightarrow x^2+y^2=z^2$

    $q\Rightarrow gcd(x,y,z)$

    $r\Rightarrow x$ is odd

    $s \Rightarrow y$ is odd

    $$p\land q \rightarrow (r \land \lnot s) \lor (\lnot r \land s)$$

     – user111702 Dec 07 '13 at 01:09
  • @user111702 Assuming you mean $q$ is the statement "gcd($x,y,z$) $=1$", then yes, that logical statement is the correct formalisation. – Josh Dec 07 '13 at 02:33
  • So then the contrapositive would be: $$\lnot ((r\land \lnot s) \lor (\lnot r \land s))\rightarrow \lnot(p\land q)$$ $$(\lnot r\lor s) \land ( r \lor \lnot s)\rightarrow \lnot p\lor \lnot q$$ right? – user111702 Dec 07 '13 at 02:45
  • Yes that is correct. And you can then expand and simplify the antecedent (LHS) to get $(r\wedge s)\vee(\neg r \wedge \neg s)$. But is there any particular reason you are thinking about this so formally? The contrapositive is just "if it is not the case that exactly one of $x,y$ are odd, then either $x^2+y^2\neq z^2$, or $\gcd(x,y,z)\neq 1$". And it should be obvious that "it is not the case that exactly one of $x,y$ are odd" is the same as saying "either $x,y$ are both odd, or both even". – Josh Dec 07 '13 at 04:02

1 Answers1

3

Yes, using the contrapositive is probably the easiest way to do this. So start with the assumption that it is not true that exactly one of $x$ or $y$ are odd. Then either:

  1. Both $x$ and $y$ are even, or
  2. Both $x$ and $y$ are odd.

So you have to consider each of these cases separately.

Case 1. (This is the slightly easier case). Assume $x,y$ are both even. We want to show that one of the statements

$$x^2+y^2=z^2 \quad (1)$$

or

$$\gcd(x,y,z)=1 \quad (2)$$

is false.

The usual way to do this is to assume that one of them is true, and show that the other one has to be false. Let us suppose that $x^2 + y^2$ indeed equals $z^2$. But $x$ and $y$ are even, so what does that tell you about $z^2 = x^2 + y^2$? Then, what does that tell you about $z$ itself? Hence what can you say about $\gcd(x,y,z)$?

(At this point it might be helpful to step back and have a review of the logical flow of our entire argument so far.)

Case 2. Assume $x,y$ are both odd. The logic in this part of the proof turns out to be slightly different from Case 1, as you will see. (Hint: you can directly show that one of the statements (1) or (2) is false, without having to assume the other.) Try beginning in the same way as you did for Case 1. Now what does this tell you about $z^2$? But what about $x^2+y^2$? Are the two expressions compatible? (Full solution hidden below:)

Since $x$ and $y$ are both odd, so are $x^2$ and $y^2$, thus $z^2 = x^2 + y^2$ is even. (Odd + odd = even always, convince yourself of this.) It is easy to see that any even square number $z^2$ has to be divisible by $4$. On the other hand, since \begin{align} x &= 2m+1 \\ y &= 2n+1 \end{align} for some integers $m, n$ we know that $x^2+y^2 = 4k + 2$ for some integer $k$, but this is not divisible by $4$. Thus we cannot have $x^2+y^2 = z^2$, i.e. the square of two odd numbers is never a square.

Incidentally, this problem is the first step in finding all the primitive Pythagorean triples.

Josh
  • 2,539
  • By the definition of an even number we get that there exist integers $i$ and $j$ such that: $$x=2i$$ $$y=2j$$ Suppose $x^2+y^2=z^2$, by substitution and algebra we get that: $$(2i)^2+(2j)^2=z^2$$ $$4i^2+4j^2=z^2$$ $$4(i^2+j^2 )=z^2$$ Since integers are closed by addition and multiplication there exists an integer $k$ such that: $$4k=z^2$$ $$2\sqrt{k}=z$$ From this we get that the $gcd(x,y,z)=2.$ – user111702 Dec 07 '13 at 22:15
  • Very good! Subtle but important point: for that last bit, you have that $$z^2=4k$$ for some integer $k$, and in fact $k$ must be square (otherwise $2\sqrt{k}=z$ wouldn't be an integer). – Josh Dec 08 '13 at 00:55
  • Case 2: Both $x$ and $y$ are odd. By the definition of an even number we get that there exist integers $i$ and $j$ such that: $$x=2i+1$$ $$y=2j+1$$ Suppose $x^2+y^2=z^2$, by substitution and algebra we get that: $$(2i+1)^2+(2j+1)^2=z^2$$ $$4i^2+4i+2+4j^2+4j+2=z^2$$ $$4i^2+4i+4j^2+4j+4=z^2$$ $$4(i^2+i+j^2+j+1)=z^2$$ Since integers are closed by addition and multiplication there exists an integer $k$ such that: $$4k^2=z^2$$ $$2k=z$$ But this time I got that the $$gcd(x,y,z)=1$$ since $x$ and $y$ are odd – user111702 Dec 09 '13 at 03:41
  • Sorry for the long hiatus, was away from internet. You made a mistake in the algebra for $(2i+1)^2$ and $(2j+1)^2$, you should find that $x^2+y^2=4k+2$ for some integer $k$. But now trying to find a contradiction using the gcd won't get you anywhere, as you have observed. Here's a clue: you have found that $z^2$ must be even. It is not hard to see that any even square number must be divisible by 4. (Can you see why?) Now compare the expressions for $z^2$ and $x^2+y^2$ and thus obtain a contradiction. – Josh Dec 18 '13 at 15:30