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.

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

ReplyDeleteProof: (=>) 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.

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

ReplyDeleteYes. You're right. It works if both a and b are negative integers.

ReplyDelete