1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove 2∤ 1

  1. Aug 29, 2012 #1
    Prove 2 ∤ 1 , assuming the existence of the natural numbers and integers along with their most basic arithmetical and ordering properties. (Not allowed to use rational numbers)



    2. Let and b be integers. We say a divides b if there exists an integer k such that ka = b.



    3. Well, my intuition says to start by saying that if a | b then there exiests an integer k such that 2*k = 1. Obviously such integer doesn't exist. I was thinking about using prop 6 (which I've already managed to prove on my on) from http://primes.utm.edu/glossary/xpage/divides.html to say If 2 divides 1 then 2 divides 1c for any integer c. Meaning 2 divides every integer, which it does not. I don't know if that's enough. Would appreciate some input
     
  2. jcsd
  3. Aug 29, 2012 #2
    Do you know that 1 is odd? If so,

    so 2k = 1. so this means 1 is even but one is odd. So you have contradiction.
     
  4. Aug 29, 2012 #3

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Try to use Proposition 6 to get that if 2|1, then 2<1. Try to construct a contradiction from that.

    I can't help any further until you mention the axioms you're using and the theorems you already proved yourself.
     
  5. Aug 29, 2012 #4
    No mention of even or odd

    Yes! I thought to try that first , but I was getting stuck. Partially because that comes with the next proposition I have to solve. Forgive me for being vague, this is my first proof based assignment for a class that started on Monday.

    Elementary Number Theor of N and Z
    In this workbook we assume the existence of the natural numbers and the integers alng with their most basic arithmetical and ordering properties. For example, we assume the truth of the statments such as "For all integers a nd b, a+b = b+a", " 0 < 1" and " For any pair of integers a and b, exactly one of the following is true: a = b, a < b , or a > b"

    Definition 1. Let a and b be integers. We say a divides b if there exists an integer k such that ka = b.

    I've proven:
    Proposition 3. Let, a, b, and c be integers. If a|b and a|c then a|(b+c)
    Proposition 4. Let a,b, and c be integers. If a|b and a|c then a|(b-c)
    Conjecture 5 (disproven). Let a, b, and c be integers. If a|(b+c) then a|b or a|c
    Proposition 6. Let a, b, and c be integers. If a|b then a|bc
    Proposition 7. Let d, a, b, x, and y be integers if d|a then d|b, then d|(ax + by)
    Proposition 8. Let a, b, and c be integers. If a|b and b|c then a|c

    -----------------------------------

    My first attempt said saying 2 > 1 . If 2 | 1, then there exists an integer k such that 2 * k = 1 . Since 2 and k are integers then 2 * k > k . Then, k is limited to a number less than 1. But I can't say that 2 * k > k just based on the fact they are integers alone because they could also be negative. I'd have to make the claim for "divides" apply to natural numbers. If i am able to also assume that if a and b are natural numbers and a | b then there exists a natural number k such that a * k = b ... I would be able to say the only natural number smaller than 1 is 0 and 2 * 0 ≠ 1

    But I dunno
     
  6. Aug 30, 2012 #5

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    First, try to prove that from 0<1 follows that 1<2.

    But if 2|1, then follows 2>1. This is a contradiction.

    Try something along these lines.
     
  7. Aug 30, 2012 #6
    Ok, I gave it a shot. Can anyone tell me if this would be valid?

    * 0 < 1 , so 0 (+1) < 1 (+ 1 ) and 1 < 2
    * If 2|1 then there exists an integer k such that 2 * k = 1

    Case 1

    * If k > 0, then 2*k ≥ 2
    * 1 < 2 , thus 2*k > 1
    * 2*k ≠ 1 , Thus 2 ∤ 1

    Case 2

    * If k = 0 then 2*k = 0
    * 0 < 1, Thus 2*k < 1
    * 2* k ≠ 1 , Thus 2 ∤ 1

    Case 3

    *If k < 0 , then there exists a natural number y for which y*(-1) = k
    * If 2*k = 1 , then 2*y*(-1)= 1
    * By Proposition 6, if 2 | 1, then 2 | (1 * c) , where c is any integer
    * If 2*k = 1 , then 2 *y*(-1) = 1 , and 2*y*(-1)*c = 1*c
    * Let c = -1. Then 2*y*(-1)*c = 1*c is 2* y = -1
    * y is a natural number, thus 2*y ≥ 2
    * 0 < 1 , so 0 (-1) < 1 ( -1) and -1 < 0 and -1< 0<1<2. Thus -1 < 2
    * 2*y*(-1)*c ≥ 2 , thus 2*y*(-1)*c ≠ 1*c and 2*k*c≠ 1*c
    *Thus 2∤1*c and 2∤1



    Thoughts???
     
  8. Aug 30, 2012 #7

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    It looks good. I'm just wondering if case 3 can't be shortened:

    But 1>0 and 2*y*(-1)<0. So the two can't equal eachother!
     
  9. Aug 30, 2012 #8

    Perfect. Thank you!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Prove 2∤ 1
  1. How to prove 1+1=2 (Replies: 6)

Loading...