[proofplan]
The hypothesis provides some solution $x_0$ with $x_0^2 \equiv d \pmod{p}$. We apply [Fermat's Little Theorem](/theorems/???) to $x_0$ to obtain $x_0^{p-1} \equiv 1 \pmod p$, then rewrite $p - 1 = 2(2k - 1)$ to transfer the identity to $d$: squaring the relation $d \equiv x_0^2$ gives $d^{2k-1} \equiv x_0^{p-1} \equiv 1$. Multiplying through by $d$ and recognising the left side as $(d^k)^2$ completes the proof.
[/proofplan]
[step:Invoke Fermat's Little Theorem on an existing square root]
By hypothesis there exists $x_0 \in \mathbb{Z}$ with $x_0^2 \equiv d \pmod{p}$. Since $\gcd(d, p) = 1$ and $d \equiv x_0^2 \pmod p$, we have $\gcd(x_0, p) = 1$ (any prime factor $p$ of $x_0$ would divide $x_0^2 \equiv d$, contradicting $\gcd(d,p) = 1$). Fermat's Little Theorem applies to $x_0$: for any integer $a$ with $\gcd(a, p) = 1$,
\begin{align*}
a^{p - 1} \equiv 1 \pmod p.
\end{align*}
Taking $a = x_0$,
\begin{align*}
x_0^{p-1} \equiv 1 \pmod{p}.
\end{align*}
[guided]
We need a solution $x_0$ to work with before we can do any algebra. The statement's hypothesis "$x^2 \equiv d \pmod p$ has a solution" provides such an $x_0$.
Before applying Fermat's Little Theorem, we must verify its hypothesis $\gcd(x_0, p) = 1$. We have $d \equiv x_0^2 \pmod p$ and $\gcd(d, p) = 1$ (given). If $p \mid x_0$, then $p \mid x_0^2 \equiv d$, contradicting coprimality. Hence $\gcd(x_0, p) = 1$, and Fermat's Little Theorem gives $x_0^{p-1} \equiv 1 \pmod p$.
This is the main tool. Notice that the conclusion of Fermat's Little Theorem involves the exponent $p - 1$, which is exactly what our hypothesis $p = 4k - 1$ will make convenient: $p - 1 = 4k - 2 = 2(2k - 1)$ is $2$ times an odd number, so the exponent $p - 1$ "almost" contains a factor of $2k$, differing from it by $1$.
[/guided]
[/step]
[step:Exploit the factorisation $p - 1 = 2(2k - 1)$]
From $p = 4k - 1$ we get
\begin{align*}
p - 1 = 4k - 2 = 2(2k - 1).
\end{align*}
Therefore $x_0^{p-1} = x_0^{2(2k-1)} = (x_0^2)^{2k - 1}$. Since $x_0^2 \equiv d \pmod p$,
\begin{align*}
(x_0^2)^{2k - 1} \equiv d^{2k-1} \pmod p,
\end{align*}
so combining with Fermat's Little Theorem from the previous step,
\begin{align*}
d^{2k - 1} \equiv x_0^{p - 1} \equiv 1 \pmod{p}.
\end{align*}
[guided]
The exponent $p - 1 = 2(2k - 1)$ is the key arithmetic identity. It rewrites $x_0^{p - 1}$ as $(x_0^2)^{2k - 1}$, which is where we can substitute $d$ for $x_0^2$ and transfer the information from $x_0$ to $d$. After substitution,
\begin{align*}
1 \equiv x_0^{p - 1} = (x_0^2)^{2k - 1} \equiv d^{2k - 1} \pmod p.
\end{align*}
We now have a statement purely about $d$, with no reference to the (unknown) solution $x_0$. This is crucial for the conclusion — the claimed square root $d^k$ must be computable from $d$ alone.
[/guided]
[/step]
[step:Multiply by $d$ and recognise $(d^k)^2$]
Multiplying both sides of $d^{2k - 1} \equiv 1 \pmod p$ by $d$ gives
\begin{align*}
d^{2k} \equiv d \pmod p.
\end{align*}
The left-hand side is $d^{2k} = (d^k)^2$. Hence
\begin{align*}
(d^k)^2 \equiv d \pmod{p},
\end{align*}
which shows that $d^k$ is a square root of $d$ modulo $p$. This completes the proof.
[guided]
The identity $d^{2k - 1} \equiv 1 \pmod p$ is almost the statement we want. We want $d^{2k} \equiv d$, which differs by a single factor of $d$. Multiplying both sides by $d$ yields exactly this:
\begin{align*}
d^{2k} = d \cdot d^{2k - 1} \equiv d \cdot 1 = d \pmod p.
\end{align*}
Rewriting $d^{2k} = (d^k)^2$ makes the square structure visible: $(d^k)^2 \equiv d \pmod p$, i.e. $d^k$ is a square root of $d$.
Why is this useful in practice? The exponent $k = (p + 1)/4$ is computable from $p$ alone, so the formula $d^k \bmod p$ gives an efficient algorithm (via fast exponentiation) to extract square roots modulo primes $p \equiv 3 \pmod 4$, without knowing any prior square root. The argument required the hypothesis that a square root exists; if $d$ is a non-residue the same computation yields $(d^k)^2 \equiv -d$ instead, so the formula implicitly supplies a test (square the output and check whether it equals $d$).
[/guided]
[/step]
