We have that: $k=\sum b_ta^t=\sum b_t^2$ we also have: $b_ta^t>(a-1)^2+b_t^2$ for $t>1$, so we get that a good $k$ has at most $2$ digits in base $a$. So we have: case 1: $b_2a+b_1=b_2^2+b_1^2$ Now for a pair $b_2,b_1$, we verify that $a-b_2,b_1$ also works, and also when $b_2=a/2$ we get: $(2b_1-1)^2=a^2+1$ wich gives $a=0$, contradiction. so there is an even number of solutions in this case. case 2: $b_1=b_1^2$ wich gives $k=1$ So $N_a$ is odd. Now finally we show case 1 has as many solutions as we would like for some $a$. Pick an even $a$ such that $a^2+1$ has at least $t$ prime factors all of them $=1$ mod $4$. Then, $a^2+1$ can be expressed as a sum of two squares in at least $2^t$ ways. Since $b_2=a/2+-\sqrt{a^2-4b_1^2+4b}/2$, iff $a^2+1=c^2+d^2$ with $c$ odd, put $2b_1-1=c$ and $b_2=a/2+-d/2$ So we get $N_a>2^{t+1}$, because every $c$ and $d$ give different values for $b_1$ and $b_2$

Here's a different way to do (b). (b) First of all, notice that if $a = (x^2+1)z + x$ for any $z, x \in \mathbb{N}$, then $x(xz+1) \cdot a + (xz+1)$ satisfies the property in the question. In otherwords, we have that $[x(xz+1)]^2 + (xz+1)^2 = x(xz+1) \cdot a + (xz+1)$ is satisfied. This implies that if we let $f(a)$ for $a \in \mathbb{N}$ be the number of integers $k$ such that $a > k^2+1$ and $k^2+1 | a-k,$ then $N_a \ge f(a).$ Finally, by the Chinese Remainder Theorem, if we select some positive integer $n$ such that $n \equiv 2^k$ (mod $2^{2k}+1)$ for each $1 \le k \le M$ and $n > 2^{2M}+ 1$, we are done. $\square$