Representing a number as $a^2+db^2$ given $d$

Question

Given integers $n$ and $d$, how can I find integers $a$ and $b$ (or show that they do not exist) such that $n=a^2+db^2$?

If it helps, in my present application I know the factorizations of $n$ and $d$, and the latter is squarefree.

Answer 1

here is a simplified version of Hardy-Muskat-Williams. Find all solutions with $0 \leq b < 4n$ to $$ b^2 \equiv -4d \pmod {4n}. $$ Let's see, this just makes $b$ even. If there is any odd prime factor $q$ of $n$ with odd exponent and $(-d|q) = -1,$ there will be no such solutions $b$ and the thing is impossible.

For each, we have $$ b^2 = -4d + 4nt, $$ $$ b^2 - 4nt = -4d. $$ That is, $$ \langle n,b,t \rangle $$ or $$ n x^2 + bxy + t y^2 $$ is a quadratic form with the proper discriminant, If $\gcd(n,b,t) = 1,$ we find the Gauss reduction of the form. If the reduced form is $ \langle 1,0,d \rangle, $ we have found a representation, gotten by finding the inverse of the two by two matrix that accomplished the Gauss reduction.