Mixing
Prove or disprove that $n^3-n$ is divisible by $6$, without using induction [duplicate]
$begingroup$
This question already has an answer here:
Proving divisibility of $a^3 - a$ by $6$
3 answers
Show that $n^3-n$ is divisible by $6$ using induction
3 answers
Prove or disprove that $n^3-n$ is divisible by $6$, without using induction
I have no idea how to go about this.
I should add that n is an integer. I started by looking for some integer that was a single case disproving it, but I couldn't find one.
Any help/suggestions are welcome!
discrete-mathematics
asked Jan 17 at 23:19
dvanariadvanaria
219210
$endgroup$
marked as duplicate by Jyrki Lahtonen, José Carlos Santos, Git Gud, max_zorn, Lord Shark the Unknown Jan 18 at 4:55
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |
$begingroup$
This question already has an answer here:
Proving divisibility of $a^3 - a$ by $6$
3 answers
Show that $n^3-n$ is divisible by $6$ using induction
3 answers
Prove or disprove that $n^3-n$ is divisible by $6$, without using induction
I have no idea how to go about this.
I should add that n is an integer. I started by looking for some integer that was a single case disproving it, but I couldn't find one.
Any help/suggestions are welcome!
discrete-mathematics
asked Jan 17 at 23:19
dvanariadvanaria
219210
$endgroup$
marked as duplicate by Jyrki Lahtonen, José Carlos Santos, Git Gud, max_zorn, Lord Shark the Unknown Jan 18 at 4:55
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
$begingroup$
Possible duplicate of Show that $n^3-n$ is divisible by $6$ using induction. Several other candidates for duplicate targets can be found with Approach0. That is the oldest (and has been used earlier as well).
$endgroup$
– Jyrki Lahtonen
Jan 17 at 23:26
$begingroup$
This question is different than that possible duplicate: I'm trying to prove this without using induction
$endgroup$
– dvanaria
Jan 17 at 23:28
$begingroup$
Here's a variant where induction is not used. Sorry about not paying attention.
$endgroup$
– Jyrki Lahtonen
Jan 17 at 23:28
2
$begingroup$
$$n^3-n = 6binom{n+1}{3}in 6mathbb{Z}$$
$endgroup$
– Jack D'Aurizio
Jan 17 at 23:38
add a comment |
$begingroup$
This question already has an answer here:
Proving divisibility of $a^3 - a$ by $6$
3 answers
Show that $n^3-n$ is divisible by $6$ using induction
3 answers
Prove or disprove that $n^3-n$ is divisible by $6$, without using induction
I have no idea how to go about this.
I should add that n is an integer. I started by looking for some integer that was a single case disproving it, but I couldn't find one.
Any help/suggestions are welcome!
discrete-mathematics
asked Jan 17 at 23:19
dvanariadvanaria
219210
$endgroup$
This question already has an answer here:
Proving divisibility of $a^3 - a$ by $6$
3 answers
Show that $n^3-n$ is divisible by $6$ using induction
3 answers
Prove or disprove that $n^3-n$ is divisible by $6$, without using induction
I have no idea how to go about this.
I should add that n is an integer. I started by looking for some integer that was a single case disproving it, but I couldn't find one.
Any help/suggestions are welcome!
This question already has an answer here:
Proving divisibility of $a^3 - a$ by $6$
3 answers
Show that $n^3-n$ is divisible by $6$ using induction
3 answers
discrete-mathematics
discrete-mathematics
asked Jan 17 at 23:19
dvanariadvanaria
219210
asked Jan 17 at 23:19
dvanariadvanaria
219210
asked Jan 17 at 23:19
dvanariadvanaria
219210
asked Jan 17 at 23:19
dvanariadvanaria
219210
asked Jan 17 at 23:19
dvanariadvanaria
219210
219210
marked as duplicate by Jyrki Lahtonen, José Carlos Santos, Git Gud, max_zorn, Lord Shark the Unknown Jan 18 at 4:55
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by Jyrki Lahtonen, José Carlos Santos, Git Gud, max_zorn, Lord Shark the Unknown Jan 18 at 4:55
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
$begingroup$
Possible duplicate of Show that $n^3-n$ is divisible by $6$ using induction. Several other candidates for duplicate targets can be found with Approach0. That is the oldest (and has been used earlier as well).
$endgroup$
– Jyrki Lahtonen
Jan 17 at 23:26
$begingroup$
This question is different than that possible duplicate: I'm trying to prove this without using induction
$endgroup$
– dvanaria
Jan 17 at 23:28
$begingroup$
Here's a variant where induction is not used. Sorry about not paying attention.
$endgroup$
– Jyrki Lahtonen
Jan 17 at 23:28
2
$begingroup$
$$n^3-n = 6binom{n+1}{3}in 6mathbb{Z}$$
$endgroup$
– Jack D'Aurizio
Jan 17 at 23:38
add a comment |
$begingroup$
Possible duplicate of Show that $n^3-n$ is divisible by $6$ using induction. Several other candidates for duplicate targets can be found with Approach0. That is the oldest (and has been used earlier as well).
$endgroup$
– Jyrki Lahtonen
Jan 17 at 23:26
$begingroup$
This question is different than that possible duplicate: I'm trying to prove this without using induction
$endgroup$
– dvanaria
Jan 17 at 23:28
$begingroup$
Here's a variant where induction is not used. Sorry about not paying attention.
$endgroup$
– Jyrki Lahtonen
Jan 17 at 23:28
2
$begingroup$
$$n^3-n = 6binom{n+1}{3}in 6mathbb{Z}$$
$endgroup$
– Jack D'Aurizio
Jan 17 at 23:38
$begingroup$
Possible duplicate of Show that $n^3-n$ is divisible by $6$ using induction. Several other candidates for duplicate targets can be found with Approach0. That is the oldest (and has been used earlier as well).
$endgroup$
– Jyrki Lahtonen
Jan 17 at 23:26
$begingroup$
Possible duplicate of Show that $n^3-n$ is divisible by $6$ using induction. Several other candidates for duplicate targets can be found with Approach0. That is the oldest (and has been used earlier as well).
$endgroup$
– Jyrki Lahtonen
Jan 17 at 23:26
$begingroup$
This question is different than that possible duplicate: I'm trying to prove this without using induction
$endgroup$
– dvanaria
Jan 17 at 23:28
$begingroup$
This question is different than that possible duplicate: I'm trying to prove this without using induction
$endgroup$
– dvanaria
Jan 17 at 23:28
$begingroup$
Here's a variant where induction is not used. Sorry about not paying attention.
$endgroup$
– Jyrki Lahtonen
Jan 17 at 23:28
$begingroup$
Here's a variant where induction is not used. Sorry about not paying attention.
$endgroup$
– Jyrki Lahtonen
Jan 17 at 23:28
2
2
$begingroup$
$$n^3-n = 6binom{n+1}{3}in 6mathbb{Z}$$
$endgroup$
– Jack D'Aurizio
Jan 17 at 23:38
$begingroup$
$$n^3-n = 6binom{n+1}{3}in 6mathbb{Z}$$
$endgroup$
– Jack D'Aurizio
Jan 17 at 23:38
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
We have
$$n^3 - n = n(n^2-1) = n(n+1)(n-1)$$
One of these $(n, n+1, n-1)$ must be even (why?) and one must be divisible by 3 (why?).
answered Jan 17 at 23:21
twnlytwnly
982213
$endgroup$
$begingroup$
I can prove one of those must be even, but I'm not sure how to prove that one of them must be divisible by 3...
$endgroup$
– dvanaria
Jan 17 at 23:49
$begingroup$
$n-1, n, n+1$ are three consecutive numbers. Whenever you have three consecutive numbers and take it $pmod 3$, then one has to be $0 pmod 3$.
$endgroup$
– twnly
Jan 18 at 0:01
add a comment |
$begingroup$
By the division theorem we have $n=6k+r$ for some $0 le r < 6$. Then
$$(n^3-n) = (6k+r)^3 - (6k+r) = 6(x-k) + (r^3-r)$$
where $x = sum_{i=1}^3 binom{3}{i} 6^{i-1}k^ir^{3-i} in mathbb{Z}$ by the binomial theorem.
But $r in {0,1,2,3,4,5}$, so $r^3-r in {0,0,6,24,60,120}$, each of which is a multiple of $6$.
Disclaimer: I would argue that both this answer and twnly's answer 'use induction', because both depend on results that themselves require induction in some form to be proved.
answered Jan 17 at 23:33
Clive NewsteadClive Newstead
51.8k474136
$endgroup$
$begingroup$
That disclaimer is so, so true. You really can't do much with regards to the natural numbers without induction. In some definitions of natural numbers, induction is actually part of them.
$endgroup$
– Git Gud
Jan 17 at 23:37
add a comment |
$begingroup$
Hint:
Fermat's theorem and Chinese remainder theorem.
answered Jan 17 at 23:22
BernardBernard
121k740116
$endgroup$
add a comment |
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
We have
$$n^3 - n = n(n^2-1) = n(n+1)(n-1)$$
One of these $(n, n+1, n-1)$ must be even (why?) and one must be divisible by 3 (why?).
answered Jan 17 at 23:21
twnlytwnly
982213
$endgroup$
$begingroup$
I can prove one of those must be even, but I'm not sure how to prove that one of them must be divisible by 3...
$endgroup$
– dvanaria
Jan 17 at 23:49
$begingroup$
$n-1, n, n+1$ are three consecutive numbers. Whenever you have three consecutive numbers and take it $pmod 3$, then one has to be $0 pmod 3$.
$endgroup$
– twnly
Jan 18 at 0:01
add a comment |
$begingroup$
We have
$$n^3 - n = n(n^2-1) = n(n+1)(n-1)$$
One of these $(n, n+1, n-1)$ must be even (why?) and one must be divisible by 3 (why?).
answered Jan 17 at 23:21
twnlytwnly
982213
$endgroup$
$begingroup$
I can prove one of those must be even, but I'm not sure how to prove that one of them must be divisible by 3...
$endgroup$
– dvanaria
Jan 17 at 23:49
$begingroup$
$n-1, n, n+1$ are three consecutive numbers. Whenever you have three consecutive numbers and take it $pmod 3$, then one has to be $0 pmod 3$.
$endgroup$
– twnly
Jan 18 at 0:01
add a comment |
$begingroup$
We have
$$n^3 - n = n(n^2-1) = n(n+1)(n-1)$$
One of these $(n, n+1, n-1)$ must be even (why?) and one must be divisible by 3 (why?).
answered Jan 17 at 23:21
twnlytwnly
982213
$endgroup$
We have
$$n^3 - n = n(n^2-1) = n(n+1)(n-1)$$
One of these $(n, n+1, n-1)$ must be even (why?) and one must be divisible by 3 (why?).
answered Jan 17 at 23:21
twnlytwnly
982213
answered Jan 17 at 23:21
twnlytwnly
982213
answered Jan 17 at 23:21
twnlytwnly
982213
answered Jan 17 at 23:21
twnlytwnly
982213
982213
$begingroup$
I can prove one of those must be even, but I'm not sure how to prove that one of them must be divisible by 3...
$endgroup$
– dvanaria
Jan 17 at 23:49
$begingroup$
$n-1, n, n+1$ are three consecutive numbers. Whenever you have three consecutive numbers and take it $pmod 3$, then one has to be $0 pmod 3$.
$endgroup$
– twnly
Jan 18 at 0:01
add a comment |
$begingroup$
I can prove one of those must be even, but I'm not sure how to prove that one of them must be divisible by 3...
$endgroup$
– dvanaria
Jan 17 at 23:49
$begingroup$
$n-1, n, n+1$ are three consecutive numbers. Whenever you have three consecutive numbers and take it $pmod 3$, then one has to be $0 pmod 3$.
$endgroup$
– twnly
Jan 18 at 0:01
$begingroup$
I can prove one of those must be even, but I'm not sure how to prove that one of them must be divisible by 3...
$endgroup$
– dvanaria
Jan 17 at 23:49
$begingroup$
I can prove one of those must be even, but I'm not sure how to prove that one of them must be divisible by 3...
$endgroup$
– dvanaria
Jan 17 at 23:49
$begingroup$
$n-1, n, n+1$ are three consecutive numbers. Whenever you have three consecutive numbers and take it $pmod 3$, then one has to be $0 pmod 3$.
$endgroup$
– twnly
Jan 18 at 0:01
$begingroup$
$n-1, n, n+1$ are three consecutive numbers. Whenever you have three consecutive numbers and take it $pmod 3$, then one has to be $0 pmod 3$.
$endgroup$
– twnly
Jan 18 at 0:01
add a comment |
$begingroup$
By the division theorem we have $n=6k+r$ for some $0 le r < 6$. Then
$$(n^3-n) = (6k+r)^3 - (6k+r) = 6(x-k) + (r^3-r)$$
where $x = sum_{i=1}^3 binom{3}{i} 6^{i-1}k^ir^{3-i} in mathbb{Z}$ by the binomial theorem.
But $r in {0,1,2,3,4,5}$, so $r^3-r in {0,0,6,24,60,120}$, each of which is a multiple of $6$.
Disclaimer: I would argue that both this answer and twnly's answer 'use induction', because both depend on results that themselves require induction in some form to be proved.
answered Jan 17 at 23:33
Clive NewsteadClive Newstead
51.8k474136
$endgroup$
$begingroup$
That disclaimer is so, so true. You really can't do much with regards to the natural numbers without induction. In some definitions of natural numbers, induction is actually part of them.
$endgroup$
– Git Gud
Jan 17 at 23:37
add a comment |
$begingroup$
By the division theorem we have $n=6k+r$ for some $0 le r < 6$. Then
$$(n^3-n) = (6k+r)^3 - (6k+r) = 6(x-k) + (r^3-r)$$
where $x = sum_{i=1}^3 binom{3}{i} 6^{i-1}k^ir^{3-i} in mathbb{Z}$ by the binomial theorem.
But $r in {0,1,2,3,4,5}$, so $r^3-r in {0,0,6,24,60,120}$, each of which is a multiple of $6$.
Disclaimer: I would argue that both this answer and twnly's answer 'use induction', because both depend on results that themselves require induction in some form to be proved.
answered Jan 17 at 23:33
Clive NewsteadClive Newstead
51.8k474136
$endgroup$
$begingroup$
That disclaimer is so, so true. You really can't do much with regards to the natural numbers without induction. In some definitions of natural numbers, induction is actually part of them.
$endgroup$
– Git Gud
Jan 17 at 23:37
add a comment |
$begingroup$
By the division theorem we have $n=6k+r$ for some $0 le r < 6$. Then
$$(n^3-n) = (6k+r)^3 - (6k+r) = 6(x-k) + (r^3-r)$$
where $x = sum_{i=1}^3 binom{3}{i} 6^{i-1}k^ir^{3-i} in mathbb{Z}$ by the binomial theorem.
But $r in {0,1,2,3,4,5}$, so $r^3-r in {0,0,6,24,60,120}$, each of which is a multiple of $6$.
Disclaimer: I would argue that both this answer and twnly's answer 'use induction', because both depend on results that themselves require induction in some form to be proved.
answered Jan 17 at 23:33
Clive NewsteadClive Newstead
51.8k474136
$endgroup$
By the division theorem we have $n=6k+r$ for some $0 le r < 6$. Then
$$(n^3-n) = (6k+r)^3 - (6k+r) = 6(x-k) + (r^3-r)$$
where $x = sum_{i=1}^3 binom{3}{i} 6^{i-1}k^ir^{3-i} in mathbb{Z}$ by the binomial theorem.
But $r in {0,1,2,3,4,5}$, so $r^3-r in {0,0,6,24,60,120}$, each of which is a multiple of $6$.
Disclaimer: I would argue that both this answer and twnly's answer 'use induction', because both depend on results that themselves require induction in some form to be proved.
answered Jan 17 at 23:33
Clive NewsteadClive Newstead
51.8k474136
answered Jan 17 at 23:33
Clive NewsteadClive Newstead
51.8k474136
answered Jan 17 at 23:33
Clive NewsteadClive Newstead
51.8k474136
answered Jan 17 at 23:33
Clive NewsteadClive Newstead
51.8k474136
51.8k474136
$begingroup$
That disclaimer is so, so true. You really can't do much with regards to the natural numbers without induction. In some definitions of natural numbers, induction is actually part of them.
$endgroup$
– Git Gud
Jan 17 at 23:37
add a comment |
$begingroup$
That disclaimer is so, so true. You really can't do much with regards to the natural numbers without induction. In some definitions of natural numbers, induction is actually part of them.
$endgroup$
– Git Gud
Jan 17 at 23:37
$begingroup$
That disclaimer is so, so true. You really can't do much with regards to the natural numbers without induction. In some definitions of natural numbers, induction is actually part of them.
$endgroup$
– Git Gud
Jan 17 at 23:37
$begingroup$
That disclaimer is so, so true. You really can't do much with regards to the natural numbers without induction. In some definitions of natural numbers, induction is actually part of them.
$endgroup$
– Git Gud
Jan 17 at 23:37
add a comment |
$begingroup$
Hint:
Fermat's theorem and Chinese remainder theorem.
answered Jan 17 at 23:22
BernardBernard
121k740116
$endgroup$
add a comment |
$begingroup$
Hint:
Fermat's theorem and Chinese remainder theorem.
answered Jan 17 at 23:22
BernardBernard
121k740116
$endgroup$
add a comment |
$begingroup$
Hint:
Fermat's theorem and Chinese remainder theorem.
answered Jan 17 at 23:22
BernardBernard
121k740116
$endgroup$
Hint:
Fermat's theorem and Chinese remainder theorem.
answered Jan 17 at 23:22
BernardBernard
121k740116
answered Jan 17 at 23:22
BernardBernard
121k740116
answered Jan 17 at 23:22
BernardBernard
121k740116
answered Jan 17 at 23:22
BernardBernard
121k740116
121k740116
add a comment |
add a comment |
$begingroup$
Possible duplicate of Show that $n^3-n$ is divisible by $6$ using induction. Several other candidates for duplicate targets can be found with Approach0. That is the oldest (and has been used earlier as well).
$endgroup$
– Jyrki Lahtonen
Jan 17 at 23:26
$begingroup$
This question is different than that possible duplicate: I'm trying to prove this without using induction
$endgroup$
– dvanaria
Jan 17 at 23:28
$begingroup$
Here's a variant where induction is not used. Sorry about not paying attention.
$endgroup$
– Jyrki Lahtonen
Jan 17 at 23:28
2
$begingroup$
$$n^3-n = 6binom{n+1}{3}in 6mathbb{Z}$$
$endgroup$
– Jack D'Aurizio
Jan 17 at 23:38