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 $
Somme di potenze k-esime e numeri primi
Somme di potenze k-esime e numeri primi
"Ma devo prendere una n-upla qualsiasi o una n-upla arbitraria?" (Lui)
-
ubermensch
- Messaggi: 49
- Iscritto il: 17 ott 2005, 21:53
Claim azzeccato, ora la dimostrazione
EDIT: Avevo letto male, era tardi, il claim azzeccato è quello di darkcrystal
EDIT: Avevo letto male, era tardi, il claim azzeccato è quello di darkcrystal
Ultima modifica di Boll il 05 giu 2006, 14:47, modificato 1 volta in totale.
"Ma devo prendere una n-upla qualsiasi o una n-upla arbitraria?" (Lui)
-
darkcrystal
- Messaggi: 706
- Iscritto il: 14 set 2005, 11:39
- Località: Chiavari
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!
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!
"Solo due cose sono infinite: l'universo e la stupidità dell'uomo, e non sono tanto sicuro della prima" - Einstein
Membro dell'EATO
Membro dell'EATO
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...
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...
Ultima modifica di Marco il 06 giu 2006, 15:27, modificato 2 volte in totale.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
-
Simo_the_wolf
- Moderatore
- Messaggi: 1053
- Iscritto il: 01 gen 1970, 01:00
- Località: Pescara
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} $
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} $