0
$\begingroup$

Q: $n\in\mathbb{Z}$. Prove that $3 | 2n^2 +1$ iff $3\nmid n$.

I began by assuming not true. Then $3|n$ implies $n=3k$ where $k\in\mathbb{Z}$.

$3 | 2(3k)^2 +1$ $\rightarrow$ $3 | 2(9k^2)+1$ $\rightarrow$ $3 | 18k^2 +1$.

$3 | 3(6k^2 + \dfrac{1}{3})$ but $6k^2 + \dfrac{1}{3}$ is not an integer. Contradiction.

Is this proof valid?

$\endgroup$
6
  • 2
    $\begingroup$ The thing you are trying to prove (at least what you've stated) is not true. $\endgroup$
    – paw88789
    Feb 16 at 15:17
  • 1
    $\begingroup$ There is a typo somewhere, we have $3\mid 2n^2+1$ iff $3\nmid n$ instead. $\endgroup$
    – Peter
    Feb 16 at 15:18
  • $\begingroup$ Fixed it @paw88789 $\endgroup$
    – blacknapkins7
    Feb 16 at 15:21
  • $\begingroup$ The statement you are asked to prove asserts "if and only if". Your hypothetical proof by contradiction will still need a two way argument. Better strategy: there are only three cases modulo $3$. Check each one separately. $\endgroup$
    – Ethan Bolker
    Feb 16 at 15:24
  • 2
    $\begingroup$ No. You need to check the cases $n \equiv 0,1,2 \pmod{3}$. You can do a lot less algebra if you do the arithmetic modulo $3$ rather than with the forms $3k+r$. Then you see $2^2 \equiv 1$ immediately. $\endgroup$
    – Ethan Bolker
    Feb 16 at 15:39

1 Answer 1

Reset to default
1
$\begingroup$

Your proof is valid, but here's an easier way to see and write this- $$3|n\iff 3|n^2\iff 3|2n^2\iff 3\nmid 2n^2+1$$ The idea is just to realise that $n$ cannot divide both $f(n)$ and $f(n)+1$.

Since the OP had already solved the problem, I didn't care much about the details. But, since it was pointed out in the comments, here's the details-

$$n=3k+1\implies 2n^2+1=2(3k^\prime)+2+1\equiv 0 \;(\operatorname{mod }3)$$ $$n=3k+2\implies 2n^2+1=2(3k^\prime)+2.2^2+1\equiv 0\;(\operatorname{mod }3)$$

which completes the argument.

$\endgroup$
2
  • 3
    $\begingroup$ The last assertion in this answer requires more work. It's not true in general that if $3$ does not divide $A+1$ then it divides $A$. $\endgroup$
    – Ethan Bolker
    Feb 16 at 15:27
  • $\begingroup$ @EthanBolker placed an edit. $\endgroup$
    – Sayan Dutta
    Feb 16 at 22:08

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.