Saturday, February 12, 2011

The product a*b is even if....

Prove that the product of the positive integers a and b is even if and only if
there exist positive integers c and d such that

a^2 + b^2 + c^2 = d^2

3 comments:

  1. Lemma: an integer is the difference of two squares iff it is not congruent to 2 modulo 4.

    Proof: (=>) Modulo 4, the only squares are 0 and 1. The difference of two such numbers can never be 2.

    (<=) If a number is not congruent to 2 modulo 4 then it is either odd or a multiple of 4. Every odd integer can be written in the form 2k+1 for some integer k, which is equal to (k+1)^2 - k^2. Every multiple of 4 can be written as 4(k+1) for some integer k, which is equal to (k+2)^2 - k^2.


    Proof of original claim: a*b is even iff at least one of a and b is even, iff a^2 + b^2 is not congruent to 2 modulo 4, iff (by the lemma) a^2 + b^2 is the difference of two squares.

    ReplyDelete
  2. PS. Why do you say "positive integers"? It works for any integers, doesn't it?

    ReplyDelete
  3. Yes. You're right. It works if both a and b are negative integers.

    ReplyDelete