0

I found this exercise in an old number theory book:

Let $f(x)$ be a polynomial with integer coefficients and $p$ a prime number. Show that for all integers $a$ holds $$a^{f(p)} ≡ a^{f(1)} \pmod{p}.$$

So for example let $$ f(x)=x^2+x+1 $$ and $a=5, p=7$, then $$ 5^{7^2+7+1}\equiv 5^{3} \pmod{7} $$

Now my goal is to prove this theorem. I can see that for a polynomial $$ g(x)=a_0+a_1x+a_2x^2+... $$ we have $$ g(p)=a_0+a_1p+a_2p^2+... \equiv a_0+a_1+a_2+... \pmod{p} $$ and this is always the same as just plugging in $1$. But why is $a^x\equiv a^y \pmod{p}$ just because $x\equiv y \pmod{p}$? Maybe I am on the wrong track on this? Any hints?

Bill Dubuque
  • 265,059
  • 37
  • 279
  • 908
calculatormathematical
  • 1,732
  • 1
  • 6
  • 21
  • Do you know Fermat's theorem? – Phicar Jul 19 '22 at 19:57
  • By little Fermat & [mod order reduction](https://math.stackexchange.com/a/2033681/242) $\bmod p\!:\ a^{\color{#c00}{\large p-1}}\equiv 1\Rightarrow a^{\large f(p)}\equiv a^{\large f(1)},\,$ since $\,f(p)\equiv f(1)\pmod{\color{#c00}{\!p\!-\!1}},\,$ by the [Polynomial Congruence Rule](https://math.stackexchange.com/a/879262/242) $ $ (exceptional case $a\equiv 0\pmod{p}$ is trivial). – Bill Dubuque Jul 19 '22 at 20:09

0 Answers0