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

[UOAMCBURGER]

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.

 

[fresh_42]

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?

 

[UOAMCBURGER]

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?

 

[fresh_42]

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

 

[UOAMCBURGER]

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?

 

[fresh_42]

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\,.$

 

[UOAMCBURGER]

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.

 

[fresh_42]

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\,.$

 

[UOAMCBURGER]

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?

 

[fresh_42]

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.

 

[fresh_42]

$$
\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.