# show that there exist infinitely many positive integers $k$ such $p^n|k^k-a$

Given a prime number $p$, and postive integers $n,a$,where $(a,p)=1$. show that: there exsit infinitely many positive integers $k$ such that $$p^n|k^k-a$$

It seem can use Fermat's little theorem $k^{p}\equiv k\pmod p$

## 1 Answer

Firstly, we only need to find one $k$ such that $$k^k \equiv a \pmod{p^n}$$ because if $k$ satisfies this equality, then so does $k+p^n \varphi(p^n)$.

Our approach is: we first find a $k_1$ such that $$\tag{1}{k_1}^{k_1} \equiv a \pmod{p}$$ then we use Hensel's lemma to lift this $k_1$ to $k_2$ such that $$\tag{2}{k_2}^{k_2} \equiv a \pmod{p^2}$$ continue this lifting will give you an $k_n$ such that $${k_n}^{k_n} \equiv a \pmod{p^n}$$

Since $(p,p-1)=1$, so we can find $r,s$ such that $a+rp = 1+s(p-1)$. Then it is easy to verify that $$(a+rp)^{a+rp} \equiv a \pmod{p}$$ this established $(1)$.

Consider the polynomial $f_1(x)=x^{k_1}-a$, then $f_1'(k_1)={k_1}^{k_1}$, which is not divisible by $p$. Hensel's lemma gives an integer $u_1$ such that $$(k_1+u_1p)^{k_1} \equiv a \pmod{p^2}$$ Since $(p,p-1) = 1$, there exists integers $v_1,w_1$ such that $u_1 + v_1 p = (p-1)w_1$, then it is easy to verify that $$(k_1+u_1p+v_1p^2)^{k_1+u_1p+v_1p^2} \equiv (k_1+u_1p)^{k_1} \equiv a \pmod{p^2}$$ This established $(2)$.

To lift it to $p^3$, consider the polynomial $f_2(x)=x^{k_2}-a$, then $f_2'(k_2)={k_2}^{k_2}$, which is not divisible by $p$. Hensel's lemma says there exists $u_2$ such that $$(k_2+u_2p^2)^{k_2} \equiv a \pmod{p^3}$$ Since $(p,p-1) = 1$, there exists integers $v_2,w_2$ such that $u_2 + v_2 p = (p-1)w_2$, then it is easy to verify that $$(k_2+u_2p^2+v_1p^3)^{k_2+u_2p^2+v_1p^3} \equiv (k_2+u_2p^2)^{k_2} \equiv a \pmod{p^3}$$

I think you will have no difficulty to generalize this process to $p^n$.