## anonymous 3 years ago Prove that if n is an integer, then n^2 mod 5 is either 0,1, or 4

1. anonymous

there are only five possible ways for n. first case: $$n \equiv 0(mod 5)$$, then $$n^2 \equiv 0(mod 5)$$ second case: $$n \equiv 1(mod 5)$$), then $$n^2 \equiv 1(mod 5)$$ third case:$$n \equiv 2(mod 5)$$), then $$n^2 \equiv 4(mod 5)$$ fourth case:$$n \equiv 3(mod 5)$$), then $$n^2 \equiv 6(mod 5)$$, which is equal to $$n^2 \equiv 1(mod 5)$$, as $$6 \equiv 1(mod 5)$$ fifth case:$$n \equiv 4(mod 5)$$), then $$n^2 \equiv 16(mod 5)$$ which is equal to $$n^2 \equiv 1(mod 5)$$, as $$16 \equiv 1(mod 5)$$ so we conclude that if n is an integer, n^2 mod 5 is either 0,1, or 4

2. anonymous

sorry, for fourth case, it's $$n^2 \equiv 9 (mod 5)$$ and it's equal to $$n^2 \equiv 4 (mod 5)$$

3. anonymous

Excellent, but how do we know that there are only five possible values for n?

4. anonymous

because the remainder for any integer k divided by an integer n has only n-1 remainders. e.g. for 2, you can only get 0 or 1 as remainder. any other remainder means that the division is incomplete.

5. anonymous

sorry it'snot n-1, it's n. but the range is 0,1,2,3,...,n-1