4
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ 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)". $\endgroup$ – Mauro ALLEGRANZA Jul 3 '17 at 15:44
  • 1
    $\begingroup$ 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. $\endgroup$ – Hagen von Eitzen Jul 3 '17 at 15:46
  • $\begingroup$ It is by the definition of divisibility... so k = 16j, means that 16 | k. $\endgroup$ – 1011011010010100011 Jul 3 '17 at 15:46
  • $\begingroup$ 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)$$ $\endgroup$ – Dave Jul 3 '17 at 15:47
  • 1
    $\begingroup$ 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$, $\endgroup$ – David Wheeler Jul 3 '17 at 15:48
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – fleablood Jul 3 '17 at 16:57
  • $\begingroup$ @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. $\endgroup$ – aras Jul 3 '17 at 16:59
  • $\begingroup$ 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. $\endgroup$ – fleablood Jul 3 '17 at 17:21
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – fleablood Jul 3 '17 at 17:27
  • $\begingroup$ @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. $\endgroup$ – Ennar Jul 3 '17 at 17:46
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
-2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.