Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am trying to show that if $n$ is an odd natural number, then $8$ divides $n^{2}-1.$ I was able to prove that because I know that if $n$ is an odd natural number, then $n^{2}$ can be writen as $8k+1$ for some $k\in \mathbb{N}.$ I would like to show this question by using the Euclidian division. Then I wrote $n^{2}-1=8k+r$, where $0\leq r < 8.$ When $r=2$ we get $n^{2}-1=8k+2.$ Since $n$ is odd, then $n^{2}-1$ is even and I got stuck. Is there way to fix that?

share|cite|improve this question
It is not true that each odd natural number can be written as $8k+1$ for $k\in\mathbb{N}$. For instance, how do you get 3? You can write each odd number as $2k+1$ though. – chris May 17 '12 at 18:21
I don't know about this, but did you try proving it via Induction. It should be pretty simple. – funktor May 17 '12 at 18:22
up vote 26 down vote accepted

Being odd means that $n=2m+1$ for some $m$. This gives


Notice that either $m$ is even or $m$ is odd: either way, $m(m+1)$ is even, so can be written as $2k$...

share|cite|improve this answer

An easier way to see this is as follows: $n^2-1=(n-1)(n+1)$ where both $n-1$ and $n+1$ are even, and one of them must be divisible by 4.

share|cite|improve this answer
Whoever downvoted the answer, care to explain? – Vadim May 17 '12 at 18:49
That's weird... Except the first two answers, everyone else was downvoted... – M Turgeon May 17 '12 at 19:17
My answer was as simultaneous with this as I have ever known - well done with the trigger finger, and because this way of thinking about it ought to be much better known! – Mark Bennet May 17 '12 at 20:43
Great! Now everyone has been downvoted... – M Turgeon May 17 '12 at 21:38
This is a very good answer - it's simpler than using $n=2m+1$ and expanding $(2m+1)^2-1$. – Jay Aug 6 '14 at 19:57

Here are are $8$ proofs $\pm1.\ $ First, the easiest: $\rm\:\! \ mod\ 8\!:\ odd^2 \equiv \{\pm1,\:\!\pm3\}^2 \equiv \{1\}$

Alternatively, $\ \ \rm n\ odd\ \Rightarrow\ n = 4k\pm1\ \Rightarrow\ n^2-1 = (4k\pm1)^2-1 = 8k \:\!(2k\pm1)$

Or: $\rm\: n\equiv u = \pm1\pmod 4\:\Rightarrow\: 4\:|\:n\!-\!u,\:2\:|\:n\!+\!u\:\Rightarrow\: 8\:|\:(n\!-\!u)(n\!+\!u) = n^2 - 1$

Or, it's easy by induction: it's true for $\rm\:n = 1,\:$ and if true for all odds below the odd $\rm\:n\!+\!2\:$ then $\rm\:(n\!+\!2)^2\!-1\: =\: n^2\!-\!1 + 4\:\!(n\!+\!1).\:$ But $\rm\:8\:|\:n^2\!-\!1\:$ by induction, $\rm\:8\:|\:4(n\!+\!1)\:$ by $\rm\:n\:$ odd.

Or, notice $\rm\:mod\ 8,\:$ the function $\rm\:f(n) = (2n\!-\!1)^2\:$ is constant (hence $\rm\:f(n)\equiv f(1)\equiv 1)$ because its first difference is $\equiv 0,\:$ i.e. $\rm\:f(n\!+\!1)-f(n) = (2n\!+\!1)^2-(2n\!-\!1)^2\! = 8n\equiv 0.$

By telescopy the prior proof yields the sum representation below, and a vivid proof.

$$\rm\quad (2n+1)^2 - 1\: =\: \sum_{k\!\:=\!\:1}^n\!\: 8k$$

More generally, it's the special case $\rm\:m = 8,\:\lambda(8)=2\:$ of the Euler-Carmichael theorem $$\rm\ gcd(a,m) = 1\ \Rightarrow\ a^{\lambda(m)}\equiv 1\pmod{m}$$

share|cite|improve this answer
@Downvoter: if something is not clear then please feel free to ask questions and I will be happy to elaborate. – Bill Dubuque May 17 '12 at 19:38
And now there are 2 downvotes. Seemingly the more proofs, the more downvotes. The mind boggles... – Bill Dubuque May 19 '12 at 15:36
Great, now every answer has two downvotes. Someone else (or the same person under another name?) downvoted all answers without any commenting on it. – Vadim May 21 '12 at 17:37

Since $n$ is odd, $n^2-1 = (n-1)(n+1)$ is the product of two consecutive even numbers, one of which must be divisible by 4.

share|cite|improve this answer

If we want to use Euclidean division explicitly, we can observe that if $n$ is an odd number, then the remainder when $n$ is divided by $8$ is equal to $1$, $3$, $5$, or $7$.

If the remainder is $1$, then $n=8k+1$ for some integer $k$. It follows that $n^2-1=(8k+1)^2-1^2=(8k)(8k+2)$. Note that $(8k)(8k+2)$ is divisible by $8$, and indeed by $16$.

If the remainder is $3$, then $n=8k+3$ for some integer $k$. Then $n^2-1^2=(8k+2)(8k+4)$, and $(8k+2)(8k+4)$ is clearly divisible by $8$.

We can use similar arguments for the other two possibilities. It is a little nicer to observe that if the remainder when $n$ is divided by $8$ is $5$, then $n=8k-3$ for some integer $k$. Also, if the remainder is $7$, then $n=8k-1$ for some integer $k$. Then we can essentially recycle the first two calculations.

share|cite|improve this answer

Every odd number can be written in the form $n=2k+1$ for $k\in\mathbb{N}$. Then $$ n^2-1=(2k+1)^2-1=4k^2+4k=4(k+k^2) $$ If $k$ is even, then so is $k^2 \Rightarrow 2| k+k^2$. If $k$ odd, so is $k^2$ and again we get that $2|k+k^2$. Thus, $8|n^2-1$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.