Proof by contradiction

  • #1

Homework Statement


“If n = 3q + 1 or n = 3q + 2 for some q ∈ Z, then n 2 = 3t + 1 for some t ∈ Z.”
Use proof by contradiction to show that the converse of A(n) is true for all n ∈ Z.
For the proof by contradiction, on the answer sheet provided they have assumed n^2 = 3t+1 but n != 3q+1 and n != 3q+2.

Is it possible to have a valid proof by contradiction if you were to assume n = 3q+1 or n = 3q+2 is true for some n in Z, but n^2 != 3t+1 and then show that you can get n^2 into the form 3(.t..) + 1 ? where 3(.t..) is just obviously some multiple of 3... Hence a contradiction.?
 
Last edited by a moderator:

Answers and Replies

  • #2
tnich
Homework Helper
1,048
336
Is it possible to have a valid proof by contradiction if you were to assume n = 3q+1 or n = 3q+2 is true for some n in Z, but n^2 != 3t+1 and then show that you can get n^2 into the form 3(.t..) + 1 ? where 3(.t..) is just obviously some multiple of 3... Hence a contradiction.?
This would not be a proof by contradiction. It would just be proving the statement “If n = 3q + 1 or n = 3q + 2 for some q ∈ Z, then n 2 = 3t + 1 for some t ∈ Z” directly. The assumption that n^2 ##\ne## 3t+1 would be superfluous.
 
Last edited by a moderator:
  • #3
tnich
Homework Helper
1,048
336
This would not be a proof by contradiction. It would just be proving the statement “If n = 3q + 1 or n = 3q + 2 for some q ∈ Z, then n 2 = 3t + 1 for some t ∈ Z” directly. The assumption that n^2 ##\ne## 3t+1 would be superfluous.
Also, the problem is to prove the converse, not the original statement. So what you need to prove is
##\forall t, n \in \mathbb Z ## such that ## n^2=3t+1, \exists q \in \mathbb Z ## such that ## n=3q+1## or ##n=3q+2##
 
  • #4
Also, the problem is to prove the converse, not the original statement. So what you need to prove is
##\forall t, n \in \mathbb Z ## such that ## n^2=3t+1, \exists q \in \mathbb Z ## such that ## n=3q+1## or ##n=3q+2##
oh that is why i was getting confused, because given statement A>B for a proof by contradiction you get A>~B and show some contradiction, hence my question about the order of the proof. I see what i've done, thanks.
 
  • #5
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728

Homework Statement


“If n = 3q + 1 or n = 3q + 2 for some q ∈ Z, then n 2 = 3t + 1 for some t ∈ Z.”
Use proof by contradiction to show that the converse of A(n) is true for all n ∈ Z.
For the proof by contradiction, on the answer sheet provided they have assumed n^2 = 3t+1 but n != 3q+1 and n != 3q+2.

Is it possible to have a valid proof by contradiction if you were to assume n = 3q+1 or n = 3q+2 is true for some n in Z, but n^2 != 3t+1 and then show that you can get n^2 into the form 3(.t..) + 1 ? where 3(.t..) is just obviously some multiple of 3... Hence a contradiction.?
Is n 2 supposed to be ##n^2?## If so, write it properly, as n^2.
 
  • #6
Is n 2 supposed to be ##n^2?## If so, write it properly, as n^2.
yes its meant to be n2, and obviously I did NOT intentionally write it as n 2 ...
 

Related Threads on Proof by contradiction

  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
5
Views
3K
  • Last Post
Replies
4
Views
761
Replies
5
Views
2K
Replies
11
Views
3K
Replies
6
Views
1K
  • Last Post
Replies
10
Views
1K
Top