Mixing
![How to find an angle of a triangle that has three points of tangency? [closed]](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhZCTB4-bb-s-32SAm6ytjzFOU06cH9o8q-a_wq_UnH6lcd8hvws23CmBWHM6g256LzTX9yK1EiCCzTC1NSgtxlNk_J9hdr9bA3tD0Nqntbl521j4bLAm_uXPANuWLBhcCKTKzns2gaUodx/s72-c/1.jpg)
Proof that if $n^2-1$ is divisible by $8$ then $n$ is odd
Clash Royale CLAN TAG#URR8PPP
up vote
4
down vote
favorite
I am still very new to proofs. I am just getting some practice, as I am still struggling with the concepts. Any feedback would be greatly appreciated. Thank you in advance.
Claim: If $n^2-1$ is divisible by $8$, then $n$ is odd.
Proof: Suppose $n$ is even; that is, $n=2k$, for some $k in mathbbZ$. Then, $n^2-1 = (2k)^2-1$, which is odd. Therefore, $n$ must be odd and thus, contradicts our assumption that $n$ is even.
This is my second practice proof I am working on so please be gentle! I am still learning the logic and working through the proofs slowly. Any feedback, tips, or hints/tricks would be greatly appreciated! Thanks.
elementary-number-theory proof-verification proof-writing
edited Jul 27 at 9:31
user21820
35.8k440136
asked Jul 27 at 3:58
Ryan
865
 |Â
show 2 more comments
up vote
4
down vote
favorite
I am still very new to proofs. I am just getting some practice, as I am still struggling with the concepts. Any feedback would be greatly appreciated. Thank you in advance.
Claim: If $n^2-1$ is divisible by $8$, then $n$ is odd.
Proof: Suppose $n$ is even; that is, $n=2k$, for some $k in mathbbZ$. Then, $n^2-1 = (2k)^2-1$, which is odd. Therefore, $n$ must be odd and thus, contradicts our assumption that $n$ is even.
This is my second practice proof I am working on so please be gentle! I am still learning the logic and working through the proofs slowly. Any feedback, tips, or hints/tricks would be greatly appreciated! Thanks.
elementary-number-theory proof-verification proof-writing
edited Jul 27 at 9:31
user21820
35.8k440136
asked Jul 27 at 3:58
Ryan
865
2
Where did you use the assumption "$n^2-1$ is divisible by $8$"? Also, how can you justify the sentence "Therefore, $n$ must be odd" ?
– Suzet
Jul 27 at 4:01
@Suzet It was unnecessary since the OP approached via contradiction.
– JMoravitz
Jul 27 at 4:02
2
@ Ryan, you could have explained better why $(2k)^2-1$ being odd implies that $8$ is not a divisor of $n^2-1$. You seem to have glossed over this step which can be fleshed out. (Note that since $2mid 8$ and supposing that $8mid n^2-1$ this should have implied something about the parity of $n^2-1$)
– JMoravitz
Jul 27 at 4:05
This contradiction shows that $n$ must atleast be odd for it to be divisible by $8$. But it doesn't guarantee that if $n$ is odd $n^2-1$ is divisible by $8$. I think the proof is ok if you only want to prove the forward implication.
– Piyush Divyanakar
Jul 27 at 4:06
@JMoravitz Actually, either the OP is proving the proposition by contraposition (where we do not have $n^2-1$ divisible by $8$), either the OP is proving it by contradiction (where we have and need to use $n^2-1$ is divisible by $8$).
– Suzet
Jul 27 at 4:06
 |Â
show 2 more comments
up vote
4
down vote
favorite
up vote
4
down vote
favorite
I am still very new to proofs. I am just getting some practice, as I am still struggling with the concepts. Any feedback would be greatly appreciated. Thank you in advance.
Claim: If $n^2-1$ is divisible by $8$, then $n$ is odd.
Proof: Suppose $n$ is even; that is, $n=2k$, for some $k in mathbbZ$. Then, $n^2-1 = (2k)^2-1$, which is odd. Therefore, $n$ must be odd and thus, contradicts our assumption that $n$ is even.
This is my second practice proof I am working on so please be gentle! I am still learning the logic and working through the proofs slowly. Any feedback, tips, or hints/tricks would be greatly appreciated! Thanks.
elementary-number-theory proof-verification proof-writing
edited Jul 27 at 9:31
user21820
35.8k440136
asked Jul 27 at 3:58
Ryan
865
I am still very new to proofs. I am just getting some practice, as I am still struggling with the concepts. Any feedback would be greatly appreciated. Thank you in advance.
Claim: If $n^2-1$ is divisible by $8$, then $n$ is odd.
Proof: Suppose $n$ is even; that is, $n=2k$, for some $k in mathbbZ$. Then, $n^2-1 = (2k)^2-1$, which is odd. Therefore, $n$ must be odd and thus, contradicts our assumption that $n$ is even.
This is my second practice proof I am working on so please be gentle! I am still learning the logic and working through the proofs slowly. Any feedback, tips, or hints/tricks would be greatly appreciated! Thanks.
elementary-number-theory proof-verification proof-writing
edited Jul 27 at 9:31
user21820
35.8k440136
asked Jul 27 at 3:58
Ryan
865
edited Jul 27 at 9:31
user21820
35.8k440136
edited Jul 27 at 9:31
user21820
35.8k440136
edited Jul 27 at 9:31
user21820
35.8k440136
35.8k440136
asked Jul 27 at 3:58
Ryan
865
asked Jul 27 at 3:58
Ryan
865
asked Jul 27 at 3:58
Ryan
865
865
2
Where did you use the assumption "$n^2-1$ is divisible by $8$"? Also, how can you justify the sentence "Therefore, $n$ must be odd" ?
– Suzet
Jul 27 at 4:01
@Suzet It was unnecessary since the OP approached via contradiction.
– JMoravitz
Jul 27 at 4:02
2
@ Ryan, you could have explained better why $(2k)^2-1$ being odd implies that $8$ is not a divisor of $n^2-1$. You seem to have glossed over this step which can be fleshed out. (Note that since $2mid 8$ and supposing that $8mid n^2-1$ this should have implied something about the parity of $n^2-1$)
– JMoravitz
Jul 27 at 4:05
This contradiction shows that $n$ must atleast be odd for it to be divisible by $8$. But it doesn't guarantee that if $n$ is odd $n^2-1$ is divisible by $8$. I think the proof is ok if you only want to prove the forward implication.
– Piyush Divyanakar
Jul 27 at 4:06
@JMoravitz Actually, either the OP is proving the proposition by contraposition (where we do not have $n^2-1$ divisible by $8$), either the OP is proving it by contradiction (where we have and need to use $n^2-1$ is divisible by $8$).
– Suzet
Jul 27 at 4:06
 |Â
show 2 more comments
2
Where did you use the assumption "$n^2-1$ is divisible by $8$"? Also, how can you justify the sentence "Therefore, $n$ must be odd" ?
– Suzet
Jul 27 at 4:01
@Suzet It was unnecessary since the OP approached via contradiction.
– JMoravitz
Jul 27 at 4:02
2
@ Ryan, you could have explained better why $(2k)^2-1$ being odd implies that $8$ is not a divisor of $n^2-1$. You seem to have glossed over this step which can be fleshed out. (Note that since $2mid 8$ and supposing that $8mid n^2-1$ this should have implied something about the parity of $n^2-1$)
– JMoravitz
Jul 27 at 4:05
This contradiction shows that $n$ must atleast be odd for it to be divisible by $8$. But it doesn't guarantee that if $n$ is odd $n^2-1$ is divisible by $8$. I think the proof is ok if you only want to prove the forward implication.
– Piyush Divyanakar
Jul 27 at 4:06
@JMoravitz Actually, either the OP is proving the proposition by contraposition (where we do not have $n^2-1$ divisible by $8$), either the OP is proving it by contradiction (where we have and need to use $n^2-1$ is divisible by $8$).
– Suzet
Jul 27 at 4:06
2
2
Where did you use the assumption "$n^2-1$ is divisible by $8$"? Also, how can you justify the sentence "Therefore, $n$ must be odd" ?
– Suzet
Jul 27 at 4:01
Where did you use the assumption "$n^2-1$ is divisible by $8$"? Also, how can you justify the sentence "Therefore, $n$ must be odd" ?
– Suzet
Jul 27 at 4:01
@Suzet It was unnecessary since the OP approached via contradiction.
– JMoravitz
Jul 27 at 4:02
@Suzet It was unnecessary since the OP approached via contradiction.
– JMoravitz
Jul 27 at 4:02
2
2
@ Ryan, you could have explained better why $(2k)^2-1$ being odd implies that $8$ is not a divisor of $n^2-1$. You seem to have glossed over this step which can be fleshed out. (Note that since $2mid 8$ and supposing that $8mid n^2-1$ this should have implied something about the parity of $n^2-1$)
– JMoravitz
Jul 27 at 4:05
@ Ryan, you could have explained better why $(2k)^2-1$ being odd implies that $8$ is not a divisor of $n^2-1$. You seem to have glossed over this step which can be fleshed out. (Note that since $2mid 8$ and supposing that $8mid n^2-1$ this should have implied something about the parity of $n^2-1$)
– JMoravitz
Jul 27 at 4:05
This contradiction shows that $n$ must atleast be odd for it to be divisible by $8$. But it doesn't guarantee that if $n$ is odd $n^2-1$ is divisible by $8$. I think the proof is ok if you only want to prove the forward implication.
– Piyush Divyanakar
Jul 27 at 4:06
This contradiction shows that $n$ must atleast be odd for it to be divisible by $8$. But it doesn't guarantee that if $n$ is odd $n^2-1$ is divisible by $8$. I think the proof is ok if you only want to prove the forward implication.
– Piyush Divyanakar
Jul 27 at 4:06
@JMoravitz Actually, either the OP is proving the proposition by contraposition (where we do not have $n^2-1$ divisible by $8$), either the OP is proving it by contradiction (where we have and need to use $n^2-1$ is divisible by $8$).
– Suzet
Jul 27 at 4:06
@JMoravitz Actually, either the OP is proving the proposition by contraposition (where we do not have $n^2-1$ divisible by $8$), either the OP is proving it by contradiction (where we have and need to use $n^2-1$ is divisible by $8$).
– Suzet
Jul 27 at 4:06
 |Â
show 2 more comments
5 Answers
5
active
oldest
votes
up vote
7
down vote
In your problem, proof-by-contradiction works as follows:
(Hypothesis) Suppose 8 divides $n^2-1$.
(Assumption) Let us assume that $n$ is even.
$n$ is even $implies$ $n=2k$ for some $k in mathbbZ$
Then, $n^2-1 = (2k)^2-1$
$n^2-1 = 2(2k^2)-1 implies n^2-1 $ is an odd number.
$n^2-1$ is odd $implies$ 8 does not divide $n^2-1$.
Contradiction! That is, assuming n is even contradicts our hypothesis (i.e., $n^2-1$ is divisible by 8).
So our assumption is wrong. This means $n$ has to be odd.
Alternatively, we can prove the contrapositive (i.e., Proving $Aimplies B $ is equivalent to proving $ neg B implies neg A $ ). This works as follows in your case:
Suppose $n$ is even.
Then, $n = 2k$ for some $k in mathbbZ$
$implies$ $n^2-1 = (2k)^2-1$
$implies$ $n^2-1 = 2(2k^2)-1$
$implies$ $n^2-1$ is odd.
$implies$ $n^2-1$ is not divisible by 8.
Thus, we have proved this: $n$ is not odd $implies$ $n^2-1$ is not divisible by 8, which is equivalent to proving this: $n^2-1$ is divisible 8 $implies n$ is odd.
answered Jul 27 at 4:51
Suhan Shetty
835
Great! Thank you! I've read from some other people that proof by contraposition was an 'easier' approach, but I did not want to abandon my initial approach by contradiction. Thank you for your solution.
– Ryan
Jul 27 at 4:55
add a comment |Â
up vote
2
down vote
As you have used the tag number-theory, solution with modular arithmetic:
$n^2-1equiv 0pmod8$ or, $n^2equiv 1pmod8$, if $n$ is even then we need to check two cases, $n=2k$, with $(2,k)=1$ and $n=2^tcdot m$ for $tge 2$. If $n=2k$ then, $n^2equiv 4k^2equiv 1pmod8 $ implies $k^2equiv 4^-1pmod8$, as, $4$ has no inverse $pmod8$, the equation can't be satisfied with any $n=2k$ and for $tge 2$,$n=2^tcdot m,n^2equiv 0pmod8$. Now, if $n$ is odd, $$n^2equiv 4p^2+4p+1equiv 4p(p+1)+1equiv 1pmod8$$
as $p(p+1)equiv 0pmod2$ for any $pin mathbbN$. Hence done. $boxed$
answered Jul 27 at 4:29
tarit goswami
1289
1
Thank you for your response. We have not covered modular arithmetic, yet, so I am unable to comprehend your solution. I apologize for using the wrong tag and will be more careful going forward. Thanks for your solution!
– Ryan
Jul 27 at 4:31
1
@Ryan Write down all $aequiv bpmodp$ as $p$ divides $(a-b)$ and try to understand the solution. Modulo is nothing more than that.
– tarit goswami
Jul 27 at 8:42
add a comment |Â
up vote
2
down vote
Yes $8$, as an even number, cannot divide a number unless that number is even. (For the number would then be a multiple of $8$, which in turn is a multiple of $2$; so the number would be a multiple of $2$ also, that is, even)
But, as you have shown, $n$ even implies $n^2-1$ is odd.
Your proof, however, doesn't mention divisibility by $8$, and what it implies; as well as circling around unnecessarily at the end. What I mean is, once you get that $n$ is odd you should be done (no need for a contradiction heaped on top of that; it's what you wanted to prove.) But, it's beside the point, for, as I mentioned, your proof was incomplete... Hang in there and it will get easier...
answered Jul 27 at 5:59
Chris Custer
5,2782622
Thank you for your feedback. The concepts of proof is still extremely difficult for me so thanks for the encouragement.
– Ryan
Jul 27 at 17:09
add a comment |Â
up vote
2
down vote
Assume to the contrary that n is even. That is, n = 2k for some integer k.
Then
$n^2 - 1
= (2k)^2 - 1
= 2(2k^2) - 1$
Note that this is an odd number which is clearly not divisible by 8 (an even number).
answered Jul 27 at 9:34
August
1,077617
Thanks! That was my thought track, but I had a hard time translating it into a proof format. Still trying to get my head around writing a clear and concise proof.
– Ryan
Jul 27 at 17:02
add a comment |Â
up vote
1
down vote
You can also prove this by the direct approach. Notice that if $n^2-1$ is divisible by $8$, then $n^2-1=8k$ for some integer $k$. Then $n^2=8k+1=2(4k)+1$. Letting $4k=j$ gives us $n^2=2j+1$ which is an odd integer. Since $n^2$ is odd, it follows that $n$ must also be odd. (Q.E.D.)
Hope this really helps you! :)
answered Jul 27 at 4:54
user573497
2009
Wow, that was such a quick and easy way! I did not even think of that. Thank you so much for your feedback.
– Ryan
Jul 27 at 5:06
1
You are welcome! :)
– user573497
Jul 27 at 5:19
add a comment |Â
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
7
down vote
In your problem, proof-by-contradiction works as follows:
(Hypothesis) Suppose 8 divides $n^2-1$.
(Assumption) Let us assume that $n$ is even.
$n$ is even $implies$ $n=2k$ for some $k in mathbbZ$
Then, $n^2-1 = (2k)^2-1$
$n^2-1 = 2(2k^2)-1 implies n^2-1 $ is an odd number.
$n^2-1$ is odd $implies$ 8 does not divide $n^2-1$.
Contradiction! That is, assuming n is even contradicts our hypothesis (i.e., $n^2-1$ is divisible by 8).
So our assumption is wrong. This means $n$ has to be odd.
Alternatively, we can prove the contrapositive (i.e., Proving $Aimplies B $ is equivalent to proving $ neg B implies neg A $ ). This works as follows in your case:
Suppose $n$ is even.
Then, $n = 2k$ for some $k in mathbbZ$
$implies$ $n^2-1 = (2k)^2-1$
$implies$ $n^2-1 = 2(2k^2)-1$
$implies$ $n^2-1$ is odd.
$implies$ $n^2-1$ is not divisible by 8.
Thus, we have proved this: $n$ is not odd $implies$ $n^2-1$ is not divisible by 8, which is equivalent to proving this: $n^2-1$ is divisible 8 $implies n$ is odd.
answered Jul 27 at 4:51
Suhan Shetty
835
Great! Thank you! I've read from some other people that proof by contraposition was an 'easier' approach, but I did not want to abandon my initial approach by contradiction. Thank you for your solution.
– Ryan
Jul 27 at 4:55
add a comment |Â
up vote
7
down vote
In your problem, proof-by-contradiction works as follows:
(Hypothesis) Suppose 8 divides $n^2-1$.
(Assumption) Let us assume that $n$ is even.
$n$ is even $implies$ $n=2k$ for some $k in mathbbZ$
Then, $n^2-1 = (2k)^2-1$
$n^2-1 = 2(2k^2)-1 implies n^2-1 $ is an odd number.
$n^2-1$ is odd $implies$ 8 does not divide $n^2-1$.
Contradiction! That is, assuming n is even contradicts our hypothesis (i.e., $n^2-1$ is divisible by 8).
So our assumption is wrong. This means $n$ has to be odd.
Alternatively, we can prove the contrapositive (i.e., Proving $Aimplies B $ is equivalent to proving $ neg B implies neg A $ ). This works as follows in your case:
Suppose $n$ is even.
Then, $n = 2k$ for some $k in mathbbZ$
$implies$ $n^2-1 = (2k)^2-1$
$implies$ $n^2-1 = 2(2k^2)-1$
$implies$ $n^2-1$ is odd.
$implies$ $n^2-1$ is not divisible by 8.
Thus, we have proved this: $n$ is not odd $implies$ $n^2-1$ is not divisible by 8, which is equivalent to proving this: $n^2-1$ is divisible 8 $implies n$ is odd.
answered Jul 27 at 4:51
Suhan Shetty
835
Great! Thank you! I've read from some other people that proof by contraposition was an 'easier' approach, but I did not want to abandon my initial approach by contradiction. Thank you for your solution.
– Ryan
Jul 27 at 4:55
add a comment |Â
up vote
7
down vote
up vote
7
down vote
In your problem, proof-by-contradiction works as follows:
(Hypothesis) Suppose 8 divides $n^2-1$.
(Assumption) Let us assume that $n$ is even.
$n$ is even $implies$ $n=2k$ for some $k in mathbbZ$
Then, $n^2-1 = (2k)^2-1$
$n^2-1 = 2(2k^2)-1 implies n^2-1 $ is an odd number.
$n^2-1$ is odd $implies$ 8 does not divide $n^2-1$.
Contradiction! That is, assuming n is even contradicts our hypothesis (i.e., $n^2-1$ is divisible by 8).
So our assumption is wrong. This means $n$ has to be odd.
Alternatively, we can prove the contrapositive (i.e., Proving $Aimplies B $ is equivalent to proving $ neg B implies neg A $ ). This works as follows in your case:
Suppose $n$ is even.
Then, $n = 2k$ for some $k in mathbbZ$
$implies$ $n^2-1 = (2k)^2-1$
$implies$ $n^2-1 = 2(2k^2)-1$
$implies$ $n^2-1$ is odd.
$implies$ $n^2-1$ is not divisible by 8.
Thus, we have proved this: $n$ is not odd $implies$ $n^2-1$ is not divisible by 8, which is equivalent to proving this: $n^2-1$ is divisible 8 $implies n$ is odd.
answered Jul 27 at 4:51
Suhan Shetty
835
In your problem, proof-by-contradiction works as follows:
(Hypothesis) Suppose 8 divides $n^2-1$.
(Assumption) Let us assume that $n$ is even.
$n$ is even $implies$ $n=2k$ for some $k in mathbbZ$
Then, $n^2-1 = (2k)^2-1$
$n^2-1 = 2(2k^2)-1 implies n^2-1 $ is an odd number.
$n^2-1$ is odd $implies$ 8 does not divide $n^2-1$.
Contradiction! That is, assuming n is even contradicts our hypothesis (i.e., $n^2-1$ is divisible by 8).
So our assumption is wrong. This means $n$ has to be odd.
Alternatively, we can prove the contrapositive (i.e., Proving $Aimplies B $ is equivalent to proving $ neg B implies neg A $ ). This works as follows in your case:
Suppose $n$ is even.
Then, $n = 2k$ for some $k in mathbbZ$
$implies$ $n^2-1 = (2k)^2-1$
$implies$ $n^2-1 = 2(2k^2)-1$
$implies$ $n^2-1$ is odd.
$implies$ $n^2-1$ is not divisible by 8.
Thus, we have proved this: $n$ is not odd $implies$ $n^2-1$ is not divisible by 8, which is equivalent to proving this: $n^2-1$ is divisible 8 $implies n$ is odd.
answered Jul 27 at 4:51
Suhan Shetty
835
answered Jul 27 at 4:51
Suhan Shetty
835
answered Jul 27 at 4:51
Suhan Shetty
835
answered Jul 27 at 4:51
Suhan Shetty
835
835
Great! Thank you! I've read from some other people that proof by contraposition was an 'easier' approach, but I did not want to abandon my initial approach by contradiction. Thank you for your solution.
– Ryan
Jul 27 at 4:55
add a comment |Â
Great! Thank you! I've read from some other people that proof by contraposition was an 'easier' approach, but I did not want to abandon my initial approach by contradiction. Thank you for your solution.
– Ryan
Jul 27 at 4:55
Great! Thank you! I've read from some other people that proof by contraposition was an 'easier' approach, but I did not want to abandon my initial approach by contradiction. Thank you for your solution.
– Ryan
Jul 27 at 4:55
Great! Thank you! I've read from some other people that proof by contraposition was an 'easier' approach, but I did not want to abandon my initial approach by contradiction. Thank you for your solution.
– Ryan
Jul 27 at 4:55
add a comment |Â
up vote
2
down vote
As you have used the tag number-theory, solution with modular arithmetic:
$n^2-1equiv 0pmod8$ or, $n^2equiv 1pmod8$, if $n$ is even then we need to check two cases, $n=2k$, with $(2,k)=1$ and $n=2^tcdot m$ for $tge 2$. If $n=2k$ then, $n^2equiv 4k^2equiv 1pmod8 $ implies $k^2equiv 4^-1pmod8$, as, $4$ has no inverse $pmod8$, the equation can't be satisfied with any $n=2k$ and for $tge 2$,$n=2^tcdot m,n^2equiv 0pmod8$. Now, if $n$ is odd, $$n^2equiv 4p^2+4p+1equiv 4p(p+1)+1equiv 1pmod8$$
as $p(p+1)equiv 0pmod2$ for any $pin mathbbN$. Hence done. $boxed$
answered Jul 27 at 4:29
tarit goswami
1289
1
Thank you for your response. We have not covered modular arithmetic, yet, so I am unable to comprehend your solution. I apologize for using the wrong tag and will be more careful going forward. Thanks for your solution!
– Ryan
Jul 27 at 4:31
1
@Ryan Write down all $aequiv bpmodp$ as $p$ divides $(a-b)$ and try to understand the solution. Modulo is nothing more than that.
– tarit goswami
Jul 27 at 8:42
add a comment |Â
up vote
2
down vote
As you have used the tag number-theory, solution with modular arithmetic:
$n^2-1equiv 0pmod8$ or, $n^2equiv 1pmod8$, if $n$ is even then we need to check two cases, $n=2k$, with $(2,k)=1$ and $n=2^tcdot m$ for $tge 2$. If $n=2k$ then, $n^2equiv 4k^2equiv 1pmod8 $ implies $k^2equiv 4^-1pmod8$, as, $4$ has no inverse $pmod8$, the equation can't be satisfied with any $n=2k$ and for $tge 2$,$n=2^tcdot m,n^2equiv 0pmod8$. Now, if $n$ is odd, $$n^2equiv 4p^2+4p+1equiv 4p(p+1)+1equiv 1pmod8$$
as $p(p+1)equiv 0pmod2$ for any $pin mathbbN$. Hence done. $boxed$
answered Jul 27 at 4:29
tarit goswami
1289
1
Thank you for your response. We have not covered modular arithmetic, yet, so I am unable to comprehend your solution. I apologize for using the wrong tag and will be more careful going forward. Thanks for your solution!
– Ryan
Jul 27 at 4:31
1
@Ryan Write down all $aequiv bpmodp$ as $p$ divides $(a-b)$ and try to understand the solution. Modulo is nothing more than that.
– tarit goswami
Jul 27 at 8:42
add a comment |Â
up vote
2
down vote
up vote
2
down vote
As you have used the tag number-theory, solution with modular arithmetic:
$n^2-1equiv 0pmod8$ or, $n^2equiv 1pmod8$, if $n$ is even then we need to check two cases, $n=2k$, with $(2,k)=1$ and $n=2^tcdot m$ for $tge 2$. If $n=2k$ then, $n^2equiv 4k^2equiv 1pmod8 $ implies $k^2equiv 4^-1pmod8$, as, $4$ has no inverse $pmod8$, the equation can't be satisfied with any $n=2k$ and for $tge 2$,$n=2^tcdot m,n^2equiv 0pmod8$. Now, if $n$ is odd, $$n^2equiv 4p^2+4p+1equiv 4p(p+1)+1equiv 1pmod8$$
as $p(p+1)equiv 0pmod2$ for any $pin mathbbN$. Hence done. $boxed$
answered Jul 27 at 4:29
tarit goswami
1289
As you have used the tag number-theory, solution with modular arithmetic:
$n^2-1equiv 0pmod8$ or, $n^2equiv 1pmod8$, if $n$ is even then we need to check two cases, $n=2k$, with $(2,k)=1$ and $n=2^tcdot m$ for $tge 2$. If $n=2k$ then, $n^2equiv 4k^2equiv 1pmod8 $ implies $k^2equiv 4^-1pmod8$, as, $4$ has no inverse $pmod8$, the equation can't be satisfied with any $n=2k$ and for $tge 2$,$n=2^tcdot m,n^2equiv 0pmod8$. Now, if $n$ is odd, $$n^2equiv 4p^2+4p+1equiv 4p(p+1)+1equiv 1pmod8$$
as $p(p+1)equiv 0pmod2$ for any $pin mathbbN$. Hence done. $boxed$
answered Jul 27 at 4:29
tarit goswami
1289
answered Jul 27 at 4:29
tarit goswami
1289
answered Jul 27 at 4:29
tarit goswami
1289
answered Jul 27 at 4:29
tarit goswami
1289
1289
1
Thank you for your response. We have not covered modular arithmetic, yet, so I am unable to comprehend your solution. I apologize for using the wrong tag and will be more careful going forward. Thanks for your solution!
– Ryan
Jul 27 at 4:31
1
@Ryan Write down all $aequiv bpmodp$ as $p$ divides $(a-b)$ and try to understand the solution. Modulo is nothing more than that.
– tarit goswami
Jul 27 at 8:42
add a comment |Â
1
Thank you for your response. We have not covered modular arithmetic, yet, so I am unable to comprehend your solution. I apologize for using the wrong tag and will be more careful going forward. Thanks for your solution!
– Ryan
Jul 27 at 4:31
1
@Ryan Write down all $aequiv bpmodp$ as $p$ divides $(a-b)$ and try to understand the solution. Modulo is nothing more than that.
– tarit goswami
Jul 27 at 8:42
1
1
Thank you for your response. We have not covered modular arithmetic, yet, so I am unable to comprehend your solution. I apologize for using the wrong tag and will be more careful going forward. Thanks for your solution!
– Ryan
Jul 27 at 4:31
Thank you for your response. We have not covered modular arithmetic, yet, so I am unable to comprehend your solution. I apologize for using the wrong tag and will be more careful going forward. Thanks for your solution!
– Ryan
Jul 27 at 4:31
1
1
@Ryan Write down all $aequiv bpmodp$ as $p$ divides $(a-b)$ and try to understand the solution. Modulo is nothing more than that.
– tarit goswami
Jul 27 at 8:42
@Ryan Write down all $aequiv bpmodp$ as $p$ divides $(a-b)$ and try to understand the solution. Modulo is nothing more than that.
– tarit goswami
Jul 27 at 8:42
add a comment |Â
up vote
2
down vote
Yes $8$, as an even number, cannot divide a number unless that number is even. (For the number would then be a multiple of $8$, which in turn is a multiple of $2$; so the number would be a multiple of $2$ also, that is, even)
But, as you have shown, $n$ even implies $n^2-1$ is odd.
Your proof, however, doesn't mention divisibility by $8$, and what it implies; as well as circling around unnecessarily at the end. What I mean is, once you get that $n$ is odd you should be done (no need for a contradiction heaped on top of that; it's what you wanted to prove.) But, it's beside the point, for, as I mentioned, your proof was incomplete... Hang in there and it will get easier...
answered Jul 27 at 5:59
Chris Custer
5,2782622
Thank you for your feedback. The concepts of proof is still extremely difficult for me so thanks for the encouragement.
– Ryan
Jul 27 at 17:09
add a comment |Â
up vote
2
down vote
Yes $8$, as an even number, cannot divide a number unless that number is even. (For the number would then be a multiple of $8$, which in turn is a multiple of $2$; so the number would be a multiple of $2$ also, that is, even)
But, as you have shown, $n$ even implies $n^2-1$ is odd.
Your proof, however, doesn't mention divisibility by $8$, and what it implies; as well as circling around unnecessarily at the end. What I mean is, once you get that $n$ is odd you should be done (no need for a contradiction heaped on top of that; it's what you wanted to prove.) But, it's beside the point, for, as I mentioned, your proof was incomplete... Hang in there and it will get easier...
answered Jul 27 at 5:59
Chris Custer
5,2782622
Thank you for your feedback. The concepts of proof is still extremely difficult for me so thanks for the encouragement.
– Ryan
Jul 27 at 17:09
add a comment |Â
up vote
2
down vote
up vote
2
down vote
Yes $8$, as an even number, cannot divide a number unless that number is even. (For the number would then be a multiple of $8$, which in turn is a multiple of $2$; so the number would be a multiple of $2$ also, that is, even)
But, as you have shown, $n$ even implies $n^2-1$ is odd.
Your proof, however, doesn't mention divisibility by $8$, and what it implies; as well as circling around unnecessarily at the end. What I mean is, once you get that $n$ is odd you should be done (no need for a contradiction heaped on top of that; it's what you wanted to prove.) But, it's beside the point, for, as I mentioned, your proof was incomplete... Hang in there and it will get easier...
answered Jul 27 at 5:59
Chris Custer
5,2782622
Yes $8$, as an even number, cannot divide a number unless that number is even. (For the number would then be a multiple of $8$, which in turn is a multiple of $2$; so the number would be a multiple of $2$ also, that is, even)
But, as you have shown, $n$ even implies $n^2-1$ is odd.
Your proof, however, doesn't mention divisibility by $8$, and what it implies; as well as circling around unnecessarily at the end. What I mean is, once you get that $n$ is odd you should be done (no need for a contradiction heaped on top of that; it's what you wanted to prove.) But, it's beside the point, for, as I mentioned, your proof was incomplete... Hang in there and it will get easier...
answered Jul 27 at 5:59
Chris Custer
5,2782622
edited Jul 27 at 6:20
answered Jul 27 at 5:59
Chris Custer
5,2782622
answered Jul 27 at 5:59
Chris Custer
5,2782622
answered Jul 27 at 5:59
Chris Custer
5,2782622
5,2782622
Thank you for your feedback. The concepts of proof is still extremely difficult for me so thanks for the encouragement.
– Ryan
Jul 27 at 17:09
add a comment |Â
Thank you for your feedback. The concepts of proof is still extremely difficult for me so thanks for the encouragement.
– Ryan
Jul 27 at 17:09
Thank you for your feedback. The concepts of proof is still extremely difficult for me so thanks for the encouragement.
– Ryan
Jul 27 at 17:09
Thank you for your feedback. The concepts of proof is still extremely difficult for me so thanks for the encouragement.
– Ryan
Jul 27 at 17:09
add a comment |Â
up vote
2
down vote
Assume to the contrary that n is even. That is, n = 2k for some integer k.
Then
$n^2 - 1
= (2k)^2 - 1
= 2(2k^2) - 1$
Note that this is an odd number which is clearly not divisible by 8 (an even number).
answered Jul 27 at 9:34
August
1,077617
Thanks! That was my thought track, but I had a hard time translating it into a proof format. Still trying to get my head around writing a clear and concise proof.
– Ryan
Jul 27 at 17:02
add a comment |Â
up vote
2
down vote
Assume to the contrary that n is even. That is, n = 2k for some integer k.
Then
$n^2 - 1
= (2k)^2 - 1
= 2(2k^2) - 1$
Note that this is an odd number which is clearly not divisible by 8 (an even number).
answered Jul 27 at 9:34
August
1,077617
Thanks! That was my thought track, but I had a hard time translating it into a proof format. Still trying to get my head around writing a clear and concise proof.
– Ryan
Jul 27 at 17:02
add a comment |Â
up vote
2
down vote
up vote
2
down vote
Assume to the contrary that n is even. That is, n = 2k for some integer k.
Then
$n^2 - 1
= (2k)^2 - 1
= 2(2k^2) - 1$
Note that this is an odd number which is clearly not divisible by 8 (an even number).
answered Jul 27 at 9:34
August
1,077617
Assume to the contrary that n is even. That is, n = 2k for some integer k.
Then
$n^2 - 1
= (2k)^2 - 1
= 2(2k^2) - 1$
Note that this is an odd number which is clearly not divisible by 8 (an even number).
answered Jul 27 at 9:34
August
1,077617
answered Jul 27 at 9:34
August
1,077617
answered Jul 27 at 9:34
August
1,077617
answered Jul 27 at 9:34
August
1,077617
1,077617
Thanks! That was my thought track, but I had a hard time translating it into a proof format. Still trying to get my head around writing a clear and concise proof.
– Ryan
Jul 27 at 17:02
add a comment |Â
Thanks! That was my thought track, but I had a hard time translating it into a proof format. Still trying to get my head around writing a clear and concise proof.
– Ryan
Jul 27 at 17:02
Thanks! That was my thought track, but I had a hard time translating it into a proof format. Still trying to get my head around writing a clear and concise proof.
– Ryan
Jul 27 at 17:02
Thanks! That was my thought track, but I had a hard time translating it into a proof format. Still trying to get my head around writing a clear and concise proof.
– Ryan
Jul 27 at 17:02
add a comment |Â
up vote
1
down vote
You can also prove this by the direct approach. Notice that if $n^2-1$ is divisible by $8$, then $n^2-1=8k$ for some integer $k$. Then $n^2=8k+1=2(4k)+1$. Letting $4k=j$ gives us $n^2=2j+1$ which is an odd integer. Since $n^2$ is odd, it follows that $n$ must also be odd. (Q.E.D.)
Hope this really helps you! :)
answered Jul 27 at 4:54
user573497
2009
Wow, that was such a quick and easy way! I did not even think of that. Thank you so much for your feedback.
– Ryan
Jul 27 at 5:06
1
You are welcome! :)
– user573497
Jul 27 at 5:19
add a comment |Â
up vote
1
down vote
You can also prove this by the direct approach. Notice that if $n^2-1$ is divisible by $8$, then $n^2-1=8k$ for some integer $k$. Then $n^2=8k+1=2(4k)+1$. Letting $4k=j$ gives us $n^2=2j+1$ which is an odd integer. Since $n^2$ is odd, it follows that $n$ must also be odd. (Q.E.D.)
Hope this really helps you! :)
answered Jul 27 at 4:54
user573497
2009
Wow, that was such a quick and easy way! I did not even think of that. Thank you so much for your feedback.
– Ryan
Jul 27 at 5:06
1
You are welcome! :)
– user573497
Jul 27 at 5:19
add a comment |Â
up vote
1
down vote
up vote
1
down vote
You can also prove this by the direct approach. Notice that if $n^2-1$ is divisible by $8$, then $n^2-1=8k$ for some integer $k$. Then $n^2=8k+1=2(4k)+1$. Letting $4k=j$ gives us $n^2=2j+1$ which is an odd integer. Since $n^2$ is odd, it follows that $n$ must also be odd. (Q.E.D.)
Hope this really helps you! :)
answered Jul 27 at 4:54
user573497
2009
You can also prove this by the direct approach. Notice that if $n^2-1$ is divisible by $8$, then $n^2-1=8k$ for some integer $k$. Then $n^2=8k+1=2(4k)+1$. Letting $4k=j$ gives us $n^2=2j+1$ which is an odd integer. Since $n^2$ is odd, it follows that $n$ must also be odd. (Q.E.D.)
Hope this really helps you! :)
answered Jul 27 at 4:54
user573497
2009
answered Jul 27 at 4:54
user573497
2009
answered Jul 27 at 4:54
user573497
2009
answered Jul 27 at 4:54
user573497
2009
2009
Wow, that was such a quick and easy way! I did not even think of that. Thank you so much for your feedback.
– Ryan
Jul 27 at 5:06
1
You are welcome! :)
– user573497
Jul 27 at 5:19
add a comment |Â
Wow, that was such a quick and easy way! I did not even think of that. Thank you so much for your feedback.
– Ryan
Jul 27 at 5:06
1
You are welcome! :)
– user573497
Jul 27 at 5:19
Wow, that was such a quick and easy way! I did not even think of that. Thank you so much for your feedback.
– Ryan
Jul 27 at 5:06
Wow, that was such a quick and easy way! I did not even think of that. Thank you so much for your feedback.
– Ryan
Jul 27 at 5:06
1
1
You are welcome! :)
– user573497
Jul 27 at 5:19
You are welcome! :)
– user573497
Jul 27 at 5:19
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2864035%2fproof-that-if-n2-1-is-divisible-by-8-then-n-is-odd%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
2
Where did you use the assumption "$n^2-1$ is divisible by $8$"? Also, how can you justify the sentence "Therefore, $n$ must be odd" ?
– Suzet
Jul 27 at 4:01
@Suzet It was unnecessary since the OP approached via contradiction.
– JMoravitz
Jul 27 at 4:02
2
@ Ryan, you could have explained better why $(2k)^2-1$ being odd implies that $8$ is not a divisor of $n^2-1$. You seem to have glossed over this step which can be fleshed out. (Note that since $2mid 8$ and supposing that $8mid n^2-1$ this should have implied something about the parity of $n^2-1$)
– JMoravitz
Jul 27 at 4:05
This contradiction shows that $n$ must atleast be odd for it to be divisible by $8$. But it doesn't guarantee that if $n$ is odd $n^2-1$ is divisible by $8$. I think the proof is ok if you only want to prove the forward implication.
– Piyush Divyanakar
Jul 27 at 4:06
@JMoravitz Actually, either the OP is proving the proposition by contraposition (where we do not have $n^2-1$ divisible by $8$), either the OP is proving it by contradiction (where we have and need to use $n^2-1$ is divisible by $8$).
– Suzet
Jul 27 at 4:06