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