# Proof by Contradiction: Converse of A(n) Holds for All n ∈ Z

• UOAMCBURGER
In summary: I did NOT intentionally write it as n 2 ... thats how it showed up in the proof. thanks for catching that!

## 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:
UOAMCBURGER said:
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:
tnich said:
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##

tnich said:
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.

UOAMCBURGER said:

## 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.

Ray Vickson said:
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 ...

## 1. What is proof by contradiction?

Proof by contradiction is a mathematical proof technique in which we assume the opposite of what we want to prove and then show that this assumption leads to a contradiction. This allows us to conclude that our original statement must be true.

## 2. When is proof by contradiction used?

Proof by contradiction is often used when a direct proof or other proof techniques are not available. It is particularly effective in proving statements involving the logical operators "and" and "or".

## 3. How does proof by contradiction work?

First, we assume the opposite of what we want to prove. Then, we use logical reasoning and mathematical principles to show that this assumption leads to a contradiction. This contradiction proves that our original statement must be true.

## 4. What are the limitations of proof by contradiction?

Proof by contradiction can only be used to prove statements that are either true or false, but not both. In addition, it may not always provide the most elegant or efficient proof.

## 5. Can proof by contradiction be used in fields other than mathematics?

Yes, proof by contradiction can be used in other fields such as philosophy and computer science. In philosophy, it is used to prove the validity of arguments. In computer science, it is used to prove the correctness of algorithms.