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
fresh_42
Mentor
Insights Author
2021 Award
16,628
15,893

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
fresh_42
Mentor
Insights Author
2021 Award
16,628
15,893
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
fresh_42
Mentor
Insights Author
2021 Award
16,628
15,893
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
fresh_42
Mentor
Insights Author
2021 Award
16,628
15,893
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
fresh_42
Mentor
Insights Author
2021 Award
16,628
15,893
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
fresh_42
Mentor
Insights Author
2021 Award
16,628
15,893
$$
\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
932
  • Last Post
Replies
5
Views
3K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
5
Views
776
Replies
32
Views
205
Replies
11
Views
4K
  • Last Post
Replies
10
Views
2K
Top