Mixing
Why $binom{mp-1}{p-1} equiv 1 pmod {p^3}$?
$begingroup$
Why $$binom{mp-1}{p-1} equiv 1 pmod {p^3}?$$
I tried by induction on $m$:
$bullet$ $m=0$ $$binom{-1}{p-1} = (-1)^{p-1}=1 equiv 1 pmod {p^3}$$
$bullet$ $m=1$ $$binom{p-1}{p-1} =1 equiv 1 pmod {p^3}$$
$bullet$ induction hylpothesis: $$binom{mp-1}{p-1} equiv 1 pmod {p^3}$$
$bullet$ $m+1$ $$binom{(m+1)p-1}{p-1}= binom{(m+1)p}{p}-binom{(m+1)p-1}{p}$$ but I am not able to move forward. Have you any hints?
Thank you so much
modular-arithmetic binomial-coefficients
edited Jan 27 at 17:09
the_fox
2,90031538
asked Jan 27 at 16:49
Phi_24Phi_24
1938
$endgroup$
add a comment |
$begingroup$
Why $$binom{mp-1}{p-1} equiv 1 pmod {p^3}?$$
I tried by induction on $m$:
$bullet$ $m=0$ $$binom{-1}{p-1} = (-1)^{p-1}=1 equiv 1 pmod {p^3}$$
$bullet$ $m=1$ $$binom{p-1}{p-1} =1 equiv 1 pmod {p^3}$$
$bullet$ induction hylpothesis: $$binom{mp-1}{p-1} equiv 1 pmod {p^3}$$
$bullet$ $m+1$ $$binom{(m+1)p-1}{p-1}= binom{(m+1)p}{p}-binom{(m+1)p-1}{p}$$ but I am not able to move forward. Have you any hints?
Thank you so much
modular-arithmetic binomial-coefficients
edited Jan 27 at 17:09
the_fox
2,90031538
asked Jan 27 at 16:49
Phi_24Phi_24
1938
$endgroup$
2
$begingroup$
Assuming $p$ is supposed to be prime, then I try $p=2, m=2$ and get $binom 31=3neq 1 bmod 8$
$endgroup$
– Mark Bennet
Jan 27 at 16:54
2
$begingroup$
The $p ge 5$, $m=2$ cases are Wolstenholme's theorem. (The primes $p=2$ and $p=3$ already don't work.) Experimentally, though, the result does seem true for all $p ge 5$ and all $m$.
$endgroup$
– Misha Lavrov
Jan 27 at 17:17
add a comment |
$begingroup$
Why $$binom{mp-1}{p-1} equiv 1 pmod {p^3}?$$
I tried by induction on $m$:
$bullet$ $m=0$ $$binom{-1}{p-1} = (-1)^{p-1}=1 equiv 1 pmod {p^3}$$
$bullet$ $m=1$ $$binom{p-1}{p-1} =1 equiv 1 pmod {p^3}$$
$bullet$ induction hylpothesis: $$binom{mp-1}{p-1} equiv 1 pmod {p^3}$$
$bullet$ $m+1$ $$binom{(m+1)p-1}{p-1}= binom{(m+1)p}{p}-binom{(m+1)p-1}{p}$$ but I am not able to move forward. Have you any hints?
Thank you so much
modular-arithmetic binomial-coefficients
edited Jan 27 at 17:09
the_fox
2,90031538
asked Jan 27 at 16:49
Phi_24Phi_24
1938
$endgroup$
Why $$binom{mp-1}{p-1} equiv 1 pmod {p^3}?$$
I tried by induction on $m$:
$bullet$ $m=0$ $$binom{-1}{p-1} = (-1)^{p-1}=1 equiv 1 pmod {p^3}$$
$bullet$ $m=1$ $$binom{p-1}{p-1} =1 equiv 1 pmod {p^3}$$
$bullet$ induction hylpothesis: $$binom{mp-1}{p-1} equiv 1 pmod {p^3}$$
$bullet$ $m+1$ $$binom{(m+1)p-1}{p-1}= binom{(m+1)p}{p}-binom{(m+1)p-1}{p}$$ but I am not able to move forward. Have you any hints?
Thank you so much
modular-arithmetic binomial-coefficients
modular-arithmetic binomial-coefficients
edited Jan 27 at 17:09
the_fox
2,90031538
asked Jan 27 at 16:49
Phi_24Phi_24
1938
edited Jan 27 at 17:09
the_fox
2,90031538
asked Jan 27 at 16:49
Phi_24Phi_24
1938
edited Jan 27 at 17:09
the_fox
2,90031538
edited Jan 27 at 17:09
the_fox
2,90031538
edited Jan 27 at 17:09
the_fox
2,90031538
2,90031538
asked Jan 27 at 16:49
Phi_24Phi_24
1938
asked Jan 27 at 16:49
Phi_24Phi_24
1938
asked Jan 27 at 16:49
Phi_24Phi_24
1938
1938
2
$begingroup$
Assuming $p$ is supposed to be prime, then I try $p=2, m=2$ and get $binom 31=3neq 1 bmod 8$
$endgroup$
– Mark Bennet
Jan 27 at 16:54
2
$begingroup$
The $p ge 5$, $m=2$ cases are Wolstenholme's theorem. (The primes $p=2$ and $p=3$ already don't work.) Experimentally, though, the result does seem true for all $p ge 5$ and all $m$.
$endgroup$
– Misha Lavrov
Jan 27 at 17:17
add a comment |
2
$begingroup$
Assuming $p$ is supposed to be prime, then I try $p=2, m=2$ and get $binom 31=3neq 1 bmod 8$
$endgroup$
– Mark Bennet
Jan 27 at 16:54
2
$begingroup$
The $p ge 5$, $m=2$ cases are Wolstenholme's theorem. (The primes $p=2$ and $p=3$ already don't work.) Experimentally, though, the result does seem true for all $p ge 5$ and all $m$.
$endgroup$
– Misha Lavrov
Jan 27 at 17:17
2
2
$begingroup$
Assuming $p$ is supposed to be prime, then I try $p=2, m=2$ and get $binom 31=3neq 1 bmod 8$
$endgroup$
– Mark Bennet
Jan 27 at 16:54
$begingroup$
Assuming $p$ is supposed to be prime, then I try $p=2, m=2$ and get $binom 31=3neq 1 bmod 8$
$endgroup$
– Mark Bennet
Jan 27 at 16:54
2
2
$begingroup$
The $p ge 5$, $m=2$ cases are Wolstenholme's theorem. (The primes $p=2$ and $p=3$ already don't work.) Experimentally, though, the result does seem true for all $p ge 5$ and all $m$.
$endgroup$
– Misha Lavrov
Jan 27 at 17:17
$begingroup$
The $p ge 5$, $m=2$ cases are Wolstenholme's theorem. (The primes $p=2$ and $p=3$ already don't work.) Experimentally, though, the result does seem true for all $p ge 5$ and all $m$.
$endgroup$
– Misha Lavrov
Jan 27 at 17:17
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The necessary tools can be found in Glaisher's 1900 paper "Congruences relating to the sums of products of the first $n$ numbers and to other sums of $n$ products", which is more or less available here. (It is the first article in the issue.) Glaisher only proves the $m=2$ case this way, I think - but the method works for all cases.
Define the polynomial
$$
f(x) = (x+1)(x+2)dotsb (x+p-1) = left[{patop 1}right] + left[{patop 2}right]x + dots + left[{patop p}right]x^{p-1}
$$
where $left[{patop k}right]$ denotes the unsigned Stirling number of the first kind. (Glaisher does not use this terminology or notation.)
The idea is that $binom{mp-1}{p-1}$ can be written as the ratio $frac{f((m-1)p)}{f(0)}$, and so it is only necessary to show that
$$
f((m-1)p) equiv f(0) pmod{p^3}
$$
and also that neither is divisible by $p$, to prove your theorem. (Well, $f(0)$ is just $(p-1)! = left[{patop 1}right]$, so we know all about it, and it's not divisible by $p$.) This goes in $3$ steps:
- We have $$f((m-1)p) equiv left[{patop 1}right] + left[{patop 2}right]((m-1)p) + left[{patop 3}right]((m-1)p)^2 pmod {p^3},$$ since all other terms have a factor of $p^3$ in them.
- Actually, when $p>2$, $left[{patop 3}right]$ (as well as all other coefficients except $left[{patop 1}right]$) is divisible by $p$, so the quadratic term also vanishes, and we get $$f((m-1)p) equiv left[{patop 1}right] + left[{patop 2}right]((m-1)p) pmod {p^3}.$$ To see the divisibility by $p$, Glaisher compares the coefficients in $f(x+1)$ and $(x+1)f(x)$, and uses the known divisibility properties of binomial coefficients.
- Actually, when $p>3$, $left[{patop 2}right]$ is divisible by $p^2$, so the linear term vanishes, and we get $$f((m-1)p) equiv left[{patop 1}right] pmod{p^3}.$$ To see this, Glaisher expands $f(-p)=left[{patop 1}right]$, and then all terms except the $left[{patop 2}right]$ term have a factor of $p^2$ in them.
This completes the proof, since we've concluded that $f((m-1)p) equiv f(0) pmod{p^3}$, and since neither is divisible by $p$, we can divide and get $frac{f((m-1)p)}{f(0)} equiv 1 pmod{p^3}$.
answered Jan 27 at 18:13
Misha LavrovMisha Lavrov
47.9k657107
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3089806%2fwhy-binommp-1p-1-equiv-1-pmod-p3%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The necessary tools can be found in Glaisher's 1900 paper "Congruences relating to the sums of products of the first $n$ numbers and to other sums of $n$ products", which is more or less available here. (It is the first article in the issue.) Glaisher only proves the $m=2$ case this way, I think - but the method works for all cases.
Define the polynomial
$$
f(x) = (x+1)(x+2)dotsb (x+p-1) = left[{patop 1}right] + left[{patop 2}right]x + dots + left[{patop p}right]x^{p-1}
$$
where $left[{patop k}right]$ denotes the unsigned Stirling number of the first kind. (Glaisher does not use this terminology or notation.)
The idea is that $binom{mp-1}{p-1}$ can be written as the ratio $frac{f((m-1)p)}{f(0)}$, and so it is only necessary to show that
$$
f((m-1)p) equiv f(0) pmod{p^3}
$$
and also that neither is divisible by $p$, to prove your theorem. (Well, $f(0)$ is just $(p-1)! = left[{patop 1}right]$, so we know all about it, and it's not divisible by $p$.) This goes in $3$ steps:
- We have $$f((m-1)p) equiv left[{patop 1}right] + left[{patop 2}right]((m-1)p) + left[{patop 3}right]((m-1)p)^2 pmod {p^3},$$ since all other terms have a factor of $p^3$ in them.
- Actually, when $p>2$, $left[{patop 3}right]$ (as well as all other coefficients except $left[{patop 1}right]$) is divisible by $p$, so the quadratic term also vanishes, and we get $$f((m-1)p) equiv left[{patop 1}right] + left[{patop 2}right]((m-1)p) pmod {p^3}.$$ To see the divisibility by $p$, Glaisher compares the coefficients in $f(x+1)$ and $(x+1)f(x)$, and uses the known divisibility properties of binomial coefficients.
- Actually, when $p>3$, $left[{patop 2}right]$ is divisible by $p^2$, so the linear term vanishes, and we get $$f((m-1)p) equiv left[{patop 1}right] pmod{p^3}.$$ To see this, Glaisher expands $f(-p)=left[{patop 1}right]$, and then all terms except the $left[{patop 2}right]$ term have a factor of $p^2$ in them.
This completes the proof, since we've concluded that $f((m-1)p) equiv f(0) pmod{p^3}$, and since neither is divisible by $p$, we can divide and get $frac{f((m-1)p)}{f(0)} equiv 1 pmod{p^3}$.
answered Jan 27 at 18:13
Misha LavrovMisha Lavrov
47.9k657107
$endgroup$
add a comment |
$begingroup$
The necessary tools can be found in Glaisher's 1900 paper "Congruences relating to the sums of products of the first $n$ numbers and to other sums of $n$ products", which is more or less available here. (It is the first article in the issue.) Glaisher only proves the $m=2$ case this way, I think - but the method works for all cases.
Define the polynomial
$$
f(x) = (x+1)(x+2)dotsb (x+p-1) = left[{patop 1}right] + left[{patop 2}right]x + dots + left[{patop p}right]x^{p-1}
$$
where $left[{patop k}right]$ denotes the unsigned Stirling number of the first kind. (Glaisher does not use this terminology or notation.)
The idea is that $binom{mp-1}{p-1}$ can be written as the ratio $frac{f((m-1)p)}{f(0)}$, and so it is only necessary to show that
$$
f((m-1)p) equiv f(0) pmod{p^3}
$$
and also that neither is divisible by $p$, to prove your theorem. (Well, $f(0)$ is just $(p-1)! = left[{patop 1}right]$, so we know all about it, and it's not divisible by $p$.) This goes in $3$ steps:
- We have $$f((m-1)p) equiv left[{patop 1}right] + left[{patop 2}right]((m-1)p) + left[{patop 3}right]((m-1)p)^2 pmod {p^3},$$ since all other terms have a factor of $p^3$ in them.
- Actually, when $p>2$, $left[{patop 3}right]$ (as well as all other coefficients except $left[{patop 1}right]$) is divisible by $p$, so the quadratic term also vanishes, and we get $$f((m-1)p) equiv left[{patop 1}right] + left[{patop 2}right]((m-1)p) pmod {p^3}.$$ To see the divisibility by $p$, Glaisher compares the coefficients in $f(x+1)$ and $(x+1)f(x)$, and uses the known divisibility properties of binomial coefficients.
- Actually, when $p>3$, $left[{patop 2}right]$ is divisible by $p^2$, so the linear term vanishes, and we get $$f((m-1)p) equiv left[{patop 1}right] pmod{p^3}.$$ To see this, Glaisher expands $f(-p)=left[{patop 1}right]$, and then all terms except the $left[{patop 2}right]$ term have a factor of $p^2$ in them.
This completes the proof, since we've concluded that $f((m-1)p) equiv f(0) pmod{p^3}$, and since neither is divisible by $p$, we can divide and get $frac{f((m-1)p)}{f(0)} equiv 1 pmod{p^3}$.
answered Jan 27 at 18:13
Misha LavrovMisha Lavrov
47.9k657107
$endgroup$
add a comment |
$begingroup$
The necessary tools can be found in Glaisher's 1900 paper "Congruences relating to the sums of products of the first $n$ numbers and to other sums of $n$ products", which is more or less available here. (It is the first article in the issue.) Glaisher only proves the $m=2$ case this way, I think - but the method works for all cases.
Define the polynomial
$$
f(x) = (x+1)(x+2)dotsb (x+p-1) = left[{patop 1}right] + left[{patop 2}right]x + dots + left[{patop p}right]x^{p-1}
$$
where $left[{patop k}right]$ denotes the unsigned Stirling number of the first kind. (Glaisher does not use this terminology or notation.)
The idea is that $binom{mp-1}{p-1}$ can be written as the ratio $frac{f((m-1)p)}{f(0)}$, and so it is only necessary to show that
$$
f((m-1)p) equiv f(0) pmod{p^3}
$$
and also that neither is divisible by $p$, to prove your theorem. (Well, $f(0)$ is just $(p-1)! = left[{patop 1}right]$, so we know all about it, and it's not divisible by $p$.) This goes in $3$ steps:
- We have $$f((m-1)p) equiv left[{patop 1}right] + left[{patop 2}right]((m-1)p) + left[{patop 3}right]((m-1)p)^2 pmod {p^3},$$ since all other terms have a factor of $p^3$ in them.
- Actually, when $p>2$, $left[{patop 3}right]$ (as well as all other coefficients except $left[{patop 1}right]$) is divisible by $p$, so the quadratic term also vanishes, and we get $$f((m-1)p) equiv left[{patop 1}right] + left[{patop 2}right]((m-1)p) pmod {p^3}.$$ To see the divisibility by $p$, Glaisher compares the coefficients in $f(x+1)$ and $(x+1)f(x)$, and uses the known divisibility properties of binomial coefficients.
- Actually, when $p>3$, $left[{patop 2}right]$ is divisible by $p^2$, so the linear term vanishes, and we get $$f((m-1)p) equiv left[{patop 1}right] pmod{p^3}.$$ To see this, Glaisher expands $f(-p)=left[{patop 1}right]$, and then all terms except the $left[{patop 2}right]$ term have a factor of $p^2$ in them.
This completes the proof, since we've concluded that $f((m-1)p) equiv f(0) pmod{p^3}$, and since neither is divisible by $p$, we can divide and get $frac{f((m-1)p)}{f(0)} equiv 1 pmod{p^3}$.
answered Jan 27 at 18:13
Misha LavrovMisha Lavrov
47.9k657107
$endgroup$
The necessary tools can be found in Glaisher's 1900 paper "Congruences relating to the sums of products of the first $n$ numbers and to other sums of $n$ products", which is more or less available here. (It is the first article in the issue.) Glaisher only proves the $m=2$ case this way, I think - but the method works for all cases.
Define the polynomial
$$
f(x) = (x+1)(x+2)dotsb (x+p-1) = left[{patop 1}right] + left[{patop 2}right]x + dots + left[{patop p}right]x^{p-1}
$$
where $left[{patop k}right]$ denotes the unsigned Stirling number of the first kind. (Glaisher does not use this terminology or notation.)
The idea is that $binom{mp-1}{p-1}$ can be written as the ratio $frac{f((m-1)p)}{f(0)}$, and so it is only necessary to show that
$$
f((m-1)p) equiv f(0) pmod{p^3}
$$
and also that neither is divisible by $p$, to prove your theorem. (Well, $f(0)$ is just $(p-1)! = left[{patop 1}right]$, so we know all about it, and it's not divisible by $p$.) This goes in $3$ steps:
- We have $$f((m-1)p) equiv left[{patop 1}right] + left[{patop 2}right]((m-1)p) + left[{patop 3}right]((m-1)p)^2 pmod {p^3},$$ since all other terms have a factor of $p^3$ in them.
- Actually, when $p>2$, $left[{patop 3}right]$ (as well as all other coefficients except $left[{patop 1}right]$) is divisible by $p$, so the quadratic term also vanishes, and we get $$f((m-1)p) equiv left[{patop 1}right] + left[{patop 2}right]((m-1)p) pmod {p^3}.$$ To see the divisibility by $p$, Glaisher compares the coefficients in $f(x+1)$ and $(x+1)f(x)$, and uses the known divisibility properties of binomial coefficients.
- Actually, when $p>3$, $left[{patop 2}right]$ is divisible by $p^2$, so the linear term vanishes, and we get $$f((m-1)p) equiv left[{patop 1}right] pmod{p^3}.$$ To see this, Glaisher expands $f(-p)=left[{patop 1}right]$, and then all terms except the $left[{patop 2}right]$ term have a factor of $p^2$ in them.
This completes the proof, since we've concluded that $f((m-1)p) equiv f(0) pmod{p^3}$, and since neither is divisible by $p$, we can divide and get $frac{f((m-1)p)}{f(0)} equiv 1 pmod{p^3}$.
answered Jan 27 at 18:13
Misha LavrovMisha Lavrov
47.9k657107
edited Jan 27 at 18:25
answered Jan 27 at 18:13
Misha LavrovMisha Lavrov
47.9k657107
answered Jan 27 at 18:13
Misha LavrovMisha Lavrov
47.9k657107
answered Jan 27 at 18:13
Misha LavrovMisha Lavrov
47.9k657107
47.9k657107
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3089806%2fwhy-binommp-1p-1-equiv-1-pmod-p3%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
$begingroup$
Assuming $p$ is supposed to be prime, then I try $p=2, m=2$ and get $binom 31=3neq 1 bmod 8$
$endgroup$
– Mark Bennet
Jan 27 at 16:54
2
$begingroup$
The $p ge 5$, $m=2$ cases are Wolstenholme's theorem. (The primes $p=2$ and $p=3$ already don't work.) Experimentally, though, the result does seem true for all $p ge 5$ and all $m$.
$endgroup$
– Misha Lavrov
Jan 27 at 17:17