How prove this $(p-1)!left(1+frac12+frac13+cdots+frac1p-1right)equiv 0pmodp^2$ The Next CEO of Stack OverflowA proof of Wolstenholme's theoremWhy is this number always divisible by $p^2$Prove that $x^2 equiv a pmod2^e$ is solvable $forall e$ iff $a equiv 1 pmod8$How can prove this $sum_k=0^pbinompk(pm isqrt3)^kequiv 1pm (isqrt3)^p-psum_k=1^p-1frac(mp isqrt3)^kkpmodp^2?$Prove $a^pq equiv a pmod pq$How prove this $binomnmequiv 0pmod p$Prove that if $p>2$ is prime then $left(prod_k=1^p-1k^kright)^2equiv (-1)^fracp+12pmod p.$proving $1 + a + a^2 + cdots + a^h-1 equiv 0 pmodp$.How prove this diophantine equation $x^2-y^2equiv apmod p$ have only $p-1$rootsProve that if $ab equiv cd pmodn$ and $b equiv d pmod n$ and $gcd(b, n) = 1$ then $a equiv c pmod n$.$left(frac3p right)=1$ iff $pequiv 1pmod12$ or $pequiv -1pmod12$Prove $left(frac-3pright)=1$ if $pequiv 1 pmod 3$
Is it ok to trim down a tube patch?
0-rank tensor vs vector in 1D
Could a dragon use its wings to swim?
My ex-girlfriend uses my Apple ID to login to her iPad, do I have to give her my Apple ID password to reset it?
Defamation due to breach of confidentiality
From jafe to El-Guest
Touchpad not working on Debian 9
Which one is the true statement?
Traduction de « Life is a roller coaster »
Does the Idaho Potato Commission associate potato skins with healthy eating?
Is there a difference between "Fahrstuhl" and "Aufzug"?
Is it okay to majorly distort historical facts while writing a fiction story?
Easy to read palindrome checker
Can I calculate next year's exemptions based on this year's refund/amount owed?
Is there a way to save my career from absolute disaster?
Is there such a thing as a proper verb, like a proper noun?
Help! I cannot understand this game’s notations!
Small nick on power cord from an electric alarm clock, and copper wiring exposed but intact
Why doesn't UK go for the same deal Japan has with EU to resolve Brexit?
Is it convenient to ask the journal's editor for two additional days to complete a review?
How to Implement Deterministic Encryption Safely in .NET
Is a distribution that is normal, but highly skewed, considered Gaussian?
Graph of the history of databases
A question about free fall, velocity, and the height of an object.
How prove this $(p-1)!left(1+frac12+frac13+cdots+frac1p-1right)equiv 0pmodp^2$
The Next CEO of Stack OverflowA proof of Wolstenholme's theoremWhy is this number always divisible by $p^2$Prove that $x^2 equiv a pmod2^e$ is solvable $forall e$ iff $a equiv 1 pmod8$How can prove this $sum_k=0^pbinompk(pm isqrt3)^kequiv 1pm (isqrt3)^p-psum_k=1^p-1frac(mp isqrt3)^kkpmodp^2?$Prove $a^pq equiv a pmod pq$How prove this $binomnmequiv 0pmod p$Prove that if $p>2$ is prime then $left(prod_k=1^p-1k^kright)^2equiv (-1)^fracp+12pmod p.$proving $1 + a + a^2 + cdots + a^h-1 equiv 0 pmodp$.How prove this diophantine equation $x^2-y^2equiv apmod p$ have only $p-1$rootsProve that if $ab equiv cd pmodn$ and $b equiv d pmod n$ and $gcd(b, n) = 1$ then $a equiv c pmod n$.$left(frac3p right)=1$ iff $pequiv 1pmod12$ or $pequiv -1pmod12$Prove $left(frac-3pright)=1$ if $pequiv 1 pmod 3$
$begingroup$
Show that
$$(p-1)!left(1+dfrac12+dfrac13+cdots+dfrac1p-1right)equiv 0pmodp^2.$$
Maybe use this
$$dfrac1k+dfrac1p-k=dfracpk(p-k)$$
and then I can't. Can you help me to prove it?
Thank you.
elementary-number-theory
$endgroup$
|
show 2 more comments
$begingroup$
Show that
$$(p-1)!left(1+dfrac12+dfrac13+cdots+dfrac1p-1right)equiv 0pmodp^2.$$
Maybe use this
$$dfrac1k+dfrac1p-k=dfracpk(p-k)$$
and then I can't. Can you help me to prove it?
Thank you.
elementary-number-theory
$endgroup$
1
$begingroup$
Adapting Wilson's theorem mod $p^2$?
$endgroup$
– PITTALUGA
Nov 6 '13 at 12:09
$begingroup$
I think the general expression is not an integer; at least for p=3,5.
$endgroup$
– user99680
Nov 6 '13 at 12:15
1
$begingroup$
It is, since every denominator appears as a factor of $(p-1)!$.
$endgroup$
– Christoph
Nov 6 '13 at 12:16
2
$begingroup$
More is true: en.wikipedia.org/wiki/Wolstenholme%27s_theorem.
$endgroup$
– lhf
Nov 6 '13 at 12:17
$begingroup$
Ah, yes, I was adding incorrectly.
$endgroup$
– user99680
Nov 6 '13 at 12:18
|
show 2 more comments
$begingroup$
Show that
$$(p-1)!left(1+dfrac12+dfrac13+cdots+dfrac1p-1right)equiv 0pmodp^2.$$
Maybe use this
$$dfrac1k+dfrac1p-k=dfracpk(p-k)$$
and then I can't. Can you help me to prove it?
Thank you.
elementary-number-theory
$endgroup$
Show that
$$(p-1)!left(1+dfrac12+dfrac13+cdots+dfrac1p-1right)equiv 0pmodp^2.$$
Maybe use this
$$dfrac1k+dfrac1p-k=dfracpk(p-k)$$
and then I can't. Can you help me to prove it?
Thank you.
elementary-number-theory
elementary-number-theory
edited Mar 15 '16 at 10:37
user26857
39.5k124283
39.5k124283
asked Nov 6 '13 at 12:04
user94270
1
$begingroup$
Adapting Wilson's theorem mod $p^2$?
$endgroup$
– PITTALUGA
Nov 6 '13 at 12:09
$begingroup$
I think the general expression is not an integer; at least for p=3,5.
$endgroup$
– user99680
Nov 6 '13 at 12:15
1
$begingroup$
It is, since every denominator appears as a factor of $(p-1)!$.
$endgroup$
– Christoph
Nov 6 '13 at 12:16
2
$begingroup$
More is true: en.wikipedia.org/wiki/Wolstenholme%27s_theorem.
$endgroup$
– lhf
Nov 6 '13 at 12:17
$begingroup$
Ah, yes, I was adding incorrectly.
$endgroup$
– user99680
Nov 6 '13 at 12:18
|
show 2 more comments
1
$begingroup$
Adapting Wilson's theorem mod $p^2$?
$endgroup$
– PITTALUGA
Nov 6 '13 at 12:09
$begingroup$
I think the general expression is not an integer; at least for p=3,5.
$endgroup$
– user99680
Nov 6 '13 at 12:15
1
$begingroup$
It is, since every denominator appears as a factor of $(p-1)!$.
$endgroup$
– Christoph
Nov 6 '13 at 12:16
2
$begingroup$
More is true: en.wikipedia.org/wiki/Wolstenholme%27s_theorem.
$endgroup$
– lhf
Nov 6 '13 at 12:17
$begingroup$
Ah, yes, I was adding incorrectly.
$endgroup$
– user99680
Nov 6 '13 at 12:18
1
1
$begingroup$
Adapting Wilson's theorem mod $p^2$?
$endgroup$
– PITTALUGA
Nov 6 '13 at 12:09
$begingroup$
Adapting Wilson's theorem mod $p^2$?
$endgroup$
– PITTALUGA
Nov 6 '13 at 12:09
$begingroup$
I think the general expression is not an integer; at least for p=3,5.
$endgroup$
– user99680
Nov 6 '13 at 12:15
$begingroup$
I think the general expression is not an integer; at least for p=3,5.
$endgroup$
– user99680
Nov 6 '13 at 12:15
1
1
$begingroup$
It is, since every denominator appears as a factor of $(p-1)!$.
$endgroup$
– Christoph
Nov 6 '13 at 12:16
$begingroup$
It is, since every denominator appears as a factor of $(p-1)!$.
$endgroup$
– Christoph
Nov 6 '13 at 12:16
2
2
$begingroup$
More is true: en.wikipedia.org/wiki/Wolstenholme%27s_theorem.
$endgroup$
– lhf
Nov 6 '13 at 12:17
$begingroup$
More is true: en.wikipedia.org/wiki/Wolstenholme%27s_theorem.
$endgroup$
– lhf
Nov 6 '13 at 12:17
$begingroup$
Ah, yes, I was adding incorrectly.
$endgroup$
– user99680
Nov 6 '13 at 12:18
$begingroup$
Ah, yes, I was adding incorrectly.
$endgroup$
– user99680
Nov 6 '13 at 12:18
|
show 2 more comments
3 Answers
3
active
oldest
votes
$begingroup$
The solution below is adapted from Notes on Wolstenholme’s Theorem by Timothy H. Choi.
Let
$$
S=(p-1)!sum_k=1^p-1 frac1k
$$
Using your insight
$$
dfrac1k+dfrac1p-k=dfracpk(p-k)
$$
we have
$$
2S=(p-1)!sum_k=1^p-1 left(dfrac1k+dfrac1p-kright) =
psum_k=1^p-1 frac(p-1)!k(p-k) = pS'
$$
Note that $S'$ is an integer. Now
$$
frac(p-1)!k(p-k) equiv (k^2)^-1 bmod p
$$
where the inverse is taken $bmod p$. This is a consequence of Wilson’s Theorem.
Hence
$$
S'equiv
sum_k=1^p-1 (k^2)^-1 equiv
sum_k=1^p-1 k^2 = frac(p-1)p(2(p-1)+1)6 equiv 0 bmod p
$$
This means that $2Sequiv 0 bmod p^2$ and so $Sequiv 0 bmod p^2$. (We need $p>3$ twice here.)
$endgroup$
add a comment |
$begingroup$
As others have noted, the congruence is not true for $p=3$, since
$$ 2!left(1+frac 1 2right)=2+1=3,$$
which is not divisible by $9$. We can still use what you suggested to prove the congruence holds $operatornamemod p$. Let $p$ be an odd prime, then
beginalign*
(p-1)!sum_k=1^p-1 frac 1 k &= (p-1)! sum_k=1^(p-1)/2 left(frac 1 k + frac 1 p-kright) \&= (p-1)!sum_k=1^(p-1)/2 fracpk(p-k) = psum_k=1^(p-1)/2 frac(p-1)!k(p-k).
endalign*
Since $(p-1)!$ always contains $k$ and $(p-k)$ as a factor, the fractions in the sum are integers and the result is a multiple of $p$.
See lhf's answer for why it is even a multiple of $p^2$ as long as $p>3$.
$endgroup$
$begingroup$
The congruence will hold for any $p>3$ modulo $p^2$. That's Wolstenholme's theorem as lhf pointed out.
$endgroup$
– EuYu
Nov 6 '13 at 12:39
1
$begingroup$
I adapted my post and referencered lhf's answer, thanks for your comment!
$endgroup$
– Christoph
Nov 6 '13 at 12:54
add a comment |
$begingroup$
I came up with this proof while I work on this problem.
We write $f(x) equiv_p g(x)$ if polynomials $f(x), g(x) in mathbbZ[x]$ satisfies $a_iequiv b_i$ mod $p$ for all coefficients $a_i$ of $f(x)$, and $b_i$ of $g(x)$.
Then we have by Fermat's theorem,
$$
x^p-1-1 equiv_p (x-1)(x-2) cdots (x-(p-1)).
$$
Group the numbers in pairs as discussed here already,
$$
frac 11+frac 1p-1=frac p1(p-1), frac12+ frac 1p-2=frac p2(p-2), cdots, frac 1(p-1)/2+frac1(p+1)/2=frac p (p-1)(p+1)/4 .
$$
Each group has numerator divisible by $p$. Then it suffices to prove that the numerator $N$ in
$$
sum_j=1^(p-1)/2 frac 1j(p-j)=frac N(p-1)! (*)
$$
is divisible by $p$.
We may write
beginalign*x^p-1-1&equiv_p
(x-1)(x-2)cdots (x-(p-1))\ &= prod_j=1^(p-1)/2 (x-j)(x-(p-j)) \ &=prod_j=1^(p-1)/2 (x^2-(j+(p-j))x + j(p-j))\
&equiv_pprod_j=1^(p-1)/2 (x^2+j(p-j))
endalign*
Expanding the last product, we find that $N$ is the coefficient of $x^2$. Since $pgeq 5$, the coefficient of $x^2$ in the product must be divisible by $p$. Hence, $p|N$ as desired.
$endgroup$
add a comment |
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%2f554261%2fhow-prove-this-p-1-left1-frac12-frac13-cdots-frac1p-1-right%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The solution below is adapted from Notes on Wolstenholme’s Theorem by Timothy H. Choi.
Let
$$
S=(p-1)!sum_k=1^p-1 frac1k
$$
Using your insight
$$
dfrac1k+dfrac1p-k=dfracpk(p-k)
$$
we have
$$
2S=(p-1)!sum_k=1^p-1 left(dfrac1k+dfrac1p-kright) =
psum_k=1^p-1 frac(p-1)!k(p-k) = pS'
$$
Note that $S'$ is an integer. Now
$$
frac(p-1)!k(p-k) equiv (k^2)^-1 bmod p
$$
where the inverse is taken $bmod p$. This is a consequence of Wilson’s Theorem.
Hence
$$
S'equiv
sum_k=1^p-1 (k^2)^-1 equiv
sum_k=1^p-1 k^2 = frac(p-1)p(2(p-1)+1)6 equiv 0 bmod p
$$
This means that $2Sequiv 0 bmod p^2$ and so $Sequiv 0 bmod p^2$. (We need $p>3$ twice here.)
$endgroup$
add a comment |
$begingroup$
The solution below is adapted from Notes on Wolstenholme’s Theorem by Timothy H. Choi.
Let
$$
S=(p-1)!sum_k=1^p-1 frac1k
$$
Using your insight
$$
dfrac1k+dfrac1p-k=dfracpk(p-k)
$$
we have
$$
2S=(p-1)!sum_k=1^p-1 left(dfrac1k+dfrac1p-kright) =
psum_k=1^p-1 frac(p-1)!k(p-k) = pS'
$$
Note that $S'$ is an integer. Now
$$
frac(p-1)!k(p-k) equiv (k^2)^-1 bmod p
$$
where the inverse is taken $bmod p$. This is a consequence of Wilson’s Theorem.
Hence
$$
S'equiv
sum_k=1^p-1 (k^2)^-1 equiv
sum_k=1^p-1 k^2 = frac(p-1)p(2(p-1)+1)6 equiv 0 bmod p
$$
This means that $2Sequiv 0 bmod p^2$ and so $Sequiv 0 bmod p^2$. (We need $p>3$ twice here.)
$endgroup$
add a comment |
$begingroup$
The solution below is adapted from Notes on Wolstenholme’s Theorem by Timothy H. Choi.
Let
$$
S=(p-1)!sum_k=1^p-1 frac1k
$$
Using your insight
$$
dfrac1k+dfrac1p-k=dfracpk(p-k)
$$
we have
$$
2S=(p-1)!sum_k=1^p-1 left(dfrac1k+dfrac1p-kright) =
psum_k=1^p-1 frac(p-1)!k(p-k) = pS'
$$
Note that $S'$ is an integer. Now
$$
frac(p-1)!k(p-k) equiv (k^2)^-1 bmod p
$$
where the inverse is taken $bmod p$. This is a consequence of Wilson’s Theorem.
Hence
$$
S'equiv
sum_k=1^p-1 (k^2)^-1 equiv
sum_k=1^p-1 k^2 = frac(p-1)p(2(p-1)+1)6 equiv 0 bmod p
$$
This means that $2Sequiv 0 bmod p^2$ and so $Sequiv 0 bmod p^2$. (We need $p>3$ twice here.)
$endgroup$
The solution below is adapted from Notes on Wolstenholme’s Theorem by Timothy H. Choi.
Let
$$
S=(p-1)!sum_k=1^p-1 frac1k
$$
Using your insight
$$
dfrac1k+dfrac1p-k=dfracpk(p-k)
$$
we have
$$
2S=(p-1)!sum_k=1^p-1 left(dfrac1k+dfrac1p-kright) =
psum_k=1^p-1 frac(p-1)!k(p-k) = pS'
$$
Note that $S'$ is an integer. Now
$$
frac(p-1)!k(p-k) equiv (k^2)^-1 bmod p
$$
where the inverse is taken $bmod p$. This is a consequence of Wilson’s Theorem.
Hence
$$
S'equiv
sum_k=1^p-1 (k^2)^-1 equiv
sum_k=1^p-1 k^2 = frac(p-1)p(2(p-1)+1)6 equiv 0 bmod p
$$
This means that $2Sequiv 0 bmod p^2$ and so $Sequiv 0 bmod p^2$. (We need $p>3$ twice here.)
edited Nov 6 '13 at 12:56
answered Nov 6 '13 at 12:49
lhflhf
167k11172403
167k11172403
add a comment |
add a comment |
$begingroup$
As others have noted, the congruence is not true for $p=3$, since
$$ 2!left(1+frac 1 2right)=2+1=3,$$
which is not divisible by $9$. We can still use what you suggested to prove the congruence holds $operatornamemod p$. Let $p$ be an odd prime, then
beginalign*
(p-1)!sum_k=1^p-1 frac 1 k &= (p-1)! sum_k=1^(p-1)/2 left(frac 1 k + frac 1 p-kright) \&= (p-1)!sum_k=1^(p-1)/2 fracpk(p-k) = psum_k=1^(p-1)/2 frac(p-1)!k(p-k).
endalign*
Since $(p-1)!$ always contains $k$ and $(p-k)$ as a factor, the fractions in the sum are integers and the result is a multiple of $p$.
See lhf's answer for why it is even a multiple of $p^2$ as long as $p>3$.
$endgroup$
$begingroup$
The congruence will hold for any $p>3$ modulo $p^2$. That's Wolstenholme's theorem as lhf pointed out.
$endgroup$
– EuYu
Nov 6 '13 at 12:39
1
$begingroup$
I adapted my post and referencered lhf's answer, thanks for your comment!
$endgroup$
– Christoph
Nov 6 '13 at 12:54
add a comment |
$begingroup$
As others have noted, the congruence is not true for $p=3$, since
$$ 2!left(1+frac 1 2right)=2+1=3,$$
which is not divisible by $9$. We can still use what you suggested to prove the congruence holds $operatornamemod p$. Let $p$ be an odd prime, then
beginalign*
(p-1)!sum_k=1^p-1 frac 1 k &= (p-1)! sum_k=1^(p-1)/2 left(frac 1 k + frac 1 p-kright) \&= (p-1)!sum_k=1^(p-1)/2 fracpk(p-k) = psum_k=1^(p-1)/2 frac(p-1)!k(p-k).
endalign*
Since $(p-1)!$ always contains $k$ and $(p-k)$ as a factor, the fractions in the sum are integers and the result is a multiple of $p$.
See lhf's answer for why it is even a multiple of $p^2$ as long as $p>3$.
$endgroup$
$begingroup$
The congruence will hold for any $p>3$ modulo $p^2$. That's Wolstenholme's theorem as lhf pointed out.
$endgroup$
– EuYu
Nov 6 '13 at 12:39
1
$begingroup$
I adapted my post and referencered lhf's answer, thanks for your comment!
$endgroup$
– Christoph
Nov 6 '13 at 12:54
add a comment |
$begingroup$
As others have noted, the congruence is not true for $p=3$, since
$$ 2!left(1+frac 1 2right)=2+1=3,$$
which is not divisible by $9$. We can still use what you suggested to prove the congruence holds $operatornamemod p$. Let $p$ be an odd prime, then
beginalign*
(p-1)!sum_k=1^p-1 frac 1 k &= (p-1)! sum_k=1^(p-1)/2 left(frac 1 k + frac 1 p-kright) \&= (p-1)!sum_k=1^(p-1)/2 fracpk(p-k) = psum_k=1^(p-1)/2 frac(p-1)!k(p-k).
endalign*
Since $(p-1)!$ always contains $k$ and $(p-k)$ as a factor, the fractions in the sum are integers and the result is a multiple of $p$.
See lhf's answer for why it is even a multiple of $p^2$ as long as $p>3$.
$endgroup$
As others have noted, the congruence is not true for $p=3$, since
$$ 2!left(1+frac 1 2right)=2+1=3,$$
which is not divisible by $9$. We can still use what you suggested to prove the congruence holds $operatornamemod p$. Let $p$ be an odd prime, then
beginalign*
(p-1)!sum_k=1^p-1 frac 1 k &= (p-1)! sum_k=1^(p-1)/2 left(frac 1 k + frac 1 p-kright) \&= (p-1)!sum_k=1^(p-1)/2 fracpk(p-k) = psum_k=1^(p-1)/2 frac(p-1)!k(p-k).
endalign*
Since $(p-1)!$ always contains $k$ and $(p-k)$ as a factor, the fractions in the sum are integers and the result is a multiple of $p$.
See lhf's answer for why it is even a multiple of $p^2$ as long as $p>3$.
edited Apr 13 '17 at 12:20
Community♦
1
1
answered Nov 6 '13 at 12:30
ChristophChristoph
12.5k1642
12.5k1642
$begingroup$
The congruence will hold for any $p>3$ modulo $p^2$. That's Wolstenholme's theorem as lhf pointed out.
$endgroup$
– EuYu
Nov 6 '13 at 12:39
1
$begingroup$
I adapted my post and referencered lhf's answer, thanks for your comment!
$endgroup$
– Christoph
Nov 6 '13 at 12:54
add a comment |
$begingroup$
The congruence will hold for any $p>3$ modulo $p^2$. That's Wolstenholme's theorem as lhf pointed out.
$endgroup$
– EuYu
Nov 6 '13 at 12:39
1
$begingroup$
I adapted my post and referencered lhf's answer, thanks for your comment!
$endgroup$
– Christoph
Nov 6 '13 at 12:54
$begingroup$
The congruence will hold for any $p>3$ modulo $p^2$. That's Wolstenholme's theorem as lhf pointed out.
$endgroup$
– EuYu
Nov 6 '13 at 12:39
$begingroup$
The congruence will hold for any $p>3$ modulo $p^2$. That's Wolstenholme's theorem as lhf pointed out.
$endgroup$
– EuYu
Nov 6 '13 at 12:39
1
1
$begingroup$
I adapted my post and referencered lhf's answer, thanks for your comment!
$endgroup$
– Christoph
Nov 6 '13 at 12:54
$begingroup$
I adapted my post and referencered lhf's answer, thanks for your comment!
$endgroup$
– Christoph
Nov 6 '13 at 12:54
add a comment |
$begingroup$
I came up with this proof while I work on this problem.
We write $f(x) equiv_p g(x)$ if polynomials $f(x), g(x) in mathbbZ[x]$ satisfies $a_iequiv b_i$ mod $p$ for all coefficients $a_i$ of $f(x)$, and $b_i$ of $g(x)$.
Then we have by Fermat's theorem,
$$
x^p-1-1 equiv_p (x-1)(x-2) cdots (x-(p-1)).
$$
Group the numbers in pairs as discussed here already,
$$
frac 11+frac 1p-1=frac p1(p-1), frac12+ frac 1p-2=frac p2(p-2), cdots, frac 1(p-1)/2+frac1(p+1)/2=frac p (p-1)(p+1)/4 .
$$
Each group has numerator divisible by $p$. Then it suffices to prove that the numerator $N$ in
$$
sum_j=1^(p-1)/2 frac 1j(p-j)=frac N(p-1)! (*)
$$
is divisible by $p$.
We may write
beginalign*x^p-1-1&equiv_p
(x-1)(x-2)cdots (x-(p-1))\ &= prod_j=1^(p-1)/2 (x-j)(x-(p-j)) \ &=prod_j=1^(p-1)/2 (x^2-(j+(p-j))x + j(p-j))\
&equiv_pprod_j=1^(p-1)/2 (x^2+j(p-j))
endalign*
Expanding the last product, we find that $N$ is the coefficient of $x^2$. Since $pgeq 5$, the coefficient of $x^2$ in the product must be divisible by $p$. Hence, $p|N$ as desired.
$endgroup$
add a comment |
$begingroup$
I came up with this proof while I work on this problem.
We write $f(x) equiv_p g(x)$ if polynomials $f(x), g(x) in mathbbZ[x]$ satisfies $a_iequiv b_i$ mod $p$ for all coefficients $a_i$ of $f(x)$, and $b_i$ of $g(x)$.
Then we have by Fermat's theorem,
$$
x^p-1-1 equiv_p (x-1)(x-2) cdots (x-(p-1)).
$$
Group the numbers in pairs as discussed here already,
$$
frac 11+frac 1p-1=frac p1(p-1), frac12+ frac 1p-2=frac p2(p-2), cdots, frac 1(p-1)/2+frac1(p+1)/2=frac p (p-1)(p+1)/4 .
$$
Each group has numerator divisible by $p$. Then it suffices to prove that the numerator $N$ in
$$
sum_j=1^(p-1)/2 frac 1j(p-j)=frac N(p-1)! (*)
$$
is divisible by $p$.
We may write
beginalign*x^p-1-1&equiv_p
(x-1)(x-2)cdots (x-(p-1))\ &= prod_j=1^(p-1)/2 (x-j)(x-(p-j)) \ &=prod_j=1^(p-1)/2 (x^2-(j+(p-j))x + j(p-j))\
&equiv_pprod_j=1^(p-1)/2 (x^2+j(p-j))
endalign*
Expanding the last product, we find that $N$ is the coefficient of $x^2$. Since $pgeq 5$, the coefficient of $x^2$ in the product must be divisible by $p$. Hence, $p|N$ as desired.
$endgroup$
add a comment |
$begingroup$
I came up with this proof while I work on this problem.
We write $f(x) equiv_p g(x)$ if polynomials $f(x), g(x) in mathbbZ[x]$ satisfies $a_iequiv b_i$ mod $p$ for all coefficients $a_i$ of $f(x)$, and $b_i$ of $g(x)$.
Then we have by Fermat's theorem,
$$
x^p-1-1 equiv_p (x-1)(x-2) cdots (x-(p-1)).
$$
Group the numbers in pairs as discussed here already,
$$
frac 11+frac 1p-1=frac p1(p-1), frac12+ frac 1p-2=frac p2(p-2), cdots, frac 1(p-1)/2+frac1(p+1)/2=frac p (p-1)(p+1)/4 .
$$
Each group has numerator divisible by $p$. Then it suffices to prove that the numerator $N$ in
$$
sum_j=1^(p-1)/2 frac 1j(p-j)=frac N(p-1)! (*)
$$
is divisible by $p$.
We may write
beginalign*x^p-1-1&equiv_p
(x-1)(x-2)cdots (x-(p-1))\ &= prod_j=1^(p-1)/2 (x-j)(x-(p-j)) \ &=prod_j=1^(p-1)/2 (x^2-(j+(p-j))x + j(p-j))\
&equiv_pprod_j=1^(p-1)/2 (x^2+j(p-j))
endalign*
Expanding the last product, we find that $N$ is the coefficient of $x^2$. Since $pgeq 5$, the coefficient of $x^2$ in the product must be divisible by $p$. Hence, $p|N$ as desired.
$endgroup$
I came up with this proof while I work on this problem.
We write $f(x) equiv_p g(x)$ if polynomials $f(x), g(x) in mathbbZ[x]$ satisfies $a_iequiv b_i$ mod $p$ for all coefficients $a_i$ of $f(x)$, and $b_i$ of $g(x)$.
Then we have by Fermat's theorem,
$$
x^p-1-1 equiv_p (x-1)(x-2) cdots (x-(p-1)).
$$
Group the numbers in pairs as discussed here already,
$$
frac 11+frac 1p-1=frac p1(p-1), frac12+ frac 1p-2=frac p2(p-2), cdots, frac 1(p-1)/2+frac1(p+1)/2=frac p (p-1)(p+1)/4 .
$$
Each group has numerator divisible by $p$. Then it suffices to prove that the numerator $N$ in
$$
sum_j=1^(p-1)/2 frac 1j(p-j)=frac N(p-1)! (*)
$$
is divisible by $p$.
We may write
beginalign*x^p-1-1&equiv_p
(x-1)(x-2)cdots (x-(p-1))\ &= prod_j=1^(p-1)/2 (x-j)(x-(p-j)) \ &=prod_j=1^(p-1)/2 (x^2-(j+(p-j))x + j(p-j))\
&equiv_pprod_j=1^(p-1)/2 (x^2+j(p-j))
endalign*
Expanding the last product, we find that $N$ is the coefficient of $x^2$. Since $pgeq 5$, the coefficient of $x^2$ in the product must be divisible by $p$. Hence, $p|N$ as desired.
answered Mar 27 at 22:33
i707107i707107
12.6k21647
12.6k21647
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%2f554261%2fhow-prove-this-p-1-left1-frac12-frac13-cdots-frac1p-1-right%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
1
$begingroup$
Adapting Wilson's theorem mod $p^2$?
$endgroup$
– PITTALUGA
Nov 6 '13 at 12:09
$begingroup$
I think the general expression is not an integer; at least for p=3,5.
$endgroup$
– user99680
Nov 6 '13 at 12:15
1
$begingroup$
It is, since every denominator appears as a factor of $(p-1)!$.
$endgroup$
– Christoph
Nov 6 '13 at 12:16
2
$begingroup$
More is true: en.wikipedia.org/wiki/Wolstenholme%27s_theorem.
$endgroup$
– lhf
Nov 6 '13 at 12:17
$begingroup$
Ah, yes, I was adding incorrectly.
$endgroup$
– user99680
Nov 6 '13 at 12:18