Question

\(p\) is a an odd prime number.prove that
\( 1^{p-1} + 2^{p-1} + 3^{p-1} + ... + (p-1)^{p-1} \equiv p + (p-1)! ~~ (mod ~ p^2) \)

Answer 1

I'm very sorry, I don't know your answer since I'm not an expert in discrete mathematics

Answer 2

no prob ;) i just asked it for fun ;)

Answer 3

Wilson theorem!

Answer 4

My intuition is telling me that p and (p-1)! come from the binomial theorem, and the reason it's prime is so mod (p^2) has no other weird divisors to cut it up possibly. Other than that, I know how to derive individual results for sum of squares, cubes, etc... but not really sure how to take it from here yet, but maybe this helps someone out or they can correct me.

Answer 5

Here's some math that might get us to something to play with: \[\Large \sum_{n=1}^{p-1}(n+1)^{p-1}-n^{p-1}=p^{p-1}-1\] start with this telescoping series. Apply the binomial theorem on the first term in the sum and then immediately pull out the first term to cancel out with the other term leaving us with: \[\Large \sum_{n=1}^{p-1}\sum_{k=1}^{p-1}\left(\begin{matrix}p-1 \\ k\end{matrix}\right)n^{p-1-k} = p^{p-1}-1 \] Now I'm thinking where to go from here.

Answer 6

\[\Large \sum_{n=1}^{p-1}n^{p-1} = p+(p-1)! \mod (p^2)\] Is closely related to what I have up there, but it needs some tweaking to make it fit... bleh I don't know lol.

Answer 7

Alright I'm looking up wilson theorem I give up lol

Answer 8

Alternative statement, tried to do the gauss method lol. \[\Large \frac{1}{2} \sum_{n=1}^{\frac{p-1}{2}} \left[ (p-n)^{p-1}+n^{p-1} \right] \equiv p+(p-1)! \mod(p^2) \]

Answer 9

@ganeshie8 it's mod p^2..wilson thm would not seem useful.
guys a small help:u can cleverly use Fermat's little thm ;)

Answer 10

consider that \(i^{p-1} \equiv 1 ~~ (mod ~ p)\) so \(\Large \frac{ i^{p-1}-1 }{ p }\) is an integer.

Answer 11

are u using this ?
\(1^{p-1}=1 \mod p\)
\(1^{p-1}=1 \mod p^2\)

Answer 12

hmm im trying this
\(a^{\phi (p^2)}=1 \mod p^2\\
a^{p^2-p}=1 \mod p^2\\
a^{p-1}a^p=1 \mod p^2\\ \)

Answer 13

not a bad idea,but as i said,if we consider that an integer,then we can prove it.

Answer 14

\(\large \phi(p^2) = p(p-1)\) would help?

Answer 15

btw i wish @ganeshie8 was here working with him makes it more fun , it remindes me with Wilson as well

Answer 16

yes we can use wilson thm but at the finishing of the proof! u want to see a part of the proof?

Answer 17

By wilson
\[(p-1)! \equiv -1\pmod p\]
multiplying \(p\) through out gives
\[p(p-1)! \equiv -p\pmod {p^2}\]

adding \(p^2\) both sides
\[p[p+(p-1)!] \equiv p(p-1)\pmod {p^2}\]

fermat gives
\[1^{p-1}+2^{p-1}+\cdots + (p-1)^{p-1}\equiv 1+1+\cdots + (p-1~\text{times})\\\equiv p-1 \pmod {p}\]
\(\cdots\)

Answer 18

i dont get it yet >.<

Answer 19

yeah thats not a proof, actually i got stuck after that :P

Answer 20

hahaha

Answer 21

\[p[p+(p-1)!] \equiv p(p-1)\pmod {p^2}\]

this should be easy to see right ?

Answer 22

yes but how does it help

Answer 23

i got excited by noticing the p+(p-1)! term on left hand side

Answer 24

did u get why fermat gives
\[1^{p-1}+2^{p-1}+\cdots + (p-1)^{p-1}\equiv 1+1+\cdots + (p-1~\text{times})\\\equiv p-1 \pmod {p}\]

?

Answer 25

hmmm it should be p(p-1)/2 , right ?

Answer 26

\[a^{p-1}\equiv 1\pmod p \]
since there are \(p-1\) terms in the sum, the sum evaluates to \(p-1\) in mod \(p\)

Answer 27

but its not easy to work \(p^2\) here

Answer 28

ok lol got it xD i was seeing something else with that sum wew!

Answer 29

keep the idea i gave you'll be able to prove it.

Answer 30

dont reveal the proof or hints

Answer 31

I end up with \[p[1^{p-1} + 2^{p-1} + 3^{p-1} + ... + (p-1)^{p-1}] \equiv p[p + (p-1)! ]\pmod {p^2}\]

but we cannot cancel p just like that :/

ok im ready for hint if others are also ready..

Answer 32

@Marki

Answer 33

hehe i died already xD

Answer 34

i won't reveal ;) i'm eager to see ur ideas and gather them too :)

Answer 35

well,consider that if we suppose \( r_{i} = \Large \frac{ i^{p-1}-1 }{ p } \)
\( \prod_{i=1}^{p-1}i^{p-1} = \prod_{i=1}^{p-1}pr_{i}+1 = (pr_{1}+1)(pr_{2}+1)...(pr_{p-1}+1)\equiv 1+ p(r_1 + r_2 +... r_{p-1}) \)

Answer 36

as \( p^2 | (pr_i)(pr_j) \) of the product of more than 2 of them

Answer 37

u know and \( \prod_{i=1}^{p-1}i^{p-1} = (\prod_{i=1}^{p-1}i)^{p-1} \)

Answer 38

now use wilson thm ;)

Answer 39

Amazing! okay that equals \((p-1)!^{p-1}\) and by wilson thm does that reduce to \(1\pmod p\) ?

Answer 40

and you have \[\prod_{i=1}^{p-1}i^{p-1} \equiv 1+ p(r_1 + r_2 +... r_{p-1})\pmod{p^2}\]

Answer 41

it how are you going to combine them xD

Answer 42

nice ;) keep going.

Answer 43

i guess next step would be \[\sum \limits_{i=1}^{p-1}i^{p-1} \equiv \sum \limits_{i=1}^{p-1}(1+pr_i) \equiv p-1 + p(r_1 + r_2 +... r_{p-1})\pmod{p^2}\]

Answer 44

correct ;)

Answer 45

then so far we have :\[\sum \limits_{i=1}^{p-1}i^{p-1} \equiv p-2+ (p-1)!^{p-1}\pmod{p^2}\]

Answer 46

that right hand side has to reduce to p + (p-1)! somehow
interesting, i don't see how wilson helps here yet :O

Answer 47

well,we can do the same thing as we did!how about write \( \Large \frac{(p-1)! +2}{p} = r\) and find \( (p-1)!^{p-1} \) from this and play with ?

Answer 48

i give up :|

Answer 49

Oh yes i know you meant
\[\frac{(p-1)! +1}{p} = r\]

right ?

Answer 50

@Marki this is going to be fun xD we're almost done here

Answer 51

sry yes ;)

Answer 52

\[(p-1)!^{p-1} \equiv (-1+pr)^{p-1} \equiv (pr-1)^{p-1} \equiv pr + 1 \pmod{p^2}\]

Answer 53

does that look okay ? i think il need to replace r

Answer 54

awesome ;)

Answer 55

but wait,it would be \( 1 - rp(p-1) \) not \( pr+1 \)

Answer 56

:O

Answer 57

(Awesome+1)!^(Awesome)

this is the coolest NT proof i have seen in like months

Answer 58

\(1-rp(p-1)\equiv pr+1 \pmod {p^2}\) @PFEH.1999

Answer 59

oh correct ;)

Answer 60

so it would be simply done ;)

Answer 61

pluggin back r we get

\[\begin{align}(p-1)!^{p-1} \equiv (-1+pr)^{p-1} \equiv (pr-1)^{p-1} &\equiv pr + 1 \pmod{p^2}\\~\\
&\equiv (p-1)!+2 \pmod{p^2}
\end{align}\]

Answer 62

finally
\[\sum \limits_{i=1}^{p-1}i^{p-1} \equiv p-2+ (p-1)!^{p-1}\pmod{p^2}\]

becomes

\[\sum \limits_{i=1}^{p-1}i^{p-1} \equiv p + (p-1)!\pmod{p^2}\]

XD

Answer 63

nice ;) this problem is really awesome,don't u think so?

Answer 64

yes i do :D

Answer 65

well,i'll come with more exciting problems ;)

Answer 66

so btw does this reduce the problem to
-(p+1) mod p^2 ?

Answer 67

what?!

Answer 68

wil look forward to attempt them @PFEH.1999 xD
@Marki are u trying to reduce p + (p-1)! in mod p^2 ?

Answer 69

like show that
\(1^{p-1} + 2^{p-1} + 3^{p-1} + ... + (p-1)^{p-1} \equiv p + (p-1)!\equiv -(p+1) ~~ (mod ~ p^2)\)

Answer 70

i think below is trivially true by fermat's little thm : \[1^{p-1} + 2^{p-1} + 3^{p-1} + ... + (p-1)^{p-1} \equiv p-1 \pmod p\]

but \(\mod p^2\) wont reduce further

Answer 71

i had a feeling it would work

Answer 72

http://www.wolframalpha.com/input/?i=%5Csum%5Climits_%7Bn%3D1%7D%5E%2829-1%29+n%5E%2829-1%29-%2829%2B1%29+mod+29%5E2

Answer 73

well,not true XD
\( p =5 \) so \( 5+ 24 \equiv -6 \) but 35 is not divisble by 25.

Answer 74

haha i see :P

Answer 75

@ganeshie8 , awesome site ;) i tried to give it a 20 digits number to tell me whether it's prime or not ;D

Answer 76

lol @PFEH.1999 u havnt troll it enough :P

Answer 77

:D

Answer 78

a guy told me if u want to improve ur mind before sleeping try to check all primes smaller than 2000 !

Answer 79

i havn't tried so far ;) i'm afraid i might burn my mind XD

Answer 80

interesting , i do similar stuff but mostly it distract me and keep me away from sleep

Answer 81

try to find the happy numbers lol xD
or weird numbers

Answer 82

it would be more quick than primes

Answer 83

i would like other question xD

Answer 84

it's easier ;)

Answer 85

ahaha xD its painful who said that counting sheep makes u sleep
like if i tried to work on numbers before sleep that means no sleep at all