[proofplan] The [Legendre symbol](/page/Legendre%20Symbol) modulo $p$ is defined by the residue class of the numerator modulo $p$: it is $0$ on the zero class, $1$ on nonzero square classes, and $-1$ on nonzero nonsquare classes. Since $a \equiv b \pmod p$, the integers $a$ and $b$ represent the same class in $\mathbb{Z}/p\mathbb{Z}$. Therefore they fall into the same one of the three defining cases, so their Legendre symbols are equal. [/proofplan] [step:Pass from congruent integers to the same residue class] Let $\bar{a}$ and $\bar{b}$ denote the residue classes of $a$ and $b$ in the [quotient ring](/page/Quotient%20Ring) $\mathbb{Z}/p\mathbb{Z}$. The congruence $a \equiv b \pmod p$ means precisely that $p \mid (a-b)$, hence \begin{align*} \bar{a}=\bar{b} \end{align*} in $\mathbb{Z}/p\mathbb{Z}$. [guided] We first translate the congruence into the language in which the Legendre symbol is defined. Let $\bar{a}$ and $\bar{b}$ be the residue classes of $a$ and $b$ in $\mathbb{Z}/p\mathbb{Z}$. By definition of congruence modulo $p$, the assumption $a \equiv b \pmod p$ means that $p$ divides $a-b$. This is exactly the [equivalence relation](/page/Equivalence%20Relation) used to form the quotient ring $\mathbb{Z}/p\mathbb{Z}$, so $a$ and $b$ determine the same residue class: \begin{align*} \bar{a}=\bar{b}. \end{align*} The rest of the proof uses only this equality of residue classes. [/guided] [/step] [step:Check that the zero case agrees for $a$ and $b$] By the previous step, $\bar{a}=\bar{b}$. Therefore \begin{align*} \bar{a}=0 \iff \bar{b}=0. \end{align*} Equivalently, \begin{align*} p \mid a \iff p \mid b. \end{align*} Thus the Legendre symbol takes the value $0$ on $a$ if and only if it takes the value $0$ on $b$. [/step] [step:Check that the nonzero square case agrees for $a$ and $b$] Assume now that $\bar{a}\neq 0$, equivalently $\bar{b}\neq 0$. By definition, $a$ is a [quadratic residue](/page/Quadratic%20Residue) modulo $p$ if and only if there exists an integer $x \in \mathbb{Z}$ such that \begin{align*} x^2 \equiv a \pmod p. \end{align*} Since $a \equiv b \pmod p$, this condition is equivalent to \begin{align*} x^2 \equiv b \pmod p. \end{align*} Hence $a$ is a nonzero quadratic residue modulo $p$ if and only if $b$ is a nonzero quadratic residue modulo $p$. [/step] [step:Apply the defining cases of the Legendre symbol] The definition of the Legendre symbol for an odd prime $p$ is: \begin{align*} \left(\frac{n}{p}\right)=0 \end{align*} when $p \mid n$, \begin{align*} \left(\frac{n}{p}\right)=1 \end{align*} when $p \nmid n$ and $n$ is a quadratic residue modulo $p$, and \begin{align*} \left(\frac{n}{p}\right)=-1 \end{align*} when $p \nmid n$ and $n$ is not a quadratic residue modulo $p$. The preceding steps show that $a$ and $b$ satisfy the same one of these three mutually exclusive cases. Therefore \begin{align*} \left(\frac{a}{p}\right)=\left(\frac{b}{p}\right). \end{align*} This proves the claimed periodicity modulo $p$. [/step]