$p=2$ için $T(x)=x$ polinomu verilen denkliği sağlar. Bu durumda $p=2$ ise $\max{\deg(T)} = 1 = p-1$.
$p>2$ asal sayısı için $T(x) = x^{p-2}$ polinomunu ele alalım.
$m,n \not \equiv 0 \pmod p$ ve $T(n) \equiv T(m) \equiv n^{p-2} \equiv m^{p-2} \pmod p$ olsun.
Her iki tarafı $mn$ ile çarpalım. $$mn^{p-1} \equiv nm^{p-1} \pmod p$$ ve Fermat'ın Küçük Teoreminden $$n^{p-1} \equiv m^{p-1} \equiv 1 \pmod p$$ olacağı için $$n\equiv m \pmod p$$ elde edilir.
Yani her $p>2$ asal sayısı için derecesi $p-2$ olan ve sorudaki gerektirmeyi sağlayan bir $T(x)$ polinomu bulunabiliyor. Geriye kontrol edilmesi gereken tek bir sayı kalıyor: $p-1$.
$T(x) = a_{p-1}x^{p-1} + \dots + a_0$ polinomu verilen şartı sağlasın. $i\not \equiv j$ olduğunda $T(i) \equiv T(j)$ olamaz. Bu durumda tüm $T(i)$ sayıları farklıdır. Yani $T(x)$ birebir ve örtendir.
$\sum\limits_{i=0}^{p-1}T(i)$ toplamını iki yoldan sayalım.
Birincisi birebir ve örtenlikten $\sum\limits_{i=0}^{p-1}T(i) \equiv \sum\limits_{i=0}^{p-1}i \equiv \dfrac {(p-1)p}{2}$ elde ederiz. $p$ asal sayısı tek olduğu için sonuç olarak $\sum\limits_{i=0}^{p-1}T(i) \equiv \dfrac {p-1}{2}\cdot p \equiv 0 \pmod p$ elde ederiz.
Diğer yoldan saydığımızda da $T(i)$ lerin toplamının $p$ ye bölünmesi gerekecek.
$T(0) = a_0$
$T(1) = a_{p-1}\cdot 1^{p-1} + \dots + a_0$
$\vdots$
$T(p-1) = a_{p-1}\cdot (p-1)^{p-1} + \dots + a_0$
polinomlarını alt alta toplarsak
$\begin{array}{rcl}\sum\limits_{i=0}^{p-1}T(i) &=& a_{p-1}\left(1^{p-1} + \dots + (p-1)^{p-1}\right) \\ && + a_{p-2}\left(1^{p-2} + \dots + (p-1)^{p-2}\right) \\ && + \dots + a_1\left(1+2+\dots + (p-1)\right) + p\cdot a_0
\end{array}$.
Fermat'ın Küçük teoreminden $a_{p-1}$ in parantezinde olan tüm sayılar $1$ e denk olacağı için
$\sum\limits_{i=0}^{p-1}T(i) = \underbrace{a_{p-1}(p-1)}_{\not \equiv 0 \pmod p} + a_{p-2}\left(1^{p-2} + \dots + (p-1)^{p-2}\right) + \dots + \underbrace{a_1\left(1+2+\dots + (p-1)\right)}_{\equiv 0 \pmod p} + \underbrace{p\cdot a_0}_{\equiv 0 \pmod p}$ elde ederiz.
İddia:$0<a<p-1$ için $\sum\limits_{i=1}^{p-1} i^a \equiv \sum\limits_{i=1}^{p-1} i^1 \equiv 0 \pmod p$.
İspat:Her $p$ asal sayısı için bir $g$ ilkel kökü vardır. (Bunun ispatı için internete bakınız.)
İlkel kök tanımı gereği $j=1,\dots, p-1$ için $g^j$ sayıları $\{1,2,\dots, p-1\}$ kümesini örter. Bu durumda herhangi bir $i=1,2,\dots, p-1$ sayısı için buna denk $g^j$ sayısı bulabiliriz.
$$\sum\limits_{i=1}^{p-1} i^a \equiv \sum\limits_{j=1}^{p-1} (g^j)^a \equiv \sum\limits_{j=1}^{p-1} (g^a)^j \equiv \underbrace{g^a + g^{2a} + \dots + g^{(p-1)a}}_{\text{Geometrik Seri}} \equiv \dfrac {g^{pa} - g^a}{g^a - 1} \pmod p$$
$a \neq p - 1$ olduğu için $g^a \not \equiv 1 \pmod p$ ve Fermat'ın Küçük Teoremince $g^{pa} \equiv (g^a)^p \equiv g^a$ olacağı için $\dfrac {g^{pa} - g^a}{g^a - 1}$ sayısı $p$ ile bölünür. $\blacksquare$
Soruya geri dönersek,
$\sum\limits_{i=0}^{p-1}T(i) = \underbrace{a_{p-1}(p-1)}_{\not \equiv 0 \pmod p} + \underbrace{a_{p-2}\left(1^{p-2} + \dots + (p-1)^{p-2}\right)}_{\equiv 0 \pmod p} + \dots + \underbrace{a_1\left(1+2+\dots + (p-1)\right)}_{\equiv 0 \pmod p} + \underbrace{p\cdot a_0}_{\equiv 0 \pmod p} \not \equiv 0 \pmod p$.
Bu durumda diğer yoldan saydığımızın tersi bir durumla karşılaştık. Yani çelişki elde ettik.
Sonuç olarak, $\max \deg(T) = \max (1, p-2)$ elde etmiş olduk.
