1

I understand that I need to derive false from $\neg(9 \nmid (n^2 + 3))$, or $9 \mid n^2 + 3$. To do this, I attempted to say $n^2 + 3 = 9k$ for some $k \in \mathbb{Z}$. Then I tried something like $3 = -n^2 = -3(k - 1)$, but $-3 \mid 3$. That doesn't contradict the statement.

I think that I'm missing something very fundamental here. Any clarity would be appreciated.

Jochen
  • 2,260
user956014
  • 23
  • 1
    There are just two cases you have to distinguish, mainly $n=3k$ and $n=3k\pm 1$. Show, that in both cases $9\nmid n^2+3$. – Jochen Aug 05 '21 at 10:11
  • 1
    proof by contradiction - Hint: $9 ~| ~(n^2 + 3) ~\implies ~3 ~| ~n^2.$ Question: if $~3 ~| ~n^2,~$ does this imply that $~3 ~| ~n$? If it does imply that, so what? – user2661923 Aug 05 '21 at 10:13

3 Answers3

3

Alternatively: The remainder of dividing a number by 9 can be 0,1,2,3,4,5,6,7 or 8. When squaring those numbers, all these remainders become 0,1,4,0,7,7,0,4 or 1, respectively. When adding 3, these remainders become, respectively, 3,4,7,3,1,1,3,7,4. None of these remainders is zero, so indeed $n^2+3$ is never a multiple of 9. EDIT: To learn more about it: https://en.wikipedia.org/wiki/Modular_arithmetic

Qwertuy
  • 1,129
2

If $9 \mid (n^2+3) $ then $n^2 = 9m - 3$. So $3 \mid n^2$, and in turn $3 \mid n$ and there is an integer $k$ so that $n = 3k$. Substitute this back into the equation: $(3k)^2 = 9m-3$. So $9k^2=9m-3$ and this means $9 \mid 3$, impossible. Hence $9\nmid (n^2+3)$.

Wang YeFei
  • 6,390
1

If you assume $\forall n, 9 \mid n^2 + 3$ then you can easily get a contradiction. A forall is like a machine that prints out facts, so we use it to print out a version with $n=2$ say. This gives us the assumption $9 \mid 2^2 + 3$ i.e $9 \mid 7$. That gives us our proof of false.