Answer to Question #136832 in Discrete Mathematics for Promise Omiponle

Question

(19) Show that if n is an integer then n^2 ≡ 0 or 1 (mod 4).
(20) Use the result of Exercise (19) to show that if m is a positive integer that can be written in the form m= 4k+ 3 (where k is a nonnegative integer), then m is not the sum of the squares of two integers.

Answer 1

(19) Ans : Any integer $n$ under( mod 4 ) is

$n\equiv$0 (mod 4) or $n\equiv$ 1 (mod 4 ) or $n\equiv$ 2 (mod 4) or $n\equiv$ 3 (mod 4)

Again we know that from property of congruences that

If $a\equiv b$ (mod n) , then $a^k\equiv b^k$ (mod n) for any positive integer $k$ .

Therefore , $n^2\equiv 0^2$ (mod 4) $\implies$ $n^2\equiv 0$ (mod 4),

$n^2\equiv 1^2$ (mod 4) $\implies n^2\equiv 1$ (mod 4),

$n^2\equiv2^2$ (mod 4) $\implies n^2 \equiv 4$ (mod 4) $\implies n^2 \equiv 1$ (mod 4),

$n^2\equiv 3^2$ (mod 4) $\implies n^2 \equiv 9$ (mod 4) $\implies n^2 \equiv 1$ (mod 4)

Hence , for any integer n , $n^2\equiv 0 \ or\ 1$ (mod 4)

(20) Ans : Given that $m$ is a positive integer in the form $4k+3$ , i,e $m=4k+3$ for some integer $k \in \Z_{\geq 0}$.

Claim : $m$ can not be written as a sum of square of two integer .

If possible let $m=a^2+b^2$ , where $a$ and $b$ are two integer .

We know that from (19) , for any integer $n$ , $n^2\equiv 0 \ or \ 1$ (mod 4)

Therefore , the possible value of $(a^2+b^2)$ (mod 4 ) are 0 ,1 and 2 .

But $m$ (mod 4 )= 3 , which is a contradiction of $m=a^2+b^2$ .

Hence , m is not the sum of square of two integer .