# What is wrong with my proof: if $c^4$ is not divisible by 16, then c is odd?

Prove that if $c^4$ is not divisible by $16$, then $c$ is odd.

Proof

By contraposition, let $c$ be an even integer, such that $c=2k$ for some integer $k$.

Then, by substitution,

$(2k)^4 = 16j$, for some integer j, by the definition of divisibility.

Then,

$(2k)^4 = 16j$

$= 16k^4 = 16j$

$= 16b = 16j$, where $b$ is an integer and $b=k^4$

Hence, by divisibility, $b=j$, which are both integers.

Therefore, by contrapositivity, if $c^4$ is not divisible by $16$, then c is odd.

What is wrong with this proof? This was the answer I wrote down on an exam and only got partial credit. Where am I going wrong? Did I assign too many variables?

Thanks!

• The proof must end with the third line, that reads: "if $c$ is even (i.e. not-odd), then $c^4$ is divisible by $16$". Thus, contraposing it: "if $c^4$ is not divisible by $16$, then $c$ is not even (i.e. odd)". – Mauro ALLEGRANZA Jul 3 '17 at 15:44
• How do you conclude in the beginning that $(2k)^4$ can be written as $16j$ if not by the very calculation that follows (where then $j$ turns out to be $j$)? - Apart from that, you show that if $c$ is even, $c=2k$ say, then $c^4=(2k)^4=16\cdot k^4$ is a multiple of $16$; hence by contraposition, if $c^4$ is not a multiple of 16, then $c$ is not even. – Hagen von Eitzen Jul 3 '17 at 15:46
• It is by the definition of divisibility... so k = 16j, means that 16 | k. – 1011011010010100011 Jul 3 '17 at 15:46
• The proof could be even shorter. Using the contrapositive, we have $$c=2k\implies c^4=(2k)^4=16k^4$$since $k^4$ is an integer, we have that $16\mid c^4$. Thus, we have $$(\exists k\in\Bbb Z:c=2k\implies 16\mid c^4)\iff (16\nmid c^4\implies\not\exists k\in\Bbb Z:c=2k)$$ – Dave Jul 3 '17 at 15:47
• You've got the order of things slightly mixed-up in your proof, you need to show $c^4 =(2k)^4$ implies $(2k)^4 = 16j$, not start with that. This is as simple as: $c^4 = (2k)^4 \implies c^4 = 2^4k^4 = 16k^4$, – David Wheeler Jul 3 '17 at 15:48

The essence of your argument is correct. You probably lost points for using too many variables. Ideally, a math proof should be as easy to understand as possible. That means using as little notation as possible.

Here's how I might write the proof:

Let $c$ be an even integer. Then there exists an integer $k$ such that $c = 2k$. Thus, $c^4 = (2k)^4 = 16k^4$. Since $k$ is an integer, $k^4$ is an integer. Therefore, $c^4$ is divisible by $16$. This completes the proof.

You probably didn't get full credit on the exam because you didn't explicitly state that $c^4$ is divisible by $16$. That is the most important step of the proof. You proved this (you wrote $(2k)^4 = 16j$), but you should have explicitly written it out.

• I'd be a lot more critical than that the statement "$(2k)^4 = 16j$" is precisely what needs to be proven and can not be stated as a given. I would give partial credit as the prove that $(2k)^4 = 16b;b=k^4$ is absolutely correct. But then the bit about showing $b=j$ is not nesc., kind of weird, and actually nonsense as $j$ never existed and was unknown in the first place. – fleablood Jul 3 '17 at 16:57
• @fleablood I agree with what you're saying...I meant that in a more general sense. OP recognized that $(2k)^4$ was divisible by 16 because it can be written as $16\cdot \text{some integer}$. The execution of the proof was flawed, but the crux of the proof idea was there. – aras Jul 3 '17 at 16:59
• I'd give the OP partial credit about 3/4. But I think the loss of full credit is not because of too many variables (which is only style) or not mentioning $c^4 = (2k)^4$ (which is implicit), but by a statement of stating what is to be proven as a premise. That is simply wrong. Fortunately the OP did the full proof anyway and avoided circular reasoning. yes, the crux is there but the reason he go partial credit was stating a conclusion as a premise, and not variables and nonspecifity. – fleablood Jul 3 '17 at 17:21

Let $A\equiv \text{$c$is even}$, $B\equiv \text{$c^4$is divisible by$16$}$. The original statement if of the form $\neg B\implies\neg A$ and thus, the contrapositive is $A\implies B$.

However, what you proved is $A\wedge B\implies B$:

By contraposition, let $c$ be an even integer, such that $c=2k$ for some integer $k$. [here you assume $A$]

Then, by substitution,

$(2k)^4 = 16j$, for some integer j, by the definition of divisibility. [here you assume $B$]

(parts in italics added by me)

If you wanted to make this work, you should drop assumption that $j$ is an integer and assume that it is some rational. Later when you write $b = j$, you get that $j$ is not just a rational, but integer number as well, and hence desired result is proven.

• Hmm, you could do: Let $(2k)^4 = 16j$ and conclude $16k^4 = 16j \implies j = k^4$ and so $j \in \mathbb Z$ but I imagine it'd be a lot more direct to just forget $j$ altogether and do $(2k)^4 = 16k^4$ and $k^4$ is an integer. The only reason j was introduced at all is because the OP was stating what was to be proven as a premise rather than a conclusion. – fleablood Jul 3 '17 at 17:27
• @fleablood, well, that is what I said. I focused on the proof by OP, the other answers already stated direct ways to prove the claim, there was no need to repeat them. – Ennar Jul 3 '17 at 17:46

There are two things wrong with you proof. (And many things right as well... but two things wrong).

"By contraposition, let $c$ be an even integer, such that $c=2k$ for some integer $k$.

Then, by substitution,

$(2k)^4=16j$ , for some integer $j$, by the definition of divisibility."

This is wrong because you don't know that $c^4 = 16j$ for some integer $j$. This is precisely what you need to prove. It is not a given.

So

"$(2k)^4 = 16j$". No, you don't know that any $j$ exist so don't put this in terms of $j$. Assume nothing and calculate $(2k)^4$.

Like so:

$(2k)^4 =$

$2^4k^4 =$

$16k^4=$

$16b$ for $b = k^4$.

And that's it. $b = k^4$ is an integer and $c^4 = 16b$

Leave out the $16j$ which you never had in the first place.

"Hence, by divisibility, b=j, which are both integers. "

That's rather meaningless as $j$ never existed. But also it doesn't matter whether $b = j$ or $b$ is some other integer altogether, just so long as $b$ is an integer. And $b$ is an integer because k is an integer. Not because $j$ is.

If you knew $j$ existed in the beginning you wouldn't need to do any proof at all! Simply say $(2k)^4 = 16j$ and that's that. But that's not a proof. That's simply a statement without justification.

The line after "by substitution" is not clear, but it appears to be assuming divisibility, because you say "by divisibility". There's no need for the $j$ here. You need to show that $(2k)^4$ is divisible by $16$, so just note that $(2k)^4 = 16k^4$ and $k^4$ is an integer. So by definition of divisibility, $16$ divides $(2k)^4$ and that proves your contrapositive.

We can compute this using far fewer variables:

Set $c=2k$, and thus $c$ is even.

Now we can see that $(2k)^4=2^4k^4=16k^4$ which is clearly divisible by $16$

Now we set $c=2j+1$, and thus $c$ is odd.

Now we can show that $(2j+1)^4 = 16 j^4 + 32 j^3 + 24 j^2 + 8 j + 1$ which we can see is not divisible by $16$

Therefore, if $c$ is not divisible by $16$ then $c$ is odd.