'Het mooiste getaltheorieprobleem op de IMO' - AOPS

We kiezen $q$ zó dat het aan volgende voorwaarden voldoet:

(i) $q \mid p^p-1$

(ii) $p \mid q-1$

(iii) $p^2 \not \mid q-1$.

Eerst bewijzen we natuurlijk dat zo'n priemgetal $q$ bestaat.

Zij $a=\frac{p^p-1}{p-1}=\sum_{i=0}^{p-1}p^i$.
Dan geldt dat $a \equiv 1 \pmod {p-1}$ en dus $ggd(p-1,a)=1$ alsook $a \equiv p+1 \pmod{ p^2}$. Bijgevolg heeft $a$ een priemdeler die niet congruent is met één modulo $p^2$. Zij $q$ die priemdeler. Dan zal $p^p \equiv 1 \pmod q$ en aangezien $p$ priem is en $q \not \mid p-1$, moet $p$ de orde van $p$ zijn modulo $q$ en dus $p \mid \phi(q)=q-1$. Dus $q$ voldoet aan alle voorwaarden.

Stel nu $q=pk+1$ (mag wegens (ii)). Stel dat er een $n$ is zodat $q \mid n^p-p$. Omdat $ggd(q,p)=1$, moet dan ook $ggd(n,q)=1$. Dus $n^p \equiv p \pmod q \Rightarrow p^k \equiv n^{pk}=n^{q-1} \equiv 1 \pmod q$. Maar wegens (ii) is ook $p^p \equiv 1 \pmod q$, dus moet $p^{ggd(p,k)} \equiv 1 \pmod q$. Maar $ggd(p,k)=1$ wegens (iii), dus $p \equiv 1 \pmod q$, contradictie aangezien $p \mid q-1$. Dus zo'n $n$ bestaat niet. Q.E.D.