# 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?

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.

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

How would I go about proving that?

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

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

Now what?

If n is an odd number, then n can be expressed by (2k + 1) where k is any whole number. Right?
So, we have:
n2 = (2k + 1)2 = 4k2 + 4k + 1
= 4 (k2 + 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? :)

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?

$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.