Register to reply

If n is a natural number and n^2 is odd, then n is odd

by mrchris
Tags: natural numbers, proof
Share this thread:
mrchris
#1
Apr13-12, 02:14 AM
P: 31
1. The problem statement, all variables and given/known data
if n is a natural number and n2 is odd, then n is odd

2. Relevant equations
odd numbers: 2k+1, where k is an integer
even numbers: 2K, where k is an integer


3. The attempt at a solution
ok so take the opposite to be true, or n2 is odd and n is even. Then we would have n2= 2p+1 and n=2k, where p and k are both integers. then take n2= (2k)2= (22)(k2)= 4k2
Then set 2p+1= 4k2
4k2-2p=1
2(2k2-p)=1
(2k2-p)=1/2
but since we know 2k2 is an integer because it is just the product of 3 integers, 2*k*k, and we also know p is an integer by definition, we also know that (2k2-p) is an integer because it is the subtraction of two integers. This leaves us with a contradiction since we know (2k2-p) can not equal 1/2, hence proof is complete.
Phys.Org News Partner Science news on Phys.org
Hoverbike drone project for air transport takes off
Earlier Stone Age artifacts found in Northern Cape of South Africa
Study reveals new characteristics of complex oxide surfaces
Robert1986
#2
Apr13-12, 06:04 AM
P: 828
OK, I didn't really carefully look at your proof, but it seems to be correct.

HOWEVER, this is not a very satisfying proof. In Number Theory, we are VERY concerned with PRIME FACTORS of numbers. Now, I am going to give you two hints. Let [itex]n = p_1^{k_1}\cdots p_m^{k_m}[/itex] be the prime factorisation of [itex]n[/itex]. NOW, what is the prime factorisation of [itex]n[/itex] (just square the one for [itex]n[/itex]. That was hint #1. Here is hint #2: In terms of prime factors, what does it mean for a number to be odd or even?

Now, use prime factorisations and properties of primes to give what is essentially a 1 line proof.
HallsofIvy
#3
Apr13-12, 07:41 AM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,323
Statement: if n^2 is odd then n is odd.

Contrapositive: if n is even then n^2 is even.

Prove the statement by proving the contrapositive.
"if n is even" we can write n= 2k for some integer k. What is n^2?

(I would NOT use "prime factorization.)

Robert1986
#4
Apr13-12, 09:05 AM
P: 828
If n is a natural number and n^2 is odd, then n is odd

Quote Quote by HallsofIvy View Post
Statement: if n^2 is odd then n is odd.

Contrapositive: if n is even then n^2 is even.

Prove the statement by proving the contrapositive.
"if n is even" we can write n= 2k for some integer k. What is n^2?

(I would NOT use "prime factorization.)
Why not use prime factorisation? For example:

EDIT:
I gave the answer here. So I deleted it.


I didn't mean to suggest that he should write out the prime factorisation of [itex]n[/itex] as I did, I just did that to explain. The proof that I did have above was a direct proof (not that there is anything wrong with contrapositive) and is one line.
mrchris
#5
Apr14-12, 01:48 AM
P: 31
Thanks for the advice, both of your answers seem to make sense, but I am in an analysis class and I can only use what I've learned in the class so far in my proofs. We definitely haven't worked with prime factorization officially yet, so even though that argument may be more straight forward, I can't use it. As for the contrapositive, we havent learned that either (which seems weird to me because it is commonly used for analysis online), so that is off limits as well.
Robert1986
#6
Apr14-12, 05:13 AM
P: 828
???
This seems very strange to me. So you did learn (in an analysis class) that an odd number has the form 2k+1 but no one mentioned that integers have prime factorisations? And you are not allowed to use contrapositive?

Is this class on some odd schedule and is it just now beginning?


Register to reply

Related Discussions
Equation in natural number Linear & Abstract Algebra 4
Let m be a natural number ... Calculus & Beyond Homework 4
Natural number Precalculus Mathematics Homework 35
Natural number Engineering, Comp Sci, & Technology Homework 2
NCk is a natural number Linear & Abstract Algebra 18