9
$\begingroup$

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

Improve this question
$\endgroup$
  • 10
    $\begingroup$ 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. $\endgroup$ – chris May 17 '12 at 18:21
  • 1
    $\begingroup$ I don't know about this, but did you try proving it via Induction. It should be pretty simple. $\endgroup$ – funktor May 17 '12 at 18:22
28
$\begingroup$

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

Improve this answer
$\endgroup$
30
$\begingroup$

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.

Improve this answer
$\endgroup$
  • 6
    $\begingroup$ Whoever downvoted the answer, care to explain? $\endgroup$ – Vadim May 17 '12 at 18:49
  • 6
    $\begingroup$ That's weird... Except the first two answers, everyone else was downvoted... $\endgroup$ – M Turgeon May 17 '12 at 19:17
  • 1
    $\begingroup$ 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! $\endgroup$ – Mark Bennet May 17 '12 at 20:43
  • 4
    $\begingroup$ Great! Now everyone has been downvoted... $\endgroup$ – M Turgeon May 17 '12 at 21:38
  • $\begingroup$ This is a very good answer - it's simpler than using $n=2m+1$ and expanding $(2m+1)^2-1$. $\endgroup$ – Jay Aug 6 '14 at 19:57
15
$\begingroup$

Here are are $8$ proofs $\pm1.\ $ First: $\bmod 8\!:\ {\rm odd}^2 \equiv \{1,\,3,\!\overbrace{5,\,7}^{\large -3,\ -1}\!\!\}^{\large 2}\equiv \{\pm1,\:\!\pm3\}^{\large 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 that $\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}$$

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

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.

Improve this answer
$\endgroup$
6
$\begingroup$

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.

Improve this answer
$\endgroup$
5
$\begingroup$

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\mid k+k^2$. If $k$ odd, so is $k^2$ and again we get that $2|k+k^2$. Thus, $8\mid n^2-1$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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