If $a^4 + 4^b$ is prime, then $a$ is odd and $b$ is even. We say an integer $p>1$ is prime when its only positive divisors are $1$ and $p$. Let $a$ and $b$ be natural number not both $1$. Prove that if $a^4+4^b$ is prime, then $a$ is odd and $b$ is even.
I'm also given a hint:
Consider the expression $(x^2-2xy+2y^2)(x^2+2xy+2y^2)$.
What I have so far is:
Let $x=a^2, y=2^b$ and substitute it into the expression.
But I am not sure how to proceed. Can anyone help please?
 A: It's clear that $a$ must be odd, as otherwise the number would be divisible by $2$.
Suppose $b$ is odd. Then we can write our number as $a^4 + 4\cdot 4^{2n} = a^4 + 4 \cdot 2^{4n}$ for some $n$. You were given the key factorization,
$$ (a^4 + 4 b^4) = (a^2 + 2ab + 2b^2)(a^2 - 2ab + 2b^2).$$
here, that means
$$ a^4 + 4 \cdot 2^{4n} = (a^2 + 2 a 2^n + 2\cdot  2^{2n})(a^2 - 2 a 2^n + 2\cdot  2^{2n}),$$
which is a nontrivial factorization. Thus $b$ cannot be odd.
Aside:
This factorization identity is called Sophie Germain's identity, after the French mathematian and general polymath who noticed it while exploring number theory. She corresponded with Gauss and Legendre, and attended lectures at the newly founded École Polytechnique. To avoid ridicule, as it was extremely uncommon for women to pursue math (or indeed, to be allowed to pursue a great many professions), she used a male pen name for her initial correspondence.
A: I think that hint is terrible and only the geniuses in the class could get it right away. I put $(x^2 - 2xy + 2y^2)(x^2 + 2xy + 2y^2)$ into Wolfram Alpha and it gave me $x^4 + 4y^4$ as an "alternate form."
But the problem says "$4^b$", not "$4y^4$." If you're a precocious genius you can right away see that if $b$ is odd then $$4^b = 4 \left(2^{\frac{2b - 2}{4}} \right)^4.$$ I'm not a genius, so it took me a while (three days, to be precise) to arrive at this. It was only then that the problem finally unraveled. Now we have $$a^4 + 4 \left(2^{\frac{2b - 2}{4}} \right)^4 = (a^2 - 2^{\frac{2b - 2}{2}} a + 2^b)(a^2 + 2^{\frac{2b - 2}{2}} a + 2^b).$$
This means that with $b$ odd, the only way for the resulting number to be prime is for $(a^2 - 2^{\frac{2b - 2}{2}} a + 2^b)$ to equal $1$ or $-1$ somehow. There are four possible solutions to that equation, and they're all ruled out with the definition of the problem (because $a$ and $b$ are natural numbers not both equal to $1$, and $0$ is or isn't a "natural number" -- but that's a whole other can of worms). Therefore, under the constraints of the problem, odd $b$ gives a composite number, so $b$ must be even in order for the expression to give a prime (this is a necessary but not sufficient condition, of course).
Let's have a concrete example: $a = 1$, $b = 3$. Then $a^4 + 4^b = 65$, which is obviously composite. But still take the time to run it through Sophie Germain's identity: $1 + 4^3 = 1 + 4 (2^1)^4 = (1 - 2 \times 1 \times 2 + 2 \times 2^2)(1 + 2 \times 1 \times 2 + 2 \times 2^2) = 5 \times 13$.
As for the parity of $a$, that, as Bob Happ said in a comment, "is the easy part here."
