$a^n$ even implies $a$ even I've tried to prove that $(\forall a,n>0 \in \mathbb{N}),(a^n \text{ even} \implies a \text{ even})$, can someone tell me whether my proof is sound?
Lemma 1: $a \text{ even} \implies a^2 \text{ even}$
Lemma 2: $a \text{ odd} \implies a^2 \text{ odd}$
$$a^n \text{ even} \equiv a^{n-1}a \text{ even} \equiv (a^{n-1} \text{ odd} \land a \text{ even}) \lor (a^{n-1} \text{ even} \land a \text{ odd}) \lor (a^{n-1} \text{ even} \land a \text{ even})$$
by virtue of Lemma 1 (by construction) $(a \text{ even} \implies a^{n-1} \text{ even})$ and by the same argument, from Lemma 2, $(a \text{ odd} \implies a^{n-1} \text{ odd})$
whence, $(a^{n-1} \text{ odd} \land a \text{ even}) \equiv \text{False}$ and $(a^{n-1} \text{ even} \land a \text{ odd}) \equiv \text{False}$
therefore, we can write
$a^n \text{ even} \equiv F \lor F \lor (a^{n-1} \text{ even} \land a \text{ even}) \equiv (a^{n-1} \text{ even} \land a \text{ even})$
Since, $(\text{True} \equiv a^n \text{ even} \equiv (a^{n-1} \text{ even} \land a \text{ even})) \therefore a^{n-1} \text{ even and a even} \square$
 A: Your proof is almost valid, but it is unfortunately circular, because you use the following lemma:
$$a \text{ is odd} \implies a^{n-1} \text{ is odd}$$
However, if you take the contrapositive of this statement:
$$a^{n-1} \text{ is even} \implies a \text{ is even}$$
which is basically the same as your statement, except with $n-1$ instead of $n$.
Therefore, in order to make your proof valid, you need to pose it as a proof by induction, making $n=1$ your base case and then using the proof you have written above to show that $a^{n-1} \text{ is even} \implies a \text{ is even}$ can be used to prove $a^n \text{ is even} \implies a \text{ is even}$.
A: much better to prove the contrapositive
$a$ odd implies $a^n$ odd. 
This is easily proved by induction since the product of two odd numbers is odd. 
A: What do you know about primes? If a prime divides a product, it divides one of the factors. You know 2 divides $a^n$, so what can you conclude?
A: I guess I don't understand your problem.  Either the "lemmas" need to be proven to be true (which is very possible) or they prove your statement almost trivially--maybe that's your question.
There are two predicates here:


*

* $p$: $a$ is odd/even 

* $q$: $a^2$ is odd/even 


Thus your lemmas are the following (let's assume "even" means "true" and "odd" means "false"):
Lemma 1: If $a$ is even (p) then $a^2$ is even (q)
$$
p \rightarrow q
$$
Lemma 2: If $a$ is not even ($\neg p$) then $a^2$ is not even ($\neg q$)
$$
\neg p \rightarrow \neg q
$$
Your assumption (the two lemmas) assumes the conclusion.  It's apparent from my formulation that you are trying to prove:
$$
p \leftrightarrow q
$$
This statement is true if both of your lemmas are true--but I would question how we know those lemmas to be true to be able to prove this statement.
