Decide if the statement " $n^2-1$ is multiple of $4$ if and only if $n-1$ is multiple of $4$" is true or false.

Question

The statement is biconditional ( P $\Longleftrightarrow$ Q )

$n-1$ is multiple of 4 $\Longleftrightarrow n^2-1$ is multiple of 4

The statement is true if $\,$ P $\Rightarrow$ Q and Q$\Rightarrow$ P are true

---

P $\Rightarrow$ Q

$ n-1=4k, \, k \in \mathbb{N} \Rightarrow n^2-1=4p\, , p \in \mathbb{N} $

Direct Proof:

\begin{split} n-1=4k, \, k \in \mathbb{N} \Rightarrow n^2-1 & = (n-1)(n+1)\\ & = 4k\, (n+1) \\ & =4kn+4k \\ &=4(kn+k) \\&=4p, \, p \in \mathbb{N} \end{split}

$\therefore \,$ P $\Rightarrow$ Q is true

---

Q $\Rightarrow$ P

$ n^2-1=4p, \, p \in \mathbb{N} \Rightarrow \, n-1=4k\ , k \in \mathbb{N} $

I found a counterexample for $n=7$ but I don't know how to proove it with a formal method.

Can someone help me please?

Answer 1

$n^2-1$ must be even $\iff n^2$ must be odd $\iff n$ must be odd

$=2m+1$(say)

Now $(2m+1)^2-1=8\cdot\dfrac{m(m+1)}2\equiv0\pmod8$

Now $n-1=2m\equiv \begin{cases} 0\pmod4 &\mbox{if } m \equiv 0\pmod2 \\ 2\pmod4 & \mbox{if } m \equiv 1\pmod2 \end{cases}$

Answer 2

It doesn't have to be complicated! You found a counterexample for $n=7$, so just substitute in:

$$n^2 - 1 = 49 - 1 = 48$$ $$n - 1 = 7 - 1 = 6$$

We know $48$ is divisible by $4$, but $6$ is not divisible by $4$. Therefore, the given statement is false.

Answer 3

$n^2 -1$ is a divisible by four is the same as saying $n^2 \equiv 1 \pmod{4}$. Consider the case where $n$ is even. Then $n = 2k$ for some $k \in \mathbb{N}$. Then we have $(2k)^2 = 4k^2 \equiv 0 \pmod{4}$. Hence, we know that $n$ cannot be even. Consider $n$ is odd. Then we have $n = 2k+1$ for some $k \in \mathbb{N}$. Notice $n^2 = (2k+1)^2 = 4k^2+4k+1$. Thus we have $n \equiv 1 \pmod{4}$. So we see that $n$ must be odd.

If $n$ is odd then we have $n = 2k+1$. Notice that $n-1 = 2k$ in this case. So $n-1 \equiv 2k \pmod{4}$. However, there exists $k$ where this is not 0. Notice that $k=1$ we have $n-1 \equiv 2 \pmod{4}$, for $k=3$ we have $n-1 \equiv 2 \pmod{4}$. So this leads us to a claim: if $k$ is odd then this is not true. Assume $k$ is odd. Then we have $k=2j+1$, $j \in \mathbb{N}$. Substitute this in to give us $n-1 \equiv 2(2j+1) \pmod{4}$. However, this gives us $n-1 \equiv 4j + 2 \equiv 2 \pmod{4}$. So if $k$ is odd we have $n-1 \equiv 2 \pmod{4}$. Hence, if $n$ is of the form $2(2j+1)+1 = 4j+3$ where $j \in \mathbb{N}$, this cannot hold true. However, this was too much work; since we found a counterexample, we could've stopped there and said that the claim is not true. Notice that your counterexample is the case where $j=1$.

Answer 4

Let's say, $$n^2-1=4k$$ $$(n-1)(n+1)=4k$$ Now for that to be true,

Either,

$$(n-1)=4p$$

Or

$$n+1=4q$$ Then, $$n-1=4q-2\not=4e$$

So , the condition that $$n^2-1=4n\implies n-1=4q$$ Doesn't hold true.

Answer 5

It's simpler with congruences:

The assertion means $n^2\equiv 1\mod 4$ if and only if $n\equiv 1\mod 4$.

The if part is obviously true. For the only if part, just list squares of congruence classes mod. $4$: $$\begin{array}{l|r r r} n&0&1&2&3\\\hline n^2&0&1&0&1\end{array}$$

Answer 6

Correct. $\,x^2-1\,$ has at least $\color{#c00}2\,$ roots $\bmod m\color{#c00}{>2}\!:\ $ $x\equiv1 $ and $\,x\equiv -1\equiv m\!-\!1.\,$ But if $\,m=2\,$ then $\,-1\equiv 1$ and $\,x^2-1\equiv (x-1)^2$ so $\,x\equiv\,1$ is a double root.

Answer 7

1)$n^2-1= (n-1)(n+1)$,

Let $n$ be odd: $n+1, n-1$ are even:

$n+1= 2r$, $n-1= 2s$.

$n^2-1= 4rs$ is divisible by $ 4$.

Choose $n=7:$

$n-1 = 6$, is not divisible by $4$.

2) let $n-1$ be divisible by $4$, I.e. $n-1 =4k$.

Since $n^2-1=(n-1)(n+1)=$

$4k(n+1)$, hence

$n^2-1 $ divisible by $4$.

Recapping:

False:

1) $n^2-1$ is divisible $ 4$ $ \Rightarrow$ $n-1$ is divisible by $4$.

(counterexample: $n=7$).

True:

2) $n-1$ is divisible by $4$ $\Rightarrow$ $n^2 -1$ is divisible by $4.$