As the question titles states, how can I efficiently find whether $d + \frac{n}{d} \equiv 0 \pmod 4$, given that $d$ divides $n$? An example would be with $n = 35$ and $d = 5$.
$5 + \frac{35}{5} = 5+7 = 12 \equiv 0 \pmod 4$, so it "passes". I tried $d + \frac{n}{d} \equiv 0 \pmod 4$, so $\frac{n}{d} \equiv -d \pmod 4$. This means that $n$ must equal $-d^{2}$ (mod 4). Can someone let me know if this is right? If not, what is a good way/are some preconditions of $d$ and $n$ so that $d + \frac{n}{d} \equiv 0 \pmod 4$.
If $n$ is odd, then $d$ is odd. In that case $d+(n/d)\equiv 0$ iff $x^2\equiv -n$ because $d$ is a unit $\bmod 4$. But for odd $d$ we must have $d^2\equiv 1$, so the ordered pair $(n,d)$ passes for odd $n$ iff $n\equiv 3\bmod 4$.
If $n$ is even, then $d$ and $n/d$ must both be even (meaning $n$ is a multiple of $4$). Assuming this parity requirement is met, then either both $d$ and $n/d$ must be twice an odd number so $d+(n/d)\equiv 2+2$, like $n=12, d=2$, or else both $d$ and $n/d$ must be multiples of $4$. Among even values of $n$, all multiples of $16$ will have at least one $d$ meeting this criterion, and all remaining multiples of $4$ that are not multiples of $8$ will also have at least one such $d$.
All told, $7/16$ of all $n$ values ($n\in \{0,3,4,7,11,12,15\}\bmod 16$) will have at least one passing value of $d$.