Sia p un primo.
Dimostrare che esiste un primo q tale che $ \forall n\in\mathbb{Z}:\; q\nmid n^p-p $
Good luck.
(questo prometto cha ha una soluzione carina ed elementare)
q|n^p-p, ma anche no.
q|n^p-p, ma anche no.
"Sei la Barbara della situazione!" (Tap)
Stamattina mi son svegliato alle 11:30... è che non solo ci ho pensato un bel po' la sera, ma per addormentarmi mi sono anche letto fin tardi un libro di Terzani sulla guerra del Vietnam... peraltro di sera non ho concluso niente su sto problema, il pomeriggio porta consiglio 
Comunque le idee che han portato alla soluzione erano queste:
- se p non divide q-1, allora la funzione x^p è iniettiva modulo q. Infatti, se p non divide q-1, esistono interi j,k tali che kp - j(q-1) = 1, e allora:
$ ~ a^p \equiv b^p \Rightarrow (a^p)^k \equiv (b^p)^k \Rightarrow a(a^{q-1})^j \equiv b(b^{q-1})^j \Rightarrow a \equiv b $
Essendo iniettiva su in insieme finito, è anche suriettiva e trovo un n tale che $ ~ n^p \equiv p \pmod q $.
Quindi, trovare un q con quelle proprietà implica trovare un q congruo a 1 modulo p.
Ora, come lo trovo un q congruo a 1 modulo p? L'unico modo che io conosco è cercare un divisore primo di $ ~ \frac{a^p-1}{a-1} $ per qualche a. In questo modo, a sarà un elemento di ordine p (modulo q), e quindi p | q-1.
Però non è detto che un q scelto in questo modo, con un a casuale, funzioni,anzi, se ho sfiga, non funzionerà.
Quindi a non è un a a caso, proviamo a buttarci dentro un numero particolare, che so, magari a=p?
Beh, se ci butto a=p, avrò che p ha ordine p modulo q. Se però p è anche una potenza p-esima modulo q? In tal caso, esisterà un elemento di ordine $ ~ p^2 $ modulo q, e quindi $ ~ p^2 \mid q-1 $. Quello che devo sperare è quindi che esista un divisore primo di $ ~ \frac{p^p-1}{p-1} $ che non è congruo a 1 modulo $ ~ p^2 $.
Dopo tutti sti passaggi posso ancora avere una sfiga esagerata, cioè che tutti i suoi fattori primi sono 1 modulo $ ~ p^2 $? No, perchè in tal caso anche lo stesso $ ~ \frac{p^p-1}{p-1} $ sarebbe congruo a 1 modulo $ ~ p^2 $, ma si vede facilmente che è congruo a p+1 modulo $ ~ p^2 $.
Quindi la risposta è: prendiamo un divisore primo q di $ ~ \frac{p^p-1}{p-1} $ che non sia congruo a 1 modulo $ ~ p^2 $. Allora se $ ~ q \mid n^p-p $ allora $ ~ n^p \equiv p \not \equiv 1 \pmod q $ allora $ ~ n^{p^2} \equiv p^p \equiv 1 \pmod p $, quindi l'ordine di n sarebbe $ ~ p^2 $, quindi $ ~ p^2 \mid q-1 $, assurdo.
Comunque le idee che han portato alla soluzione erano queste:
- se p non divide q-1, allora la funzione x^p è iniettiva modulo q. Infatti, se p non divide q-1, esistono interi j,k tali che kp - j(q-1) = 1, e allora:
$ ~ a^p \equiv b^p \Rightarrow (a^p)^k \equiv (b^p)^k \Rightarrow a(a^{q-1})^j \equiv b(b^{q-1})^j \Rightarrow a \equiv b $
Essendo iniettiva su in insieme finito, è anche suriettiva e trovo un n tale che $ ~ n^p \equiv p \pmod q $.
Quindi, trovare un q con quelle proprietà implica trovare un q congruo a 1 modulo p.
Ora, come lo trovo un q congruo a 1 modulo p? L'unico modo che io conosco è cercare un divisore primo di $ ~ \frac{a^p-1}{a-1} $ per qualche a. In questo modo, a sarà un elemento di ordine p (modulo q), e quindi p | q-1.
Però non è detto che un q scelto in questo modo, con un a casuale, funzioni,anzi, se ho sfiga, non funzionerà.
Quindi a non è un a a caso, proviamo a buttarci dentro un numero particolare, che so, magari a=p?
Beh, se ci butto a=p, avrò che p ha ordine p modulo q. Se però p è anche una potenza p-esima modulo q? In tal caso, esisterà un elemento di ordine $ ~ p^2 $ modulo q, e quindi $ ~ p^2 \mid q-1 $. Quello che devo sperare è quindi che esista un divisore primo di $ ~ \frac{p^p-1}{p-1} $ che non è congruo a 1 modulo $ ~ p^2 $.
Dopo tutti sti passaggi posso ancora avere una sfiga esagerata, cioè che tutti i suoi fattori primi sono 1 modulo $ ~ p^2 $? No, perchè in tal caso anche lo stesso $ ~ \frac{p^p-1}{p-1} $ sarebbe congruo a 1 modulo $ ~ p^2 $, ma si vede facilmente che è congruo a p+1 modulo $ ~ p^2 $.
Quindi la risposta è: prendiamo un divisore primo q di $ ~ \frac{p^p-1}{p-1} $ che non sia congruo a 1 modulo $ ~ p^2 $. Allora se $ ~ q \mid n^p-p $ allora $ ~ n^p \equiv p \not \equiv 1 \pmod q $ allora $ ~ n^{p^2} \equiv p^p \equiv 1 \pmod p $, quindi l'ordine di n sarebbe $ ~ p^2 $, quindi $ ~ p^2 \mid q-1 $, assurdo.