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

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

Related Calculus and Beyond Homework Help News on Phys.org
Päällikkö
Homework Helper
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
Homework Helper
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?

VietDao29
Homework Helper
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? :)

StatusX
Homework Helper
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.