Question

is it possible to show using direct method that if n^2 is odd, then n is odd?

Answer 1

I'm not really a fan of proof by contradiction

Answer 2

use contrapositive

Answer 3

@perl, *direct method* :P

Answer 4

i don't know of a direct method, sorry

Answer 5

direct method is to show P->Q, assume P, then show Q.

Answer 6

why are you not a fan of contradiction?

Do you use counter examples to show something is not true?

Answer 7

because i tend to prove directly first before using contradiction

Answer 8

sometimes that's not possible

Answer 9

many of the theorems you are using to do any of these things were proved in non direct methods, so you are always sort of using a contradiction :)

Answer 10

But then again I also will stop the car and ask for directions ;)

Answer 11

If \(n^2\) doesn't have 2 as one of its factors, then \(n \) wouldn't either. (Why?)

Answer 12

I don't know if this says anything that will help, but I saw this section (in image below) in this article http://www.math.uiuc.edu/~hildebr/347.summer14/even-odd-proofs-sol.pdf

Answer 13

@ParthKohli n^2 = 2k + 1. Ok how does this implie n does not have 2 as a factor?

Answer 14

yes but why....

Answer 15

It does.

If a number doesn't have prime factor \(p_0\) in its prime factors, then why would any of its factors have \(p_0\) in their prime factors?

Answer 16

Not sure if this is a direct proof, but it's the best I could come up with...

Answer 17

I don't think you can end a proof with a question mark ;P

Answer 18

im just playing

Answer 19

perhaps it's sometimes really impossible to prove directly as @zzr0ck3r said. but I'd still like to think it's always possible though :/

Answer 20

I doubt it. I was just saying that some things are.

Answer 21

\[
n^2 = 2k+1\implies \frac{2k+1}{n}=n
\]An odd number divided by an even number is not an integer, therefore \(n\) must be odd.

Answer 22

If \(p\) does not divide \(k\), then \(p\) will not divide \(k_0\), a factor of \(k\).

Here, p = 2, \(k = n^2\) and \(k_0 = n\).

Answer 23

h hope that could help you
http://zimmer.csufresno.edu/~larryc/proofs/proofs.direct.html

Answer 24

Another direct proof method would be to examine each case. Either \(n\) is even or odd. If it can't be even, then it must be odd.

Answer 25

@wio very clever :)

Answer 26

there is hope that proving directly is always possible. it just take some cleverness :p. Thanks everyone ^^

Answer 27

There are many theorems in math that are proven by contradiction. Proving directly is not always possible. For instant, you wouldn't be able to get cantor's transfinite math if you do not use proof by contradiction. Same goes for many analysis results.

Answer 28

let n=2m-1,\(m\in \mathbb{Z}\)
\(\large\tt \begin{align} \color{black}{n=2m-1\\
n^2=4m^2-4m+1\\
n^2(mod~2)=(4m^2-4m+1)(mod~2)\\
n^2(mod~2)=(4m^2-4m+1)(mod~2)\equiv 1\\
n^2(mod~2)\equiv 1^2\\
n(mod~2)\equiv 1

}\end{align}\)
so n is odd

Answer 29

how did you go from n^2 (mod 2 ) = 1
to
n mod 2 = 1

Answer 30

that the theorm
if
\(a^k \equiv b^k~~ (mod ~n)\)
then
\(a\equiv b~~ (mod ~n)\)