Decomposition of Algebraic Numbers into Sets of Real and Rational Numbers Show that a real number $\alpha$ is algebraic of degree at most $n$ if and only if there are real numbers $\{a_1, a_2, ..., a_n\}$ such that for every $k \in \mathbb{N}$ there exist rational numbers $\{b_{1,\space k}, ..., b_{n, \space k}\}$ such that $\alpha^k = a_1b_{1,\space k} + ... + a_nb_{n,\space k}$. 
There are two hints: For the forward assertion use the Euclidean Algorithm and for the reverse use linear algebra.
I have been staring at this problem for hours and all of my attempts have led me nowhere. I would appreciate any suggestions on how to proceed or any other references.
One failed attempt: I tried to argue that $\alpha^k$ = $(\alpha^{n})^{k/n}$ and from here I tried to exponentiate $p(\alpha) - \alpha^n$ and proceed inductively. I ended up with a mess and did not think it would get me anywhere
 A: For the first direction, let me give you an example. Suppose $\alpha = 1 + \sqrt[3] 2$. Then $(\alpha - 1)^3 - 2 = 0$. So we have
$$ \alpha^3 - 3 \alpha^2 + 3 \alpha - 3 = 0. $$
Thus
$$ \alpha^3 = 3 \cdot \alpha^0 - 3 \cdot \alpha^1 + 3 \cdot \alpha^2. \tag{1} $$
Now I multiply both sides by $\alpha$ to obtain
$$ \alpha^4 = 3 \cdot \alpha^1 - 3 \cdot \alpha^2 + 3 \cdot \alpha^3. $$
Using $(1)$ we write this as
$$ \alpha^4 = 9 \cdot \alpha^0 - 6 \alpha^1 + 6 \alpha^2. $$
Likewise, if we multiply this by $\alpha$ and apply $(1)$ we obtain
$$ \alpha^5 = 18 \cdot \alpha^0 - 9 \cdot \alpha^1 + 12 \cdot \alpha^2. $$
Repeating this, we observe that we can always write
$$ \alpha^k = b_{0,k} \cdot \alpha^0 + b_{1,k} \cdot \alpha^1 + b_{2,k} \cdot \alpha^2 $$
for some rational numbers $b_{0,k}, b_{1,k}, b_{2,k}$.
Try using the polynomial division (the Euclidean Algorithm) to make this precise.

For the second direction, show that $1, \alpha, \alpha^2, \dots, \alpha^n$ are linearly dependent over $\mathbf{Q}$ by showing that they belong to a $\mathbf{Q}$-vector space of dimension at most $n$. What does linear dependence tell you?
