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?
9
$\begingroup$
$\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
29
$\begingroup$
$\endgroup$
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$...
30
$\begingroup$
$\endgroup$
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.
-
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$ 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$
$\endgroup$
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}$$
answered May 17 '12 at 19:00
-
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$
$\endgroup$
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.
answered May 17 '12 at 18:25
6
$\begingroup$
$\endgroup$
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.
answered May 17 '12 at 18:23
5
$\begingroup$
$\endgroup$
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$.
