Prove 2∤ 1

  • Thread starter beep
  • Start date
  • #1
beep
4
0
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
 

Answers and Replies

  • #2
Punkyc7
420
0
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
micromass
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
22,178
3,305
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
beep
4
0
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.

No mention of even or odd

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.

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
micromass
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
22,178
3,305
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
beep
4
0
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.

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
micromass
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
22,178
3,305
It looks good. I'm just wondering if case 3 can't be shortened:

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

But 1>0 and 2*y*(-1)<0. So the two can't equal eachother!
 
  • #8
beep
4
0
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!


Perfect. Thank you!
 

Suggested for: Prove 2∤ 1

Replies
20
Views
425
Replies
9
Views
212
  • Last Post
Replies
2
Views
39
  • Last Post
2
Replies
54
Views
2K
Replies
5
Views
364
Replies
12
Views
418
  • Last Post
Replies
5
Views
176
Top