-1

The square of any integer is either perfectly divisible by 4 or leaves a remainder 1 when divided by 4. Any number which on division by 4 leaves a remainder 2 or 3 is not a perfect square. Prove

Sakshi Bhatia
  • 23
  • 1
    Have you tried anything? What part of the question are you stuck on? Also note that this is not a very good test, since it's passed by numbers such as $5, 8, 12$ and $13$, which are not squares. – Arthur Sep 09 '15 at 09:22

2 Answers2

2

Looking at the remainder (regarding division by $4$) of the square, using the computation rule $$ (a b) \bmod q = \left((a \bmod q)(b \bmod q)\right) \bmod q \quad (a,b,q \in \mathbb{Z}) $$ for taking the remainder, one gets $$ r = n^2 \bmod 4 = (\underbrace{n \bmod 4}_s)^2 \bmod 4 \\ $$ For the four possible values of $s$ we get these remainders: $$ r(0) = 0^2 \bmod 4 = 0 \\ r(1) = 1^2 \bmod 4 = 1 \\ r(2) = 2^2 \bmod 4 = 0 \\ r(3) = 3^2 \bmod 4 = 1 $$ thus a perfect square is of the form $4q$ or $4q+1$.

mvw
  • 34,562
1

You want to know the class of the square of a number modulo 4. Hence, it is enough to show that in the finite ring $\mathbb{Z}/4\mathbb{Z}$ the only squares are 0 and 1. Compute the square of the four classes $\{\bar{0},\bar{1},\bar{2},\bar{3}\}$ and figure out the answer.

Patricio
  • 101