Why Must n Equal 4q or 4q+2 If It Isn't 4q+1 or 4q+3?

AI Thread Summary
The discussion centers on proving that if n² = 4k + 1 for some integer k, then n must be in the form of 4q + 1 or 4q + 3 for some integer q. The confusion arises from why the conditions n ≠ 4q + 1 and n ≠ 4q + 3 imply that n can only be 4q or 4q + 2. It is clarified that when n is divided by 4, the only possible remainders left that do not fall into the excluded categories are 0 and 2. The proof relies on the properties of integers in a Euclidean ring, emphasizing that all integers can be expressed in terms of multiples of 4, thus confirming the original statement. The conclusion reinforces that only the forms 4q and 4q + 2 remain valid under the given conditions.
UOAMCBURGER
Messages
31
Reaction score
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. I am 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.
 
Physics news on Phys.org
UOAMCBURGER said:

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. I am 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?
 
fresh_42 said:
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?
 
UOAMCBURGER said:
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##.
 
fresh_42 said:
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?
 
UOAMCBURGER said:
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\,.##
 
fresh_42 said:
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.
 
UOAMCBURGER said:
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\,.##
 
fresh_42 said:
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
UOAMCBURGER said:
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
$$
\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.
 

Similar threads

Proof by contrapositive; if (m^2+n^2) div by 4, then m,n are even numbers
Replies
1
Views
3K
Prove that ## n ## must be a power of ## 2 ##
Replies
15
Views
2K
Prove that ## a^{({2}^{n})}\equiv 1\pmod {2^{n+2}} ## for any ##n##?
Replies
6
Views
2K
Prove that ##5 | (2^n a) \rightarrow (5 | a)##for any ##n##
Replies
10
Views
3K
Proof That an Integer is Divisible by 2
Replies
3
Views
2K
For ## n>1 ##, show that every prime divisor of ## n+1 ## is an odd integer
Replies
9
Views
2K
Given that ## p\nmid n ## for all primes ## p\leq \sqrt[3]{n} ##
Replies
4
Views
2K
Prove that there are infinitely many primes of the form ## 6k+1 ##?
Replies
12
Views
3K
For n>3, show that the integers n, n+2, n+4 cannot all be prime
Replies
27
Views
3K
Prove that ## aa_{1}, aa_{2}, ...., aa_{n} ## is also a complete set?
Replies
14
Views
2K

Hot Threads

Recent Insights

Back
Top