Ps. very easy
p|1^k+2^k+...+p^k
p|1^k+2^k+...+p^k
Mostrare che se $ p \in \mathbb{P} $ e $ k>0 $ sono fissati tali che $ p-1 \nmid k $ allora $ p \mid \sum_{i=1}^p{i^k} $.
Ps. very easy
Ps. very easy
The only goal of science is the honor of the human spirit.
Escludiamo dalla sommatoria il $ ~p^k $ finale, che non cambia la congruenza modulo $ ~p $.
Consideriamo un generatore $ ~g $ modulo $ ~p $, dunque $ 1, g, g^2, \ldots, g^{p-2} $ sono tutte le classi di resto modulo $ ~p $, eccetto quella dello 0.
Dato che la sommatoria è la somma delle potenze $ ~k $-esime di tutte le classi di resto modulo $ ~p $ (eccetto quella dello 0), allora
$ $\sum_{i=1}^{p-1}i^k\equiv\sum_{i=0}^{p-2}(g^i)^k\equiv\sum_{i=0}^{p-2}(g^k)^i\equiv\dfrac{(g^k)^{p-1}-1}{g^k-1}\pmod{p} $
Ora per il PTF $ p|(g^k)^{p-1}-1 $, mentre $ p\not|g^k-1 $ perché $ ~g $ è generatore e $ p-1\not|k $, dunque $ ~g^k $ non prende mai la classe dell'1 modulo $ ~p $.
Consideriamo un generatore $ ~g $ modulo $ ~p $, dunque $ 1, g, g^2, \ldots, g^{p-2} $ sono tutte le classi di resto modulo $ ~p $, eccetto quella dello 0.
Dato che la sommatoria è la somma delle potenze $ ~k $-esime di tutte le classi di resto modulo $ ~p $ (eccetto quella dello 0), allora
$ $\sum_{i=1}^{p-1}i^k\equiv\sum_{i=0}^{p-2}(g^i)^k\equiv\sum_{i=0}^{p-2}(g^k)^i\equiv\dfrac{(g^k)^{p-1}-1}{g^k-1}\pmod{p} $
Ora per il PTF $ p|(g^k)^{p-1}-1 $, mentre $ p\not|g^k-1 $ perché $ ~g $ è generatore e $ p-1\not|k $, dunque $ ~g^k $ non prende mai la classe dell'1 modulo $ ~p $.
Una soluzione che non usa i generatori?
Malus question
Sia $ p\in\mathbb P\land p\ge3 $, $ k\in\mathbb N^+ $ e $ a_1,a_2,\dots,a_{\phi(p^k)} $ un sistema di residui che copre tutte le classi coprime con $ p^k $. Sia infine $ \omega\in\mathbb N $. Dimostrare che
$ \displaystyle \sum_{j=1}^{\phi(p^k)}a_j^\omega\equiv\begin{cases}0\mod{p^k} & \text{se $p-1\nmid\omega$} \\ \phi(p^k)\mod{p^k} & \text{se $p-1\mid\omega$} \end{cases} $
Sia $ p\in\mathbb P\land p\ge3 $, $ k\in\mathbb N^+ $ e $ a_1,a_2,\dots,a_{\phi(p^k)} $ un sistema di residui che copre tutte le classi coprime con $ p^k $. Sia infine $ \omega\in\mathbb N $. Dimostrare che
$ \displaystyle \sum_{j=1}^{\phi(p^k)}a_j^\omega\equiv\begin{cases}0\mod{p^k} & \text{se $p-1\nmid\omega$} \\ \phi(p^k)\mod{p^k} & \text{se $p-1\mid\omega$} \end{cases} $
Ultima modifica di FeddyStra il 24 ago 2009, 15:12, modificato 1 volta in totale.
[quote="julio14"]Ci sono casi in cui "si deduce" si può sostituire con "è un'induzione che saprebbe fare anche un macaco", ma per come hai impostato i conti non mi sembra la tua situazione...[/quote][quote="Tibor Gallai"]Ah, un ultimo consiglio che risolve qualsiasi dubbio: ragiona. Le cose non funzionano perché lo dico io o Cauchy o Dio, ma perché hanno senso.[/quote]To understand recursion, you fist need to understand recursion.
[tex]i \in \| al \| \, \pi \, \zeta(1)[/tex]
[tex]i \in \| al \| \, \pi \, \zeta(1)[/tex]
Se $ p\ne2 $ oppure $ ~p=2 $ e $ k\in\left\{1,2\right\} $, allora $ ~p^k $ ha un generatore e si risolve come prima.
Poniamo dunque $ ~p=2 $ e $ ~k>3 $ (ricordiamo che $ \phi(2^k)=2^{k-1} $).
Le classi coprime con $ ~2^k $ sono rappresentate da tutti i dispari minori di $ ~2^k $, dunque
$ \displaystyle\sum_{J=1}^{\phi(2^k)}a_j^{\omega}\equiv1^{\omega}+3^{\omega}+\ldots+(2^k-3)^{\omega}+(2^k-1)^{\omega}\pmod{2^k} $
Ora se $ ~\omega $ è dispari, per motivi di simmetria (dovuta al fatto che $ \phi(2^k) $ è pari e vale $ ~2^{k-1} $) la somma si annulla modulo $ ~2^k $.
[Pensavo di averlo fatto giusto, adesso aggiusto il caso in cui omega è pari]
Poniamo dunque $ ~p=2 $ e $ ~k>3 $ (ricordiamo che $ \phi(2^k)=2^{k-1} $).
Le classi coprime con $ ~2^k $ sono rappresentate da tutti i dispari minori di $ ~2^k $, dunque
$ \displaystyle\sum_{J=1}^{\phi(2^k)}a_j^{\omega}\equiv1^{\omega}+3^{\omega}+\ldots+(2^k-3)^{\omega}+(2^k-1)^{\omega}\pmod{2^k} $
Ora se $ ~\omega $ è dispari, per motivi di simmetria (dovuta al fatto che $ \phi(2^k) $ è pari e vale $ ~2^{k-1} $) la somma si annulla modulo $ ~2^k $.
[Pensavo di averlo fatto giusto, adesso aggiusto il caso in cui omega è pari]
