Tuesday, February 14, 2012

(The difference of two squares) mod 4

Argument
: Let a , b any integer, and z = a^2 - b^2
Then (z mod 4) can never be 2 for any value of a and b.

Proof
Lemma 1.  (A perfect square mod 4 ) is always either 0 or 1.
Proof for lemma 1.
Let k = any number.
Then 2k is an ever number, and (2k+1) is an odd number.
Square of 2k = 4k^2 ==>  (4k^2) mod 4 = 0
Square of (2k+1) = (4k^2 + 4k + 1) ==> (4k^2 + 4k + 1) mod 4 = 1

From lemma 1, we can conclude that (a^2 - b^2) can one of following four cases
1) even^2 - even^2
2) even^2 - odd^2
3) odd^2 - even^2
4) odd^2 - odd^2
where even = an even number and odd = an odd number.

Taking mod 4 for each case,
1) (0 - 0) mod 4 => 0
2) (0 - 1) mod 4 => 3
3) (1 - 0) mod 4 => 1
4) (1 - 1) mod 4 => 0

Therefore, for all possible cases, taking mod 4 of difference of squares always result in 0,1, or 3, but never 2.

1 comment: