10
$\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?

$\endgroup$
2
  • 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
    Commented May 17, 2012 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$
    – user11470
    Commented May 17, 2012 at 18:22

6 Answers 6

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.

$\endgroup$
6
  • 7
    $\begingroup$ Whoever downvoted the answer, care to explain? $\endgroup$
    – Vadim
    Commented May 17, 2012 at 18:49
  • 7
    $\begingroup$ That's weird... Except the first two answers, everyone else was downvoted... $\endgroup$
    – M Turgeon
    Commented May 17, 2012 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$ Commented May 17, 2012 at 20:43
  • 4
    $\begingroup$ Great! Now everyone has been downvoted... $\endgroup$
    – M Turgeon
    Commented May 17, 2012 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
    Commented Aug 6, 2014 at 19:57
29
$\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$...

$\endgroup$
3
  • 1
    $\begingroup$ Could someone elaborate as to why $m(m+1)$ is even regardless of if m is odd or even? It might be obvious, but I think the line of thinking would be to check what happens when m is even or when m is odd and then find that $m(m+1)$ is even. $\endgroup$ Commented Jan 28, 2021 at 16:50
  • $\begingroup$ @GrayLiterature Yes, that's right. Check when $m$ is even or odd separately. $\endgroup$
    – anon
    Commented Apr 1, 2022 at 20:39
  • $\begingroup$ @GrayLiterature If $m$ is odd then $m+1$ is even. If $m$ is even then $m+1$ is odd. So either way, $m(m+1)$ is always even. See also triangular numbers. $\endgroup$ Commented Nov 25, 2022 at 22:25
15
$\begingroup$

We sketch $\:\!\bf 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: $\rm\,n\equiv u\pmod{\!2m}\Rightarrow n^2\equiv u^2\pmod{\!4m}\,$ by here. OP is case $\rm\,u\equiv\pm1,\, m = 2.$


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: $\rm\:mod\ 8\:$ the function $\rm\:f(n) = (2n\!-\!1)^2\:$ is constant (thus induction $\rm\,\Rightarrow 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 (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}$$


$\endgroup$
3
  • 1
    $\begingroup$ And now there are 2 downvotes. Seemingly the more proofs, the more downvotes. The mind boggles... $\endgroup$ Commented May 19, 2012 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
    Commented May 21, 2012 at 17:37
  • $\begingroup$ The trend continues - another proof and another downvote! $\endgroup$ Commented Nov 28, 2022 at 15:29
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.

$\endgroup$
4
  • $\begingroup$ Would you mind expanding on why one of the terms must be divisible by 4? I'm afraid I can't figure it out $\endgroup$
    – Jon
    Commented Jun 21, 2022 at 18:05
  • $\begingroup$ @Jon Out of two consecutive multiples of $2$ one must be divisible by $4$ - if the lower number is not divisible by $4$ it is twice an odd number ie $2\times (2n-1)=4n-2$ and adding $2$ gives you $4n$, which is a multiple of $4$ $\endgroup$ Commented Jun 21, 2022 at 19:32
  • $\begingroup$ Thanks for your answer. Taking this for granted " if a number is not divisible by 4 it is twice an odd number", I don't understand the justification to add 2 to 4n - 2 $\endgroup$
    – Jon
    Commented Jun 22, 2022 at 14:30
  • $\begingroup$ @Jon Well an even number is twice something, and that something is either even or odd. If twice even it is divisible by 4, if not it is twice odd. Every odd number is of the form $2n-1$. $\endgroup$ Commented Jun 22, 2022 at 15:14
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.

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

$\endgroup$

You must log in to answer this question.