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

Proof via contradiction

  • #1

Homework Statement


For any integer n, let A(n) be the statement:
“If n 2 = 4k + 1 for some k ∈ Z, then n = 4q + 1 or 4q + 3 for some q ∈ Z.”

Use proof by contradiction to show that A(n) is true for all n ∈ Z.


The Attempt at a Solution


[/B]
the answer sheet says that since n !=4q+1 and n != 4q+3 implies that n = 4q or n = 4q+2. Im confused why n!=4q+1 and n != 4q+3 implies that n = 4q or n = 4q+2. Why only those two examples? couldn't n = 4q+x where x = 0,2,4,5,6,7,.... basically any integer that is not 1 or 3, since 'x' is defined to NOT be those with the proof via contradiction.
 

Answers and Replies

  • #2
12,683
9,214

Homework Statement


For any integer n, let A(n) be the statement:
“If n 2 = 4k + 1 for some k ∈ Z, then n = 4q + 1 or 4q + 3 for some q ∈ Z.”

Use proof by contradiction to show that A(n) is true for all n ∈ Z.


The Attempt at a Solution


[/B]
the answer sheet says that since n !=4q+1 and n != 4q+3 implies that n = 4q or n = 4q+2. Im confused why n!=4q+1 and n != 4q+3 implies that n = 4q or n = 4q+2. Why only those two examples? couldn't n = 4q+x where x = 0,2,4,5,6,7,.... basically any integer that is not 1 or 3, since 'x' is defined to NOT be those with the proof via contradiction.
You want to show ##n^2=4k+1 \Longrightarrow n=4q+1 \vee n=4q+3## by contradiction. This means we still have given ##n^2=4k+1## but assume ##(n=4q+1 \vee n=4q+3)## is false. So in order for an OR statement to be false, both components have to be false; otherwise the OR statement would be true. Now if ##(n=4q+1 \vee n=4q+3)## is false and so both have to be false, we assume ##(n\neq 4q+1 \wedge n\neq 4q+3)\,.##

Now which remainders for ##n## by division with ##4## are possible?
 
  • #3
You want to show ##n^2=4k+1 \Longrightarrow n=4q+1 \vee n=4q+3## by contradiction. This means we still have given ##n^2=4k+1## but assume ##(n=4q+1 \vee n=4q+3)## is false. So in order for an OR statement to be false, both components have to be false; otherwise the OR statement would be true. Now if ##(n=4q+1 \vee n=4q+3)## is false and so both have to be false, we assume ##(n\neq 4q+1 \wedge n\neq 4q+3)\,.##
yes i understand that, its just applying De Morgan's laws. But why does that imply that n=4q or n = 4q+2 ONLY? on the answer page it says "since n≠4q+1∧n≠4q+3, it follows that n = 4t or 4t + 2 for some t ∈ Z." My question is why do they say it follows that, that is the case? because how do we know n can be written in the form: n = 4q or 4q + 2 for some q ∈ Z? How do we know it couldn't be written as n = 4q+4 or something else?
 
  • #4
12,683
9,214
yes i understand that, its just applying De Morgan's laws. But why does that imply that n=4q or n = 4q+2 ONLY? on the answer page it says "since n≠4q+1∧n≠4q+3, it follows that n = 4t or 4t + 2 for some t ∈ Z." My question is why do they say it follows that, that is the case? because how do we know n can be written in the form: n = 4q or 4q + 2 for some q ∈ Z? How do we know it couldn't be written as n = 4q+4 or something else?
Sorry, I've edited my post while you posted yours. Consider the division of ##n## by ##4##.
 
  • #5
You want to show ##n^2=4k+1 \Longrightarrow n=4q+1 \vee n=4q+3## by contradiction. This means we still have given ##n^2=4k+1## but assume ##(n=4q+1 \vee n=4q+3)## is false. So in order for an OR statement to be false, both components have to be false; otherwise the OR statement would be true. Now if ##(n=4q+1 \vee n=4q+3)## is false and so both have to be false, we assume ##(n\neq 4q+1 \wedge n\neq 4q+3)\,.##

Now which remainders for ##n## by division with ##4## are possible?
0,2,4,8,12,16,... so on right?
 
  • #6
12,683
9,214
0,2,4,8,12,16,... so on right?
Only ##0## and ##2##. Any other integer has another multiple of ##4## and is swallowed by ##q##. The multiple ##q## isn't specified and can be any. Now e.g. ##n=4q+7=4(q+1)+3=4q' +3## or ##n=4q+12=4(q+3)+0=4q''\,.## The entire statement is all about the remainders by division with ##4\,.##
 
  • #7
Only ##0## and ##2##. Any other integer has another multiple of ##4## and is swallowed by ##q##. The multiple ##q## isn't specified and can be any. Now e.g. ##n=4q+7=4(q+1)+3=4q' +3## or ##n=4q+12=4(q+3)+0=4q''\,.## The entire statement is all about the remainders by division with ##4\,.##
That doesn't really make sense to me. Can any number in Z, (since that is what we are working with), be represented by 4q+x : x,z ∈ Z? Because it is for n ∈ Z.
 
  • #8
12,683
9,214
That doesn't really make sense to me. Can any number in Z, (since that is what we are working with), be represented by 4q+x : x,z ∈ Z? Because it is for n ∈ Z.
Yes, ##\mathbb{Z}## is a Euclidean ring, that means we have division with remainder: Given two integers ##x,y## there are always integers ##q,r## such that ##x=qy+r## with ##0\leq r < y##. Here we have given ##x=n## and ##y=4##. As I said, the specific value of ##q## isn't part of the statement, only its existence. The contradictory assumption is ## ... \neq 1,3## for all ##q\in \mathbb{Z}## as "for all" is the negation of "there is some", so we can use any ##q\,.##
 
  • #9
Yes, ##\mathbb{Z}## is a Euclidean ring, that means we have division with remainder: Given two integers ##x,y## there are always integers ##q,r## such that ##x=qy+r## with ##0\leq r < y##. Here we have given ##x=n## and ##y=4##. As I said, the specific value of ##q## isn't part of the statement, only its existence. The contradictory assumption is ## ... \neq 1,3## for all ##q\in \mathbb{Z}## as "for all" is the negation of "there is some", so we can use any ##q\,.##
Right, but I don't understand what you mean in post #6.
What is clear to me so far is this: For any n ∈ Z, n can be written in the following way, n = x*y + r, where x,y,r ∈ Z also.
Now given (in this example) that n != 4q+1 and n != 4q+3, (this is where i'm confused), Why wouldn't it follow that n = 4q + r where r ∈ Z \ {1,3}, or even n = x*y + r as long as the two cases where (x,r) = (4,1) and (4,3) are left out?
 
  • #10
12,683
9,214
Right, but I don't understand what you mean in post #6.
What is clear to me so far is this: For any n ∈ Z, n can be written in the following way, n = x*y + r, where x,y,r ∈ Z also.
Now given (in this example) that n != 4q+1 and n != 4q+3, (this is where i'm confused), Why wouldn't it follow that n = 4q + r where r ∈ Z \ {1,3}, or even n = x*y + r as long as the two cases where (x,r) = (4,1) and (4,3) are left out?
Because we can choose ##q## in such a way that ##0 \leq r < y=4##. So we are left with the cases ##r \in \{\,0,2\,\}\,.## In all other cases, we simply choose another ##q## such that we have ##r<4## again.
 
  • #11
12,683
9,214
$$
\lnot \,(\,\exists\, q\in \mathbb{Z}\, : \,n=4q+1 \vee n=4q+3)
\Longleftrightarrow
(\,\forall q\in \mathbb{Z}\, : \,n \neq 4q+1 \wedge n\neq 4q+3)
$$
The "for all" quantifier allows us to change the value of ##q## as it is supposed not to hold for all of them.
 

Related Threads on Proof via contradiction

  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
5
Views
3K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
4
Views
701
  • Last Post
Replies
5
Views
485
Replies
5
Views
2K
Replies
11
Views
3K
Replies
6
Views
1K
Top