(10 points) (a) For every positive integer n, prove that if n is not divisible by 3, then n2 mod 3 = 1. (b) For every positive integer n, prove that if n is odd

positive-integers

#1

(10 points) (a) For every positive integer n, prove that if n is not divisible by 3, then n2 mod 3 = 1. (b) For every positive integer n, prove that if n is odd, then n2 mod 8 = 1.

Answer:

(a) If n is not divisible by 3, then it is of the form 3k + 1 or 3k + 2 for some non negetive integer k. In the first case [math] (3k+1)^{2} = 3(3k^{2} + 2k) + 1 [\math] which is 1 mod 3. In the second case [math] (3k+2)^{2} = 3(3k^{2} + 4k + 1) + 1 [\math] which is also 1 mod 3.
(b) If n is odd then it is of the form 2k+1 for some non negetive integer k. [math] (2k+1)^{2} = 4k(k+1) + 1. For any positive integer k, either k or (k+1) is diveisible by 2 which tells that k(k+1) is divisible by 2. So, the first term 4k(k+1) is divisible by 8. hence [math]n^{2} mod 8 = 1 [\math]