The validity of my proof for the following statement: for any integer $n$ larger than $0$, prove that if $a^n$ is even, $a$ has to be even as well

Question

I know that this is a trivial question, but I have never done any serious proofs before and therefore I am a complete novice when it comes to that part of math.

Anyhow, I used the "prove by contradiction" technique and my proof is the following:

Proof:

We use proof by contradiction. Suppose that there exists an integer $n > 0$ for which $a^n$ is even, with $a$ being an odd integer larger than $0$.

We notice that if it is indeed even $a^n$ can be written as $(2k)^n$ with $k$ being any positive integer.

Now let's look at possible values of $n$. If $n$ is $1$ then we already have a contradiction, because if $a^1$ is even, which is stated in the problem, $a$ has to be even as well. We conclude that $n$ has to be larger than $1$. Again, we write $a^n$ as $(2k)^n$ and we realize that, for us to get the value of $a$ and check if it's even we have to take the $n$th root of $a^n$. We do exactly that and we reach the following: $a = 2k$ which represents a contradiction.

Therefore, we have proved that if $a^n$ is even, so is $a$. $QED$

Any feedback on this proof and its validity would be highly appreciated.

Answer 1

You can prove that by induction in n.

To $n = 1$, we have $a^{1}$ is even, then, trivially, $a$ is even.

Suppose that if $a^{n}$ is even, then $a$ is even. Let's prove that $a^{n+1}$ is even then, $a$ is even.

Consider that $a^{n+1} = 2k$, $k \in \mathbb{N}.$ Observe that,

$$2k = a^{n+1} = a^{n}a$$

Then, $a^{n}$ is even or $a$ is even. If $a$ is even, we conclude our proof. If $a^{n}$ is even, we can use the induction hypothesis.

Answer 2

In my opinion, a proof by contraposition is very natural here.

Required to prove: $a^n$ is even implies $a$ even.

Contrapositive is: $a$ is odd implies $a^n$ odd.

Let $a = 2k+1$. Now using binomial theorem, it's easy to see that $a^n$ is the sum of even numbers plus $1$, making it odd. The statement is proved by contraposition.

EDIT:

A proof by contradiction was requested. Actually proof by contraposition is easy to transform into a proof by contradiction.

In this case one has to show $a^n$ even implies $a$ even. Assume, to the contrary, that an odd $a=2k+1$ exists such that $a^n$ is even. Again, proceeding by binomial theorem, we can show $a^n$ is odd. Meaning there is a number that is simultaneously odd and even. Contradiction. Hence such an odd $a$ cannot exist and $a$ must be even.

Answer 3

A short proof

We claim that $a^n=even$ cannot hold for odd $a$.

Let $d$ denote the unit's digit of odd $a$ then $d=1,3,5,7 or 9$. This implies $a^n$ has $1,3,5,7 or 9$ at its unit's digit for all $n\in \mathbb N$.

Answer 4

Your first mistake as

We notice that if it.. [$a^n$].... is indeed even an can be written as $(2k)^n$ with k being any positive integer.

That is assuming that $a$ is even as well. SO $a = 2k$ and $a^n = (2k)^n$. But this is assuming what you want to prove.

If you are assuming $a^n$ is even then you are assuming $a^n =2k$.

But if you are assuming is that $a$ is ODD so $a$ can be written as $a = 2j + 1$ and therefore $a^n = (2j + 1)^n$.

A good bit of contradiction would be to prove that if $a^n = (2j+1)^n$ that $a^n$ must be odd. A contradiction. Can you do that?

======

Actually my way when I was young would be a quasi induction bootstrap.

Lemma: And odd number times an odd number is odd.

Proof: If $a = 2k + 1$ and $b= 2j + 1$ then $ab = (2k+1)(2j+1) = 4jk + 2j + 2k + 1 = 2(2jk+j+k) + 1$ is odd.

So if $a$ is odd then $a^2 = a*a$ is odd. And $a^3 = a^2*a$ is odd. And continuing for as long as we need we get $a, a^2, a^3, a^4, a^5,......$ are all odd.

(I don't know if you've formally been introduced to Proof By Induction; but basically if you can prove something for a basic case, and you can prove a "bootstrapping" method to get from one case to the next, it makes sense that you can start from the base and bootstrap as many as you need to get to all the cases.)

I suppose another way to do this is $(2k + 1)^n = 2^nk^2 + n*2^{n-1}k^{n-1} + ...... + 2k + 1$ and prove that all but the last terms are even. That might be overkill and relies messily on the binomial theorem.

A rather sophisticated proof by contradiction might be:

Suppose $a$ is odd but $a^n$ is even. $a^1$ is odd. And $a^2=a*a$ is odd. But $a^n$ is even. That means sense the powers of $a$ start of as odd but sometime turn even then there must be some very first power of $a$ where $a^k$ is even but every lower power is odd. So $a^{k-1}$ is odd. ANd $a$ is odd but $a^k = a^{k-1}a$ would also have to be odd. So there can't be a first power where $a^k$ is even. SO all $a^n$ are odd.