• Support PF! Buy your school textbooks, materials and every day products Here!

Prove 2∤ 1

  • Thread starter beep
  • Start date
  • #1
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
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
22,097
3,280
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
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
22,097
3,280
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
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
22,097
3,280
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
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!
 

Related Threads on Prove 2∤ 1

  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
4
Views
3K
Replies
4
Views
4K
Replies
1
Views
3K
  • Last Post
Replies
7
Views
2K
Replies
1
Views
13K
  • Last Post
Replies
1
Views
2K
Replies
2
Views
614
Replies
3
Views
1K
  • Last Post
Replies
16
Views
2K
Top