More Proofs: Prove that if n is an odd positive int., then n^2 = 1(mod 8)

[VinnyCee]

Homework Statement

Prove that if n is an odd positive integer, then n^2\,\equiv\,1\,\left(mod\,8\right).

Homework Equations

Theorem:

a\,\equiv\,b\left(mod\,m\right)

if and only if

a\,mod\,m\,=\,b\,mod\,m

The Attempt at a Solution

Using the theorem above:

a\,=\,n^2

b\,=\,1,\,m\,=\,8

Then I have this:

n^2\,mod\,8\,=\,1\,mod\,8

What do I do next to show this for odd positive n?

 

[Päällikkö]

This is hardly "beyond calculus". Anyways, you can represent odd numbers with 2k + 1, where k is a natural number (or zero). Then use eg. proof by induction.

 

[dextercioby]

You need to prove that (2k+1)^2=8p+1 for some "k" and "p" in \mathbb{Z}.

 

[VinnyCee]

How would I go about proving that?

4\,k^2\,+\,4\,k\,+\,1\,=\,8\,p\,+\,1

k^2\,+\,k\,=\,2\,p

Now what?

 

[VietDao29]

If n is an odd number, then n can be expressed by (2k + 1) where k is any whole number. Right?
So, we have:
n² = (2k + 1)² = 4k² + 4k + 1
= 4 (k² + k) + 1 = 4k(k + 1) + 1
What can you say about the product of 2 successive integers? Hint: Is that divisible by 2?
So, is the product 4k(k + 1) divisible by 8?
Can you go from here? :)

 

[StatusX]

How would I go about proving that?

4\,k^2\,+\,4\,k\,+\,1\,=\,8\,p\,+\,1

k^2\,+\,k\,=\,2\,p

Now what?

p is any integer, so k^2+k=2p is equivalent to (ie, exactly the same question as) whether k^2+k is even. Well, is it?

 

[VinnyCee]

k^2\,+\,k is always even. If k were odd, adding an odd integer to another odd one produces an even integer. If k were even, then the whole expression is even as well because adding two even integers always results in an even integer.