[proofplan] For part (i) we use that $\mathbb{Z}/p\mathbb{Z}$ is a [field](/page/Field), so the quadratic $X^2 - d$ factors into at most two distinct linear factors; and if $x_0$ is one root then $-x_0$ is another and is distinct (because $p$ is odd and $x_0 \not\equiv 0$). For part (ii) we translate the congruence modulo $N$ into a pair of congruences modulo $p$ and $q$ via the [Chinese Remainder Theorem](/theorems/???); part (i) gives two sign choices in each factor, and the CRT isomorphism glues each of the four $(\pm, \pm)$ combinations to a unique residue modulo $N$. [/proofplan] [step:Record that $\mathbb{Z}/p\mathbb{Z}$ is a field and factor $X^2 - d$] For part (i), $\mathbb{Z}/p\mathbb{Z}$ is a field because $p$ is prime. Over any field, a polynomial of degree $2$ has at most $2$ roots. Thus the congruence $x^2 \equiv d \pmod p$, equivalently the polynomial equation $X^2 - d = 0$ in the field $\mathbb{F}_p$, has at most $2$ solutions modulo $p$. [guided] Why does degree bound the number of roots? In any [integral domain](/page/Integral%20Domain) — and in particular in a field — a non-zero polynomial $f(X)$ of degree $n$ has at most $n$ roots. The proof is by induction: if $r$ is a root, $f(X) = (X - r)g(X)$ with $\deg g = n - 1$, and any other root must be a root of $g$. The quadratic $X^2 - d$ has degree $2$, and in the field $\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}$ it has at most $2$ roots. So the congruence $x^2 \equiv d \pmod p$ has $0$, $1$, or $2$ solutions. We will rule out the case of exactly one solution next. [/guided] [/step] [step:Show that a single solution forces a pair of solutions $\pm x_0$] Suppose the congruence has at least one solution $x_0 \in \mathbb{Z}$ with $x_0^2 \equiv d \pmod p$. Since $\gcd(d, p) = 1$, we have $x_0 \not\equiv 0 \pmod p$ (otherwise $d \equiv x_0^2 \equiv 0$, contradicting coprimality). Then $(-x_0)^2 = x_0^2 \equiv d \pmod p$, so $-x_0$ is also a solution. The two solutions $x_0$ and $-x_0$ are distinct modulo $p$ precisely when $2x_0 \not\equiv 0 \pmod p$; since $p$ is odd, $\gcd(2, p) = 1$, and since $x_0 \not\equiv 0$, we have $2x_0 \not\equiv 0 \pmod p$. Hence $x_0 \not\equiv -x_0 \pmod p$, giving two distinct solutions. [guided] The map $x \mapsto -x$ is an involution on the solution set, and its only fixed points are the residues $x$ with $2x \equiv 0 \pmod p$. When $p$ is odd, the only such residue is $x \equiv 0$, which cannot be a solution because $\gcd(d, p) = 1$ forces $x_0 \not\equiv 0$. Thus the involution has no fixed point on the solution set, and solutions come in pairs $\{x_0, -x_0\}$. [/guided] [/step] [step:Show that any solution coincides with $\pm x_0$] Still in part (i), suppose $y \in \mathbb{Z}$ is any solution, $y^2 \equiv d \pmod p$. Then \begin{align*} 0 \equiv y^2 - x_0^2 = (y - x_0)(y + x_0) \pmod p. \end{align*} Since $p$ is prime, $\mathbb{Z}/p\mathbb{Z}$ has no zero divisors, so $p \mid y - x_0$ or $p \mid y + x_0$, i.e. $y \equiv x_0 \pmod p$ or $y \equiv -x_0 \pmod p$. Combined with the previous step this shows the solution set is exactly $\{x_0, -x_0\} \pmod p$, which has cardinality $2$. This proves part (i). [guided] The factorisation $y^2 - x_0^2 = (y - x_0)(y + x_0)$ is the decisive algebraic move. It reduces a quadratic condition on $y$ to a pair of linear conditions. The primality of $p$ enters exactly here: a product vanishes in $\mathbb{Z}/p\mathbb{Z}$ if and only if at least one factor vanishes, precisely because $\mathbb{Z}/p\mathbb{Z}$ is an [integral domain](/page/Integral%20Domain). If $p$ were composite, this step would fail: for instance modulo $8$ the equation $x^2 \equiv 1$ has four solutions $\{1, 3, 5, 7\}$ rather than two, because $8$ is not prime. [/guided] [/step] [step:Translate the mod-$N$ congruence via the Chinese Remainder Theorem] For part (ii), $p$ and $q$ are coprime (they are distinct primes), so the Chinese Remainder Theorem provides the ring isomorphism \begin{align*} \phi: \mathbb{Z}/N\mathbb{Z} &\longrightarrow \mathbb{Z}/p\mathbb{Z} \times \mathbb{Z}/q\mathbb{Z} \\ x \bmod N &\longmapsto (x \bmod p, \, x \bmod q). \end{align*} The congruence $x^2 \equiv d \pmod N$ corresponds under $\phi$ to the pair of congruences \begin{align*} x^2 \equiv d \pmod p \quad \text{and} \quad x^2 \equiv d \pmod q. \end{align*} Moreover $\gcd(d, p) = 1$ and $\gcd(d, q) = 1$ follow from $\gcd(d, N) = 1$. [guided] The CRT states: for coprime moduli $m_1, m_2$, the ring $\mathbb{Z}/m_1 m_2 \mathbb{Z}$ is isomorphic (via the natural reduction map) to $\mathbb{Z}/m_1 \mathbb{Z} \times \mathbb{Z}/m_2 \mathbb{Z}$. We verify the hypothesis: $p \ne q$ are distinct primes, hence coprime. Under the isomorphism $\phi$, $x^2 \equiv d \pmod N$ is equivalent to the simultaneous conditions $x^2 \equiv d \pmod p$ and $x^2 \equiv d \pmod q$, because ring operations (squaring, equality) transport through $\phi$. The coprimality hypotheses for part (i) are also verified: if $\gcd(d, N) = 1$ then no prime factor of $N$ divides $d$, so in particular $\gcd(d, p) = 1$ and $\gcd(d, q) = 1$. [/guided] [/step] [step:Count the solutions as products of per-prime solution sets] If $x^2 \equiv d \pmod N$ has no solution, then by the CRT isomorphism of the previous step at least one of the congruences modulo $p$ or modulo $q$ has no solution, and the count is $0$. Suppose instead there is at least one solution $x_0$. Reducing modulo $p$ gives a solution of $x^2 \equiv d \pmod p$; by part (i) this congruence has exactly two solutions, $\pm x_0 \pmod p$. Similarly the congruence modulo $q$ has exactly two solutions, $\pm x_0 \pmod q$. By the CRT bijection $\phi$, each choice of sign modulo $p$ and independently modulo $q$ corresponds to a unique residue class modulo $N$. There are $2 \times 2 = 4$ sign combinations, and $\phi$ being a bijection guarantees they yield four distinct residues modulo $N$. Each of these four residues satisfies $x^2 \equiv d$ modulo both $p$ and $q$, hence modulo $N$. Part (i) applied to each prime separately shows there are no additional solutions modulo $p$ or modulo $q$, and hence none modulo $N$. Therefore the number of solutions modulo $N$ is either $0$ or $4$, proving part (ii). [guided] The product structure from the CRT converts the counting problem into a product of per-prime counts. Schematically: \begin{align*} \#\{x \bmod N : x^2 \equiv d\} = \#\{x \bmod p : x^2 \equiv d\} \cdot \#\{x \bmod q : x^2 \equiv d\}. \end{align*} By part (i) each factor on the right is $0$ or $2$. The product is $0$ if either factor is $0$, and $2 \cdot 2 = 4$ if both factors are $2$. This gives the dichotomy $0$ or $4$. Concretely, the four solutions correspond to the four sign combinations: for $\varepsilon_p, \varepsilon_q \in \{+1, -1\}$, let $x_{\varepsilon_p, \varepsilon_q}$ be the unique residue modulo $N$ with \begin{align*} x_{\varepsilon_p, \varepsilon_q} \equiv \varepsilon_p x_0 \pmod p, \qquad x_{\varepsilon_p, \varepsilon_q} \equiv \varepsilon_q x_0 \pmod q. \end{align*} Existence and uniqueness of $x_{\varepsilon_p, \varepsilon_q}$ modulo $N$ is the content of the CRT bijection. The four residues are pairwise distinct modulo $N$ because distinct sign pairs give distinct images in $\mathbb{Z}/p\mathbb{Z} \times \mathbb{Z}/q\mathbb{Z}$, and $\phi$ is injective. Note the crucial asymmetry: in part (i), a solution is its own negative modulo $p$ iff $2x_0 \equiv 0 \pmod p$, which fails for odd $p$ with $x_0 \ne 0$. The same argument in each coordinate of the CRT decomposition confirms that the four sign combinations do not collapse. [/guided] [/step]