Question

\(\text{For an odd prime p, verify that the sum}\\
\sum _{i=1}^{(p-1)}i^n= 0 \mod p \text{ or } \sum _{i=1}^{(p-1)}i^n= -1 \mod p\)

Answer 1

*

Answer 2

xD

Answer 3

*

Answer 4

-.-

Answer 5

*

Answer 6

now @Kainui and @PFEH.1999 left lol if they click on star as well no one left to solve

Answer 7

Check for \(n=1\).\[\sum _{i = 0}^{p-1}i = \frac{p(p-1)}{2} \equiv 0 \pmod{p}\]Maybe induction?

Answer 8

why not try if it works :D

Answer 9

thats a good idea !

Answer 10

since p is odd, 2|(p-1)
consequently the sum is a multiple of p

Answer 11

Yup, but that is only \(n=1\).

Answer 12

that clears the base case

Answer 13

well trying to know which numbers divisable by p-1 is a good step

Answer 14

the trick part is remainder is not 0 for all \(n\)

Answer 15

hmm its not hard though if u tried

Answer 16

it is easy if you allow me to use fermat's little thm

Answer 17

i think its solvable with fermat :D

Answer 18

im still trying the induction idea though as it looks interesting

Answer 19

By Fermat's little thm, \(a^{p-1}\equiv 1\pmod {p}\)
it follows \(a^n \equiv 1 \pmod {p}\) whenever \((p-1)|n\)

so the remainder for the sum in question would be \(1 + 1+ \cdots + (\text{p-1 times}) = p-1\equiv -1 \pmod{p}\)

Answer 20

need to work the case when \((p-1) \not |~ n \)

Answer 21

yaaay

Answer 22

\(\)

Answer 23

You spelled "*" wrong.

Answer 24

If we're still at the induction thingy, http://en.wikipedia.org/wiki/Faulhaber%27s_formula

Answer 25

I'm trying to see if that formula tells us anything about divisibility.

Answer 26

yeah u revealed zeta :P
but its ok , u can do that as well
i thought using NT would be much easy to make it introduction to zeta .

Answer 27

what is the maximum value for \(n\)

Answer 28

n can be anything

Answer 29

OK, yes, it seems that there's an (n+1) term in every expansion. So our sum is divisible by p?

Answer 30

ganesh already proved case one with p-1|n
it gives -1 remainder

Answer 31

u can mix with binomial idk there is many ways to prove its zero when p-1 dont divide n
pk try this by induction

Answer 32

well i checked induction works with first case :D

Answer 33

for case 1 wolfram is giving false

https://www.wolframalpha.com/input/?i=%5Csum+_%7Bi%3D1%7D%5E%7B%285-1%29%7Di%5E%7B100%7D+%28mod+5%29%3D+0+

Answer 34

assume p-1|n then p-1 dont divide n+1 (p-1) even

so we got by fermat
(1+2+3+4+.....+p-1)=p(p-1)/2 mod p=0 mod p since p-1 is even

now we need to try up to n+p

Answer 35

@mathmath333 case 1 when p-1|n it gives -1 mod not 0 :D

Answer 36

https://www.wolframalpha.com/input/?i=%5Csum+_%7Bi%3D1%7D%5E%7B%285-1%29%7Di%5E%7B100%7D+%28mod+5%29+%3D-1%28mod+5%29+

Answer 37

when \((p-1)\not | ~n\) :
Notice the bases in the sum \(B = \{1,2,3,\ldots,(p-1)\}\) are relatively prime to \(p\)

Next consider an integer \(r\) which is relatively prime to \(p\) and whose order is \(p-1\)

Since \(r\) is relatively prime to \(p\), the same holds for all powers of \(r\).
Hence \(r^k\) is congruent to some positive integer \(\in B\)

so the sum \(r^{0n}+r^{1n} + r^{2n} + \cdots + r^{n(p-2)}\) will be congruent to the sum in question.

\[r^{0n}+r^{1n} + r^{2n} + \cdots + r^{n(p-2)} = \dfrac{1-r^{(p-1)n}}{1-r^n} \equiv 0 \pmod {p}\]
\(\blacksquare\)

Answer 38

how did u get
last step ?

Answer 39

yes yes

Answer 40

\[ \dfrac{1-r^{(p-1)n}}{1-r^n} \]

do you agree the nujmerator is divisible by \(p\) ?

Answer 41

its perfect solution though :P
yes

Answer 42

i thought u used geometric series in like inverse way maybe xD

Answer 43

and the denominator is not divisible by \(p\)because we assumed that \((p-1) \not | ~n\)

consequently the fraction is divisible by \(p\)

Answer 44

ik ik how did u establish that
\(r^{0n}+r^{1n} + r^{2n} + \cdots + r^{n(p-2)} = \dfrac{1-r^{(p-1)n}}{1-r^n} \)

Answer 45

it helps to think of the fraction like this :

\[\dfrac{1-r^{(p-1)n}}{1-r^n} = \dfrac{(1-r^n)\times p\times (stuff)}{1-r^n}\]

Answer 46

hehe yeah amazing :D

Answer 47

remember this approach , will help incase u decided to learn zeta function ;)

Answer 48

i skipped many steps in my reply to keep it short, il be glad to try to answer if anyone has questions.. :)

Answer 49

teach me zeta function @Marki

Answer 50

maybe in a new post..

Answer 51

so when \(n-1| p\) it is \(-1\) and when \(n-1\not | p\) it is \(0\) ?

Answer 52

Exactly ^
still trying for a counter example ha :P

Answer 53

haha

Answer 54

haha wont find one its solid theorem :D

Answer 55

when \((p-1)|n\), the remainder is \(-1\)
otherwise it is \(0\)

Answer 56

yes yes , btw induction works good , start from p-1 |n
then check for z_(p-1)

n+1
n+2
n+3
n+4
.......

up to
n+p

Answer 57

at each time u'll gonna find geometric series which is known it divide p

Answer 58

some way :P

Answer 59

but i found @ganeshie8 solution more sense

Answer 60

:D thats it

Answer 61

induction looks neat, but i missed few replies above while cooking up the solution.. let me scroll up read them again :)

Answer 62

so you have induction proof for both cases ?

Answer 63

well u agree that DA gives all states?

Answer 64

so first case is p-1|n
gives -1 from Fermat ..

then we need to show by induction that other cases divides

Answer 65

or we need to show it gives 0 r -1 (ovs all gives 0)

Answer 66

got it ! you're inducting on n, pretty neat :)

Answer 67

*

Answer 68

lol kai its already been solved :P

Answer 69

I was just joking around =P