Proof by direct method?

Question

Definition: An integer $n$ is throdd if $n=3k+1$ for some $k\in\Bbb Z$.

Proposition: For all integers $n$, if $n^2$ is throdd, then $n$ is throdd.

direct proof:

let $n$ be a particular but arbitrarily chosen throdd integer

then $n = 3k + 1$ for some $k \in \mathbb{Z}$

then $n^2 = (3k + 1)^2 = 9k^2 + 6k + 1 = 3(3k^2 + 2k) + 1$

$3k^2 + 2k$ is an integer by closure, $n^2$ meets the definition of threeven.

Wouldn't there be a counter example, or is there a way to prove it by contrapositive?

"throdd" is not a standard mathematical term. I think you mean "not divisible by $3$". — Robert Israel, Nov 03 '13 at 22:50
@RobertIsrael I think it is $3k+1$, and threevens are $3k+2$. I hope we won't have elevenevens or stuff like that in the future. — Lord Soth, Nov 03 '13 at 22:51
If it is $3k+1$, the statement is wrong: e.g. consider $2^2$. — Robert Israel, Nov 03 '13 at 22:52
Unless the teacher has defined the term and said definition is included here, this will probably be closed as "unclear what you're asking". Don't worry, though; it can always be reopened once you've figured that out. — dfeuer, Nov 03 '13 at 22:54
@RobertIsrael, maybe it's related to PEBKAC (problem exists between keyboard and chair). — dfeuer, Nov 03 '13 at 22:55
A throdd integer is an integer of the form $3k+1$ for some $k\in\Bbb Z$, as John’s earlier question. PBAC is particular but arbitrarily chosen. — Brian M. Scott, Nov 04 '13 at 05:55

score 2 · Answer 1 · answered Nov 04 '13 at 09:45

You can’t start by assuming that $n$ is throdd: that’s what you’re trying to prove, so any such argument would be circular. For a direct proof you should assume that $n^2$ is throdd, and for a proof of the contrapositive you should assume that $n$ is not throdd and try to prove that $n^2$ is not throdd. That looks more promising, so you might try it. If $n$ is not throdd, then $n$ is not $3k+1$ for any $k\in\Bbb Z$, and therefore either $n=3k$ for some $k\in\Bbb Z$, or $n=3k+2$ for some $k\in\Bbb Z$. If $n=3k$, then $n^2=(3k)^2=9k^2=3(3k^2)$, so $n^2$ is not throdd, just as we hoped to find.

Now investigate what happens if $n=3k+2$. Is $n^2$ always throdd? Never throdd? Sometimes throdd and sometimes not? If it’s never throdd, you’ve proved the proposition; in either of the other two cases you can find a counterexample to show that the proposition isn’t always true.

Proof by direct method?

1 Answers1