1
$\begingroup$

I was solving this question http://www.spoj.com/problems/HS08PAUL/, which asks number of integers in range $[1,n]$ which are expressible in form $x^2+y^4$, $x$ and $y$ being integers.

A simple implementive solution passes (loop $x$ for $1\leq x\leq\sqrt{n}$ and then $y$ till $x^2+y^4\leq n$, but I was wondering if there is some mathematical theorem governing such numbers.

More specifically: given an integer $n$, do there exist integers $x$ and $y$ such that $x^2+y^4=n$?

  • 1
    Looking modulo $16$ $x^2$ is either $0,1,4,9$ and $y^4$ is either $0,1$ so $x^2 + y^4$ is either $0,1,2,4,5,9,10$ modulo $16$ which might be helpful.2012-12-14

2 Answers 2

3

Every perfect square is $0$ or $1$ modulo $4$. So $x^2+y^4\equiv0,1,2$ mod $4$ and this implies if $n\equiv3$ mod $4$ then there is no soloution.

2

Since $x^2+y^4=x^2+(y^2)^2$, Fermat's Theorem on sums of two squares could be used with two caveats:

  1. It applies only to odd $n$.
  2. It would give only a necessary condition.

Moreover, since to apply it you have to factor $n$, it is probably a worse computational method.