Euler's criterion EulersCriterion 2002-02-15 01:33:10 2003-01-24 23:40:53 Theorem %\usepackage{graphicx} %\usepackage{xypic} \usepackage{bbm} \newcommand{\Z}{\mathbbmss{Z}} \newcommand{\C}{\mathbbmss{C}} \newcommand{\R}{\mathbbmss{R}} \newcommand{\Q}{\mathbbmss{Q}} \newcommand{\mathbb}[1]{\mathbbmss{#1}} Let $p$ be an odd prime and $n$ an integer such that $(n,p)=1$ (that is, $n$ and $p$ are relatively prime). Then $(n|p)\equiv n^{(p-1)/2}\pmod{p}$ where $(n|p)$ is the Legendre symbol.