Eğer $(n,q)=d>1$ ise $d\mid (n+1)^p-n^p$ olduğundan $d\mid (n+1)^p$ olur fakat bu $(n+1,n)=1$ olmasıyla çelişir. Dolayısıyla $(n,q)=1$ olmalıdır. $q=1$ için sorudaki önerme barizdir. $q>1$ için $q=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$ yazalım. $n$'nin $p_i$ modunda tersi vardır. $$(n+1)^p\equiv n^p\pmod{p_i}\implies (1+n^{-1})^p\equiv 1\pmod{p_i}$$ $a=1+n^{-1}$ sayısının $p_i$ modundaki mertebesi $m$ olsun, iddia gereği $1+n^{-1}$ sayısının bir kuvveti $1$'e denk olduğundan mertebesi de olmalıdır. $p.$ kuvvet de $1$ kalanı verdiğinden $m\mid p$ olmalıdır, yani $m=1,p$ olabilir. Eğer $m=1$ ise $$1+n^{-1}\equiv 1\pmod{p_i}\implies n^{-1}\equiv 0\pmod{p_i}$$ çelişkisi elde edilir. Dolayısıyla $m=p$ olacaktır. Aynı zamanda küçük Fermat teoreminden $$(1+n^{-1})^{p_i-1}\equiv 1\pmod{p_i}$$ olduğundan $m=p\mid p_i-1$ olmalıdır. Yani her $i=1,2,\dots, k$ için $$p_i\equiv 1\pmod{p}\implies p_i^{a_i}\equiv 1\pmod{p}$$ olacaktır. Tüm $i$'ler için çarparsak $$q=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}\equiv 1\pmod{p}\implies p\mid q-1$$ bulunur.
