Which Galois Field is isomorphic to this extension? Let $\alpha$ be an element in an algebraic closure of $GF(64)$ such that $\alpha^4=\alpha+1$. For which $r\in \mathbb{N}$ is $GF(64)$ adjoined $\alpha$ isomorphic to $GF(2^r)$?
[Adding the following bit by the OP from the comments, JL]
Since is $\alpha$ a root of the irreducible polynomial $x^4+x+1$ the degree of its minimal polynomial over $GF(2)$ i four. So $\alpha$ is in $GF(16)$. But $GF(16)$ is not a subfield of $GF(64)$, so I'm not sure where to go with this. 
 A: Let $E$ be an algebraic closure of $GF(64)$ and $\alpha \in E$ such that $\alpha^4 = \alpha + 1$. Raising both terms to the fourth power and using $char(E)=2$ you get that $\alpha^{16} = \alpha^4+1$. Doing that again, $\alpha^{64} = \alpha^{16}+1$. Combine this three equalities to get $\alpha^{64} = \alpha+3=\alpha+1$. This tells you that $\alpha$ is a root of $X^{64}-X-1$.
Now remember that $GF(64)$ is exactly the set of roots of $X^{64}-X$ in $E$. If $\alpha$ were in $GF(64)$, then $\alpha$ would be a common root of $X^{64}-X$ and $X^{64}-X-1$. But then $X-\alpha$ would be a factor of $(X^{64}-X) - (X^{64}-X-1) = 1$ which is an absurd. So $\alpha$ is not in $GF(64)$.
Looking at $f=X^4+X+1$ you discover that if $\gamma\in E$ is a root of $f$ then $\gamma+1$ and $\gamma^2$ are also roots of $f$ in $E$. Keep in mind that $char(E)=2$. With this information you can factor $f$ like this $$f=X^4+X+1=(X^2+X+(\alpha^2+\alpha))(X^2+X+(\alpha^2+\alpha+1))$$
If we prove that $\alpha^2+\alpha$ is in $GF(64)$ then $g=X^2+X+(\alpha^2+\alpha)$ is in $GF(64)[X]$ and $g(\alpha)=0$. So the minimal polynomial of $\alpha$ over $GF(64)$ divides $g$. Because $\alpha$ is not in $GF(64)$ then $g$ is the minimal polynomial of $\alpha$ over $GF(64)$. This gives $[GF(64)(\alpha):GF(64)]= 2$ and then $[GF(64)(\alpha):GF(2)]=2\cdot6=12$. So $r=12$.
Let's prove that $\alpha^2+\alpha$ is in $GF(64)$. Put $\beta = \alpha^2+\alpha$. Now $\beta^2=\alpha^4+\alpha^2$ and $\beta^2-\beta=\alpha^4-\alpha = 1$. This gives $\beta^2+\beta+1=0$. Multiply by $\beta - 1$ to obtain $\beta^3-1=0$. Multiply by $\beta$ to give $\beta^4 = \beta$. Raise to the fourth power and $\beta^{16}=\beta^4=\beta$. Do it again and $\beta^{64}= \beta$. This proves that $\beta$ is a root in $E$ of $X^{64}-X$ and then $\beta\in GF(64)$.
