# Proofs-Divisibility of Integers

• May 14th 2009, 11:22 PM
utopiaNow
Proofs-Divisibility of Integers
Let $\displaystyle n \in \mathbb{Z}$. Prove that $\displaystyle 2\ |\ (n^4 - 3)$ if and only if $\displaystyle 4\ |\ (n^2 + 3)$.

Attempt at Proof:
First I just dealt with the forward implication: if $\displaystyle 2 \ |\ (n^4 - 3)$ then $\displaystyle 4 \ |\ (n^2 + 3)$. To prove this I took the contrapositive of this statement which is: If $\displaystyle 4 \not\vert\ (n^2 + 3)$, then $\displaystyle 2 \not\vert\ (n^4 - 3)$.
$\displaystyle 4 \not\vert\ (n^2 + 3)$ can be broken down into 3 cases, the case I'm having trouble with is: let $\displaystyle (n^2 + 3) = 4q + 2$, then $\displaystyle n^2 = 4q - 1$ and then $\displaystyle n^4 - 3 = (4q - 1)^2 - 3 = 16q^2 - 8q - 2 = 2(8q^2 -4q - 1)$ which is an even number and so $\displaystyle 2 \ |\ (n^4 - 3)$, but that's not what I wanted for the contrapositive.

What am I doing wrong?
• May 14th 2009, 11:45 PM
CaptainBlack
Quote:

Originally Posted by utopiaNow
Let $\displaystyle n \in \mathbb{Z}$. Prove that $\displaystyle 2\ |\ (n^4 - 3)$ if and only if $\displaystyle 4\ |\ (n^2 + 3)$.

Attempt at Proof:
First I just dealt with the forward implication: if $\displaystyle 2 \ |\ (n^4 - 3)$ then $\displaystyle 4 \ |\ (n^2 + 3)$. To prove this I took the contrapositive of this statement which is: If $\displaystyle 4 \not\vert\ (n^2 + 3)$, then $\displaystyle 2 \not\vert\ (n^4 - 3)$.
$\displaystyle 4 \not\vert\ (n^2 + 3)$ can be broken down into 3 cases, the case I'm having trouble with is: let $\displaystyle (n^2 + 3) = 4q + 2$, then $\displaystyle n^2 = 4q - 1$ and then $\displaystyle n^4 - 3 = (4q - 1)^2 - 3 = 16q^2 - 8q - 2 = 2(8q^2 -4q - 1)$ which is an even number and so $\displaystyle 2 \ |\ (n^4 - 3)$, but that's not what I wanted for the contrapositive.

What am I doing wrong?

$\displaystyle 2\ |\ (n^4 - 3)$ implies that $\displaystyle n^4$ is odd which implies $\displaystyle n$ is odd.

If $\displaystyle n$ is odd there exists a $\displaystyle k \in \mathbb{Z}$ such that $\displaystyle n=2k+1$

Then:

$\displaystyle n^2+1=(2k+1)^2+3=4k^2+4k+4$

The other direction of the proof proceeds by observing that $\displaystyle 4\ |\ (n^2 + 3)$ implies $\displaystyle n$ odd ...

CB