4

the proof at hand is:

Prove that for any $n > 0$, if $a^n$ is even, then $a$ is even.

Hint: Contradiction

So I know to start the problem in a contradiction format would be: $a^n$ is even, then $a$ is odd so that $a = 2k+1$. Then plug in that into $a^n$, we get $(2k+1)^n$. This is where I become stuck.

Thanks in advance!

Community
  • 1
sparky123
  • 73
  • 1
    This is equivalent to showing that if $a$ is odd, then $a^n$ for all $n>0$ is odd. Which is pretty easy via binomial expansion, since every term except $1$ has a factor of $2k$ for some $k$. – Rushabh Mehta Jan 26 '20 at 18:09
  • Alright, thank you. I understand that in a binomial theorem, we'd have the equation, a^(n-k)b$^k$. Would you mind elaborating how you'd use that formula in proving this? – sparky123 Jan 26 '20 at 18:18
  • If $a^n$ is even for any $n$, then in particular for $n=1$. So $a$ is even. Or do you mean, if for some $n>0$ we have that $a^n$ is even? – Dietrich Burde Jan 26 '20 at 19:17

6 Answers6

2

Hint: expand using the binomial theorem.

Patrick Stevens
  • 36,135
1

$$(2k+1)^n=2q+1\quad,\quad \text{for some }q\in\Bbb Z$$since$$(2k+1)^n{=\sum_{i=0}^n(2k)^i\\=1+\sum_{i=1}^n(2k)^i\\=1+2\cdot\sum_{i=1}^n2^{i-1}\cdot k^i\\=1+2q}$$

Mostafa Ayaz
  • 31,924
  • So then is it necessary to even show anything before you come to this conclusion that q is some integer? Because I know this a is a key part of the proof, but I just didnt know how to get to his point. I could easily prove this problem if it was just n$^2$. Thanks! – sparky123 Jan 26 '20 at 18:22
  • You can only simply use the binomial expansion as $$(a+b)^n=\sum_{k=0}^n \binom{n}{k}a^kb^{n-k}$$to show that step. – Mostafa Ayaz Jan 26 '20 at 18:25
  • Yes, would you be able to show that in use here? It would be appreciated! – sparky123 Jan 26 '20 at 18:29
  • Would it be a$^n$ = 2k$^{n-0}$ * 1$^0$ + 2k$^{n-1}$ 1$^{1}$ + 2k$^{n-2}$ 1$^{2}$ + ... + 2k$^{n-k}$ *1$^{n-k}$? – sparky123 Jan 26 '20 at 18:41
  • I added more details. Hope it help now!! – Mostafa Ayaz Jan 26 '20 at 19:01
1

By Euclid's lemma, if $2|a^n$ then $2|a$ or $2|a$ or $2|a$ or ... or $2|a$,

so we conclude that $2|a$.

J. W. Tanner
  • 60,406
1

The contrapositive is that $$a \text{ odd }\implies a^n \text { odd}$$

Use induction here: if $a^1=2k_1+1$, then $a^2=(2k_1+1)^2=2(2k_1^2+2k_1)+1=2k_2+1$ hence true for $n=2$

Then assume true for $n=m$, $(2k_1+1)^m=2k_m+1$

Then $$(2k_1+1)^{m+1}=(2k_m+1)(2k_1+1)=4k_mk_1+2k_m+2k_1+1=2(2k_mk_1+k_m+k_1)+1$$

Hence true with $k_{m+1}=2k_mk_1+k_m+k_1$

Rhys Hughes
  • 12,842
0

You can prove this by induction:

For $n=1$ the claim is clear.

Assume that if $a^n $ is even then $a $ is even.

Let $a^{n+1}$ be even. Then:

$a^{n+1} = a a^n$ .

If a is not even, then $a^n$ must be even because otherwise their product won't be even.

But then , by the induction hypothesis , $a$ is even, contradiction.

So $a$ must be even, as wanted.

infinity
  • 946
0

Prove by contradiction : If $a^n$ is even then a is an odd number.

We have : a = 2k + 1 By assumption above : $(2k+1)^n$ = 2q for all q $\in$ Z

Using binomial theorem we have : $(2k+1)^n$ = $\sum_{i = 0}^n C_i^n(2k)^i$ = 1 + 2$\sum_{i = 1}^n C_i^n(2k)^{i - 1}$.

We can derive that q is a rational number contradicting the fact that q is an integer.

Lê Lâm
  • 11