一方で f(n)=n^3-3n+1 についての逆問題は厳しいきがします
つまり pをp≡±1 (mod 9)なる素数とするとき
f(n)≡0(mod p) を満たす整数nが必ず存在することの証明

p≡1 (mod 9) のときの存在を示すのは問題ない :
gをmod pの原始根とし a=g^((p-1)/9), aのmod pの逆元をbとする
このとき n = a+b とすれば f(n)≡0 (mod p)が確認できる
実際 b^3*f(a+b) ≡ a^6+a^3+1 ≡ 0 (mod p) となる

問題は p≡ -1(mod 9) のときで このあたりが初等的方法の限界でしょう
(このケースで完全な初等的な解法はあるのだろうか？)
無理やり"初等的"にやろうとすると 例えば F_pの2次拡大を具体的に記述するとか？
しかし代数的構造をある程度調べざるを得なくなるので相当苦しいでしょう
(とくに有限体論では当たり前である生成元の存在,つまり単数群の巡回的構造)
そもそも ただの翻訳になってしまったら それは初歩的な解法といえないだろうし
それなら有限体論の基礎を学んだほうがマシでしょうね

しかしながら もしかしたらあるのかもしれないですね
(F_pの2次拡大を翻訳しなおす方法は無しとしても)

以上