Prove that if n is a positive integer, then n 2 is congruent to0, 1, or 4 modulo

Question

Prove that if n is a positive integer, then n2 is congruent to0, 1, or 4 modulo 8. I really don't even know where to start on this problem.Anyhelp would be much appreciated. Thanks. Prove that if n is a positive integer, then n2 is congruent to0, 1, or 4 modulo 8. I really don't even know where to start on this problem.Anyhelp would be much appreciated. Thanks.

Explanation / Answer

If n is a positive integer then n has to be even or odd. (Proof by Cases) Assume n is odd, then for some integer k n=2k+1. It follows that n^2 is (2k+1)(2k+1)=4k^2+4k+1=4(k(k+1))+1. Notice k(k+1) is two consecutive integers, therefore one of them has to be even. So k(k+1) is even, then for some integer "m" 2m=k(k+1). So n^2=4(2m)+1=8m+1. ---->n^2-1=8(m) by def n^2==1 mod 8 since m is an integer. Now suppose n is even. n=2k for some integer k. Therefore n^2=4k^2-->n^2-4=4k^2-4 -->n^2-4=4(k^2-1) if k^2-1 is even then for some integer m, k^2-1 = 2m --->n^2-4=8m. Hence n^2==4 mod8 by definition. If k^2-1 is odd k^2-1=2m+1-->n^2-4=4(2m+1)=8m+4. n^2-4=8m+4-->n^2=8m or n^2-0=8m. Hence by def n^2==0 mod8 Qed

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.