Proof regarding divisibility

Question

if $n\in\mathbb{Z}$, then $4$ does not divide $(n^2 - 3)$

I'm not sure how to approach this question, I know how to do questions that involve proving that it does divide but I'm unsure of how to do does not divide. Would I want to use contrapositive as a method of proof?

Answer 1

Break it into two cases: even and odd. I'll do the even case (since it's easier but you'll get the idea).

Suppose $n$ is even, then $n = 2m$ for some $m\in\mathbb{Z}$. Then $n^2 = (2m)^2 = 4m^2$. Therefore $n^2 - 3 = 4m^2 - 3$. Can $4$ ever divide this?

Answer 2

Have you done any modular arithmetic? Have a think about what would happen if you worked out the possible values of $n^2 - 3 $ (mod $4$). If 4 is to divide $n^2 - 3 $, then you would need $n^2 - 3 \equiv 0$ (mod $4$). Can this happen?

Answer 3

$n^2\equiv 0,1 \pmod 4$ so $$n^2-3\equiv 1, 2 \pmod 4$$

Answer 4

I suppose you could use proof by contrapositive if you really wanted to, but that seems needlessly complicated for something that could so easily be considered with congruences (modular arithmetic), e.g., $47 \equiv -1 \mod 12$ or $47 \equiv 11 \mod 12$.

The simplest modulus would of course be 4 and you're done in the blink of an eye, but to make things a tiny bit more interesting I'm going to use 12; in order for a number to be divisible by 4, it must be 4, 8 or 0 modulo 12. The squares modulo 12 are 1, 4, 9, 4, 1, 0, 1, 4, 9, 4, 1, 0. Then the squares minus 3, taken modulo 12, are 10, 1, 6, 1, 10, 9, 10, 1, 6, 1, 10, 9; none of these are 4, 8 or 0.

Answer 5

Hint $\ $ If $\,f(x)\,$ is a polynomial with integer coef's then, by Polynomial Congruence Rule (PCR)

$\qquad\quad\ \ 4\mid f(n) \iff 4\mid f(\color{#c00}{n\ {\rm mod}\ 4})\ \ $ since $\ \ {\rm mod}\ 4\!:\,\ \color{#c00}{ n'}\equiv n\,\Rightarrow\, f(\color{#c00}{n'})\equiv f(n)\ $ by PCR

Thus if $\ 4\nmid f(n)\ $ for all $\,n \in \{0,1,2,3\}\,$ then $\ 4\nmid f(n)$ for all $\,n\in\Bbb Z.$