[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*}[/step]

[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: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*}[/step]

[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: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.[/step]

[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]