# Can I prove (if $n^2$ is even then $n$ is even) directly?

I want to prove that if $n^2$ is even then $n$ is even directly without using the contrapositive or the contradiction methods.

#### Solutions Collecting From Web of "Can I prove (if $n^2$ is even then $n$ is even) directly?"

Hint $\$ Induction yields a direct proof: $\rm\ 2\ |\ n^2\:\Rightarrow\:2\ |\ n\:$ is true for $\rm\:n = 0,1\:$ so $\rm\color{red}{induction}$ yields

$$\rm 2\ |\ (n+1)^2 = (n-1)^2 + 4n\ \Rightarrow\ 2\ |\ (n-1)^2\ \color{red}{\Rightarrow}\ 2\ |\ n-1\ \Rightarrow\ 2\ |\ n+1$$

Similarly one may prove $\rm\: 2\ |\ nk\:\Rightarrow\: 2\ |\ n\ \ or\ \ 2\ |\ k\$ (Prime Divisor Property for $\rm\:p = 2$) via

$$\rm\ 2\ |\ (n+1)k = (n-1)k + 2k\ \Rightarrow\ 2\ |\ (n-1)k\ \color{red}{\Rightarrow}\ 2\ |\ n-1\ \ or\ \ 2\ |\ k\ \Rightarrow\ 2\ |\ n+1\ \ or\ \ 2\ |\ k$$

Note that your problem is the special case $\rm\ k = n\$ of the Prime Divisor Property for $\:2$.

Note that the proof is essentially a brute-force case-analysis. It verifies the result for a complete system of least residues modulo $2,\:$ viz. $\rm\:0,1,\:$ and then, by induction, lifts this proof to all naturals, using the fact that the property $\rm\:P\:$ is true for $\rm\:n\:$ implies that it is true for $\rm\:n+2,\:$ i.e.
$$\rm P(0),\ P(1),\ [P(n)\Rightarrow P(n+2)]\ \Rightarrow\ \ \forall n\: P(n)$$

Similarly there are brute-force residue case-analyis proofs of the prime divisor property for any fixed prime (as known to the ancient Greeks). Such proofs amount to brute-force checking all entries of the multiplication table for integers modulo p, to verify that a product is zero implies that some factor is zero. But proving this true for all primes requires a new idea. For the integers this idea is that gcds exist for all naturals (by the Euclidean algorithm), hence
$$\rm\:p\ |\ ab\ \Rightarrow\ p\ |\ pb,ab\ \Rightarrow\ p\ |\ gcd(pb,ab) = \gcd(p,a)b\:$$

$\rm p\:$ prime $\Rightarrow$ $\rm gcd(p,a) = p\ or\ 1$. $\rm\:gcd(p,a)=p\:$ $\Rightarrow$ $\rm\:p\:|\:a.\:$ $\rm\:gcd(p,a)=1\:$ $\Rightarrow$ $\rm\:p\:|\:gcd(p,a)b = b.$

Hence we’ve proved: $\:$ prime $\rm p\ |\ ab\ \Rightarrow\ p\ |\ a\ \ or\ \ p\ |\ b\quad\ \$ [Prime Divisor Property for $\mathbb Z\:$]

This prime divisor property is easily shown to be equivalent to the uniqueness of factorizations into irreducibles. In domains that don’t have unique factorization, irreducibles need not satisfy the prime divisor property. In such general domains, the term “prime” is used to denote those irreducibles that do satisfy the prime divisor property

The same proof as above shows that irreducibles satisfy the prime divisor property in any integral domain where gcds exist, e.g. Euclidean domains which, like $\mathbb Z$, enjoy a Division Algorithm. One well-known example is the ring $\rm F[x]$ of polynomials over a field $\rm F,\:$ which enjoy the high-school polynomial long division algorithm.

$n^2+n=n(n+1)$ is even; therefore, $n^2$ and $n$ have the same parity.

This is easily possible using prime factor decomposition. Just consider how often the prime factor “2” occurs in $n^2$ and deduce that 2 divides $n$.

Hint: Let $n^2$ be even. Then $n^2=2k$, for some integer $k$. Moreover, by the Fundamental Theorem of Arithmetic, $n^2$ has prime-power decomposition $n^2=\left(p_1^{a_1}p_2^{a_2}\cdots p_s^{a_s}\right)^2=p_1^{2a_1}p_2^{2a_2}\cdots p_s^{2a_s}$, for some positive integers $s$ and $a$.

One can show that if $(a,b)=1$ and $a|bc$ then $a|c$.

Proof: If (a,b)=1 then $ax+by=1$ for integers $x,y$. We also have $bc=ka$ for some integer $k$, but then $c=1a=acx+bcy=a(cx+ky)$. Hence $a|c$.

Now for any prime $p$ and integer $n$ we have $(p,n)=1$ or $(p,n)=p$. In either case $p|n$. Putting in your particular example of $p=2$ yields want you want.

Here’s a proof by induction. It’s similar to Bill’s proof but doesn’t use the Prime Divisor Property.

$P(n)$: $n^2$ is even iff $n$ is even.

Proof:
$(n=1)$: ”$1^2$ is even” and ”$1$ is even” are both false so $P(1)$ is true.

(Inductive step): Assume $P(n)$: $n^2$ is even iff $n$ is even.

Now assume $(n+1)^2$ is even. Then $n^2 + 2n + 1$ is even which means that $n^2$ is odd. By the induction hypothesis $n$ is odd, in which case $n+1$ is even. On the other hand, if $n+1$ is even, then clearly $(n+1)^2$ is even.

This completes the proof.