OliForum Matematico

Determinare in funzione di $ k $ e $ p $ ($ k,p \in \mathbb{N} $ e $ p $ primo) il resto della divisione per $ p $ della somma
$ 1^k+2^k+\dots+(p-1)^k $

Osservazione forse strampalata: se k è primo e non divide p-1 dovrebbe venire 0.

Claim azzeccato, ora la dimostrazione

EDIT: Avevo letto male, era tardi, il claim azzeccato è quello di darkcrystal

Beh, se è per quello basta che k sia dispari: infatti accoppiando i termini di residui opposti (1 con p-1, 2 con p-2...) si annullano tutti.
Il problema sono i pari... suvvia, io avrei una soluzione... se la mia dimostrazione non è sbagliata non è impossibile, voglio aspettare ancora qualche giorno per vedere se qualcuno lo risolve!

Comunque, il mio claim: il resto è sempre 0 a meno che p-1 | k.

Ciao!

O è in corso una candid camera alle mie spalle, o in questo periodo vanno di moda i generatori moltiplicativi...

Quarto post consecutivo sul Teorema dell'Elemento Primitivo.

Sia dunque g un elemento primitivo mod p.

La somma a primo membro può essere riscritta, dopo aver riordinato i termini come

/*1^k + 2^k + ... + (p-1)^k = \left( g^0 \right)^k + \left( g^1 \right)^k + \left( g^2 \right)^k + \cdots \left( g^{p-2} \right)^k = g^{0} + g^{k} + g^{2k} + \cdots g^{(p-2)k}*/.

Se /*g^k = 1 \pmod p*/, cosa che avviene sse k | p-1, allora la somma fa ovviamente p-1.

Se invece /*g^k \ne 1 \pmod p*/, allora la somma è in verità una somma geometrica, che fa
/*\frac{g^{(p-1)k}-1}{g^k-1} \pmod p*/. Ma sappiamo che /*g^{p-1} = 1*/, quindi la somma è 0. []

EDIT: Uff... ce l'ho fatta a rendere invisibile il messaggio...

Esattamente la dimostrazione che avevo in mente io

Quanto la fate complicata...

1) $ \forall $ $ i $ abbiamo che $ i^k \equiv 1 \pmod{p} $ (cioè $ p-1|k $) e quindi:

$ \displaystyle \sum_{i=1}^p i^k \equiv p-1 \pmod{p} $

2) abbiamo per un $ a $ che $ a^k \neq 1 \pmod{p} $. Allora moltiplichiamo il tutto per $ a^k $. Avremo che $ \{1,2,3,...,p-1 \} = \{a,2a,3a,4a,...,a(p-1) \} $ come classi di conguenza e si vede facilmente per assurdo. Quindi avremo:

$ \displaystyle \sum_{i=1}^p i^k \equiv \sum_{i=1}^p (ai)^k \pmod{p} $
$ \displaystyle (1-a^k)\sum_{i=1}^p i^k \equiv 0 \pmod{p} $

quindi, essendo $ p \nmid a^k-1 $ avremo:

$ \displaystyle \sum_{i=1}^p i^k \equiv 0 \pmod{p} $