The post below is jointly by Rainer Dietmann and Christian Elsholtz.
We had worked on the problem since a while and had an independent asymptotic solution
to Euler's problem.
Our argument is possibly easier, but in it's current form
it does does not achieve the correct order of magnitude of the number of solutions. This seems to be a very nice feature of Lucia's approach!
We had intended to make the argument entirely explicit
in order to prove the statement for all $n$, not only for sufficienly large $n$. (See also the comments
after the second argument below).
We also had intended to prepare these results for publication.
Lucia, we would appreciate if you could contact us by email, the email
adresses (RD in Royal Holloway and CE in Graz) are easy to find.
$\textbf{Theorem:}$
Let $n$ be a sufficiently large positive integer with
$n \equiv 2 \pmod 4$. Then $n$ can be written as the sum of two
positive integers, none of them having any prime factor
$p$ with $p \equiv 3 \pmod 4$.
This asymptotically answers a question of Euler.
Important partial results are due to R.D. James (TAMS 43 (1938), 296--302)
who proved the ternary case and an approximation to the binary case. Indeed the ternary case allows for an elementary proof,
based on Gaus' theorem on the sum of three triangular numbers: Any integer $k$
can be written as $k = \frac{x(x-1)}{2}+ \frac{y(y-1)}{2} + \frac{z(z-1)}{2}$ and therefore
$$ 4k + 3 = (x^2 + (x - 1)^2) + (y^2 + (y - 1)^2) + (z^2 + (z - 1)^2).$$
Observe that $ (x^2 + (x - 1)^2)$ is a sum of two adjacent squares, and thus cannot be divisible by any prime $ p = 3 \mod 4$. (Recall here and for later reference the following $\textbf{Fact:}$ if $p|n = s^2 +t^2$, with $p = 3 \mod 4$ prime, then $p|s$ and $p|t$.)
Using a well known result of the late George Greaves, one gets a short
proof of the Theorem.
$\textbf{Proof.}$
By a result of Greaves (Acta Arith 29 (1976), 257--274),
each sufficiently large positive integer $n$ with
$n \equiv 2 \pmod 4$ can be written in the form
$$ n = p^2+q^2+x^2+y^2
$$
for rational primes $p, q$ and integers $x, y$, and the number of such representations is at least of order of magnitude
$n (\log n)^{-5/2}$. We write $a=p^2+x^2$ and $b=q^2+y^2$
and take multiplicities into account:
namely the number of representations $r_2(a)$ of
$a$ as a sum of two squares is $r_2(a) \leq d(a)\ll a^{\varepsilon}\ll n^{\varepsilon}$.
The same holds for $r_2(b)$. We therefore find that there are
at least
$$
n^{1-2\varepsilon}
$$
many tuples $(a, b)$ with positive
integers $a, b$, such that $n=a+b$ and both $a$ and $b$ are the sum
of the square of a prime and the square of an integer.
Now suppose that $w$ is a prime with $w \equiv 3 \pmod 4$ and
$w$ divides $a=p^2+x^2$, say. Then by the `fact' above and
as $p$ is prime this implies that $p=w$ and $x$ is
divisible by $w$. Therefore, at most $O(1+n^{1/2}/w)$ many
$a$ can be divisible by $w$, and for any such $a$ there will be only
one corresponding $b$ since $a+b=n$. The same argument applies if
$w$ divides $b$. Moreover, clearly $w$ can be at most $n^{1/2}$. Summing over all such $w$
we conclude that the number of tuples $(a,b)$ with $a+b=n$
and $a, b$ of the form above,
where one of $a$ and $b$ is divisible by any prime congruent
$3 \mod 4$, is at most $O(n^{1/2} \log \log n)$, which is of smaller order of magnitude than the expression $n^{1-2\varepsilon}$ above.
This finishes the proof.
$\textbf{Remark.}$
It seems likely that the number of representations $f(n)$ can be greatly improved by observing that one only needs $r_2(a)$ on average. This should produce $f(n)$
within a logarithmic factor. Moreover it seems possible to adapt Greaves's argument by replacing $p^2$ and $q^2$ by squares of integers not containing a prime $3\bmod 4$, achieving a further logarithmic saving.
(Let us briefly reflect why the argument works: Greaves uses the fact
that Iwaniec's half dimensional sieve can also handle sums of two squares.
The contribution from the almost trivial 'fact' is also quite useful.)
Let us briefly sketch another possible approach, which could be more
suitable for getting a result for all positive integers:
Let $f(n)$ denote the number of representations as a sum of two integers, both not containing any prime factor $3 \bmod 4$.
Let $r_{(a,b,c,d)}(n)$ denote the number of representations as sum $ax^2+by^2+cz^2+dt^2$.
We intend to show that $$n^\varepsilon r(n) \gg r_{(1,1,1,1)}(n)- 2 \sum_{p=3 \bmod 4} r_{(1,1,p^2,p^2)}(n) \gg r_{(1,1,1,1)}(n).$$
Observe that $r_{(1,1,p^2,p^2)}(n)\approx \frac{1}{p^2}r_{(1,1,1,1)} $ and that $\sum_{p =3\mod 4} \frac{1}{p^2}$ is a small and
finite number.
For a completely explicit result all we need is an explicit lower bound on
$r_{(1,1,1,1)}(n)$, which can be derived from Jacobi's formula,
and an explicit upper bound on expressions like $r_{(1,1,p^2,p^2)}(n)$,
which can be obtained either by the circle method using a Kloosterman
refinement, a modular forms approach, or via Dirichlet's hyperbola method. The big question then is if the
resulting numerical bounds allow the remaining finitely many cases
to be checked by a computer.