Criterio di Eulero: differenze tra le versioni

 

==Dimostrazione del criterio di Eulero==

 

Viceversa, assumiamo che ''a''^{(''p'' − 1)/2} ≡ 1 (mod ''p''). Sia α un elemento primitivo modulo ''p'', in modo che possiamo dire ''a'' = α^''i''. Allora, α^{''i''(''p'' − 1)/2} ≡ 1 (mod ''p''). Per il piccolo teorema di Fermat, (''p'' − 1) divide ''i''(''p'' − 1)/2, perciò ''i'' deve essere pari. Sia ''k'' ≡ α^''i''/2 (mod ''p''). Abbiamo infine ''k''² = α^''i'' ≡ ''a'' (mod ''p'').