# Homework Help: Prove 2∤ 1

1. Aug 29, 2012

### beep

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. Aug 29, 2012

### Punkyc7

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.

3. Aug 29, 2012

### micromass

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.

4. Aug 29, 2012

### beep

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

5. Aug 30, 2012

### micromass

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.

6. Aug 30, 2012

### beep

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???

7. Aug 30, 2012

### micromass

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!

8. Aug 30, 2012

### beep

Perfect. Thank you!