Provide a counterexample: If $n^2-1$ is divisible by $5$, then $n$ is divisible by $2$ or $3$

Question

Provide a counterexample: If $n^2-1$ is divisible by $5$, then $n$ is divisible by $2$ or $3$

My book doesn't have an answer to this question, but I think it's $n=6$. Since $6^2-1=35$, which is divisible by $5$ but not by $2$ or $3$. Is this the right way to solve these counterexample problems? Are these problems solved by just plugging in numbers until you get to the right one?

Answer 1

Yes! That approach is exactly the right way to do it. A statement like "If $n^2 - 1$ is divisible by $5$, then $n$ is divisible by $2$ or $3$" means it's true for EVERY SINGLE POSSIBLE $n$ out there.

So if you can find even one $n$ where it's not true, then the statement is false!

You can solve counterexample problems by plugging in numbers one by one, but I find it's more insightful to take a two-pronged approach. Try to prove the proposition - and then ask, where are you getting stuck? What is going wrong? Use that to guide finding a counterexample.

In this case, you're not interpreting the problem correctly. Notice that the statement is not $n^2 - 1$ is divisible by $2$ or $3$, but that $n$ is divisible by $2$ or $3$. Since you picked $n=6$, it is in fact divisibly by both $2$ and $3$.

Instead try reasoning along these lines. Suppose $5$ divides $n^2 - 1$. Since $n^2 - 1 = (n+1)(n-1)$ and $5$ is prime, we must have either that $5|(n+1)$ or $5|(n-1)$. That is, either $n = 5k - 1$ or $n = 5k + 1$ for some $k$. So let's search for a number of the form $5k \pm 1$ that is not divisible by $2$ or $3$. Now I'd start listing numbers and looking for ones that are not divisible by $2$ or $3$: $$\ldots\ -1,\ 1,\ 4,\ 6,\ 9,\ 11,\ 14,\ 16,\ 19,\ 21,\ \ldots$$

Extra challenge- is there a pattern you can see here?

Answer 2

Your counterexample is not quite right. $n=6$ has $5|n^2-1$, but $2|n$ and $3|n$.

On the other hand, take $n=11$. $11^2=121$ and so $n^2-1$ is divisible by $5$ but $2\nmid 11$ and $3\nmid 11$.

Answer 3

$n^2 - 1= (n-1)(n+1)$ so if $5|n^2 -1$, as $5$ is prime we know either $5|n-1$ or $5|n+1$.

Now if we're clever we can try to take counter examples $n=6$ or $4$. nope. $n = 11$ or $9$. Oh, wait there's a counter example. $n=11$. (Also $n=1$ and $5|0$ is a counter example.)

But plugging in numbers in the hope of a counterexample is ineffiecient. What if the first counter example is really huge? Or what if the statement is true and we never find a counter example?

we should evaluate further.

So $n\equiv \pm 1 \pmod 5$. And we are asked to show or find a counter example that $n \equiv 0 \pmod 3$ or $n \equiv 0\pmod 2$.

Now By Chinese remainder theorem $\gcd(5,2); \gcd(5,3); \gcd(2,3)=1$ so ther is a unique solution to

$n \equiv a \pmod 5$ and $n \equiv b \pmod 3$ and $n \equiv c \pmod 2$ will have a unique solution $\mod 30$ and we just need to choose $a = \pm 1$ and $b \ne 0$ and $c \ne 0$.

Example $n \equiv 1 \pmod 5$ and $n\equiv 1 \pmod 3$ and $n\equiv 1 \mod 2$ will have solutions and that solution would be a counter example.

We don't even have to find it! We know it exists!

.... but it's $1 \pmod {30}$ so $n =1$ is counter example. $n = 31$ is a counterexample and $n = 30k + 1$ is a counter example. $(30k + 1)^2- 1 = 900k^2 + 60k + 1 - 1= 5(180k^2 + 12k)$ but $2|30k$ and $3|30k$ so $2,3\not \mid 30k + 1$).

We can find other counter examples.

$n \equiv -1 \pmod 5$ and $n \equiv 1 \pmod 3$ $n\equiv 1 \pmod 2$ would give us $n \equiv 19\pmod 30$ so $19, 49, 79$ etc are counter examples.

And $n \equiv 1 \pmod 5$ and $n \equiv -1 \pmod 3$ and $n \equiv 1 \pmod 2$ will have solution $n \equiv 11 \pmod 30$. So $11, 41, 71$ etc are counter examples.

And $n \equiv -1\pmod 5$ and $n \equiv -1 \pmod 3$ and $n \equiv 1 \pmod 2$ will have soultion $n \equiv 29 \pmod 30$. So $29, 59, 89$ etc are counter examples.

Answer 4

A counterexample is an $n$ with $5\mid n^2\!-\!1,$ not $(2\mid n$ or $3\mid n),\,$ i.e $\,5\mid n^2\!-\!1\,$ and $\,2\nmid n\,$ and $\,3\nmid n$

Equvalently $\, 5\mid (n\!-\!1)(n\!+\!1)\,$ and $\,\gcd(n,6) = 1,\,$ true iff $ \,n\equiv \pm1\, $ both $\!\bmod 5$ & $6$

e.g. $\, n\equiv 1\,$ both $\bmod 5$ & $6\iff 5,6\mid n-1\iff 30\mid n-1,\,$ e.g. $\,n\ =\ 1,\ 31,\,\ldots$

and also its negative: $\ n\equiv -1\,$ both $\bmod 5$ & $6\iff 30\mid n+1,\,$ e.g. $\,n=-1,29,\,\ldots$

and also the mixed sign case $\,n\equiv 1,-1\bmod 5,6\iff n\equiv 11\pmod{\!30}\ $ by CRT

and also the negative of that: $\,n\equiv -1,1\bmod 5,6\iff n\equiv -11\equiv 19\pmod{\!30}$

Of course we need only one counterexample, but it's instructive to find them all by CRT.