中文描述看不惯啊，改成符号可以吗

对k归纳可证

等下吃完饭用电脑给你答案

只用注意到，由Fermat小定理，任意与p互素的整数a，有a^{(p-1)p^{k-1}}=1(mod p^k)。那么可以选取n＝b+t(p-1)p^{k-1},这里b满足b^b-M=0(mod p^{k-1}).所以，n^n=(b+t(p-1)p^{k-1})^b * (b+t(p-1)p^{k-1})^{t(p-1)p^{k-1}}=(b+t(p-1)p^{k-1})^b(mod p^k). 二项式展开得到 b^b+t(p-1)p^{k-1}b^{b}+...,当k>＝2时，...中每一项都被p^k整除。
所以只用选取t使得b^b+t(p-1)p^{k-1}b^b＝M（mod p^k）,可以假设b^b-M=cp^{k-1},所以b^b+t(p-1)p^{k-1}b^b=(1+t(p-1)p^{k-1})(cp^{k-1}+M) = M+(t(p-1)+c)p^{k-1}(mod p^k),解出t就可以了。这个就是归纳的步骤，k＝1的时候是比较好做的。

楼上强悍。。