Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How can we prove that integers can be defined as odd or even?

  1. Dec 16, 2015 #1
    Iam working through Spivak calculus now.
    The book defines natural numbers as of form N=1,2,3,4....
    Iam able to prove that every natural number is either odd or even. How can I extend to Z, integers?
    In one of the problems, Spivak says we can write any integer of the form 3n, 3n+1, 3n+2.( n is integer) He gives as hint to the problem.But am not convinced,
    In general how can we prove that if m is a natural number, n is an integer, then
    any integer can be expressed of the form km, km+1, km+2, km+3,.....,km+(k-1)?
     
  2. jcsd
  3. Dec 16, 2015 #2

    Erland

    User Avatar
    Science Advisor

    If you have a negative integer n = -m, and k>0, then there are integers q,r, with 0≤r<k such that m = kq + r.
    What can you then say about n?

    (Hint: r = k - (k - r) ).
     
  4. Dec 16, 2015 #3

    WWGD

    User Avatar
    Science Advisor
    Gold Member

    Like Erland suggested, it basically comes down to the fact that an integer m divided by n, can have possible remainders 0,1,...m-1. As he suggested, you can use the Euclidean algorithm to prove this.
     
  5. Dec 18, 2015 #4
    Spivak has not mentioned about Euclid algorithm. Could you help me with some other way?
     
    Last edited: Dec 18, 2015
  6. Dec 18, 2015 #5
    I did think of alternate proof like this. Let A be a set of integers which can't be expressed of the form 3n, 3n+1, 3n+2: where n is an integer
    Every non-null set of integers has a smallest member. Let it be s.
    Consider s-1. s-1 must be expressed of the form 3n, 3n+1, 3n+2. Orelse, it belongs to A, resulting in contradiction.
    Now the proof involves equating s-1 to either of these 3 forms: 3n, 3n+1,3n+2
    By equating we can easily find that, s is of the form 3n, 3n+1, 3n+2. Hence s does not belong to A. A is null set. So, every integer exists of this form.
     
  7. Dec 18, 2015 #6

    Samy_A

    User Avatar
    Science Advisor
    Homework Helper

    Nitpick:
    This is not correct. Every non-null set of natural numbers has a smallest member.

    Your proof only works for positive integers, but of course once you have it for positive integers, you can easily extend it to all integers (by considering -n if n is negative).
     
  8. Dec 18, 2015 #7
    Yeah...you are right....we can prove for natural numbers( postive integers) . For negative integers, we can sustidute -n. I tried proving s does not belong to A. I can easily prove -s does not belong to A. but what about s?
     
  9. Dec 18, 2015 #8

    Samy_A

    User Avatar
    Science Advisor
    Homework Helper

    You have established that each natural number n can be expressed as 3k, 3k+1 or 3k+2.
    If n is a negative integer, -n is positive. So -n can be expressed as 3k, 3k+1 or 3k+2.
    Just as an example, say -n=3k+1, then n=-3k-1.
    We don't like that -1, but that is easily fixed: n=-3(k+1)+3-1=3(-k-1)+2.

    But it really boils down to what @Erland and @WWGD said before: when you divide an integer by a natural number m, the remainder can only be 0,1,2, ..., m-1.
     
  10. Dec 18, 2015 #9
    nailed it...thanks
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: How can we prove that integers can be defined as odd or even?
  1. How can one prove (Replies: 4)

  2. How can you prove? (Replies: 9)

  3. How can prove this ? (Replies: 7)

Loading...