Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
10  
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
1  
I don't know about this, but did you try proving it via Induction. It should be pretty simple. –  Bidit Acharya May 17 '12 at 18:22

6 Answers 6

up vote 23 down vote accepted

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

$$n^2-1=(2m+1)^2-1=(4m^2+4m+1)-1=4m^2+4m=4m(m+1).$$

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

share|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|improve this answer
5  
Whoever downvoted the answer, care to explain? –  Vadim May 17 '12 at 18:49
6  
That's weird... Except the first two answers, everyone else was downvoted... –  M Turgeon May 17 '12 at 19:17
1  
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
4  
Great! Now everyone has been downvoted... –  M Turgeon May 17 '12 at 21:38

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

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

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

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

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

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\qquad QED$$

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|improve this answer
6  
@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
1  
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|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|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|improve this answer

Your Answer

 
discard

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.