Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

It is easy to show that the following problems are equivalent.

a. When is $Pn^2-2an+\frac{a^2-k}{P}$ , with $P$ Prime, $k=a^2 mod P$, and $n$ any integer, a square?


b. When is $X^2-PY^2=k$ solvable in integers?

So, any suggestions on problem a ? How fast would an algorithm used to compute this run ?

share|cite|improve this question
I don't follow. Problems like Problem a are solved precisely by rewriting them as Pell's equations whenever possible. –  Qiaochu Yuan Jan 31 '10 at 19:28
See the Wikipedia article on Pell's equation. There is even some discussion of runtime for classical and quantum computers. –  S. Carnahan Jan 31 '10 at 19:41
I think the questioner is asking which numbers are norms in $Z[\sqrt P]$ which is different from Pell's equation. E.g., if you ask when you can solve this for primes $k$, then the question is which rational prime ideals split or ramify into principal ideals in $\mathbb Q(\sqrt p)$. Pell's equation asks how to find the units. –  Douglas Zare Jan 31 '10 at 22:06

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.