I'm aware that there are already two questions about this specific proof (namely this one and this one), but I'm specifically puzzled by Spivak's approach in his Answer Book.
The basic idea is clear enough: one needs to find a polynomial expression of the form $x^6 + a_5 x^5 + a_4 x^4 + a_3 x^3 + a_2 x^2 + a_1 x + a_0$ (with $a_0, \dots, a_5$ integers) with $\sqrt{2} + \sqrt[3]{2}$ as a root; then, by Gauss's lemma, since $\sqrt{2} + \sqrt[3]{2}$ is not an integer, it is not rational either. The question thus reduces to finding the appropriate $a_0, \dots, a_5$. And here is where I got confused.
Spivak's idea is the following: let $x = \sqrt{2} + \sqrt[3]{2}$ and $n = 2^{\frac{1}{6}}$. We can then write the first powers of $x$ in terms of $n$ as follows:
$x^0 = n^0$
$x^1 = n^2 + n^3$
$x^2 = 2n^0 + n^4 + 2n^5$
$x^3 = 2n^0 + 6n + 6n^2 + 2n^3$
$x^4 = 4n^0 + 2n^2 + 8n^3 + 12n^4 + 8n^5$
$x^5 = 40n^0 + 40n + 20n^2 + 4n^3 + 2n^4 + 10n^5$
$x^6 = 12n^0 + 24n + 60n^2 + 80n^3 + 60n^4 + 24n^5$
This gives us the following table:
$\begin{array}{l | c | r} & n^0 & n^1 & n^2 & n^3 & n^4 & n^5 \\ x^0 & 1 & 0 & 0 & 0 & 0 & 0 \\ x^1 & 0 & 0 & 1 & 1 & 0 & 0 \\ x^2 & 2 & 0 & 0 & 0 & 1 & 2 \\ x^3 & 2 & 6 & 6 & 2 & 0 & 0 \\ x^4 & 4 & 0 & 2 & 8 & 12 & 8 \\ x^5 & 40 & 40 & 20 & 4 & 2 & 10 \\ x^6 & 12 & 24 & 60 & 80 & 60 & 24 \end{array}$
(Note that there's a missing $4$ in the second column of Spivak's own table on p. 14, with a corresponding missing term in the first equation below)
This is the part I don't really understand. Spivak then claims that the integer coefficients $a_0, \dots, a_5$ are the integers satisfying the system of linear equations generated by the columns of the above table, i.e. satisfying:
$a_0 + 2a_2 + 2a_3 + 4a_4 + 40a_5 + 12 =0$
$6a_3 + 40a_5 + 24=0$
$a_1 + 6a_3 + 2a_4 + 20a_5 + 60 = 0$
$a_1 + 2a_3 + 8a_4 + 4a_5 + 80 = 0$
$a_2 + 12a_4 +2a_5 + 60 =0$
$2a_2 + 8a_4 + 10a_5 + 24 = 0$
I checked and indeed the solution to this system of equations indeed gives us the right answer. But I don't understand why. That is, I don't understand (a) what is the heuristics behind the solution, i.e. how he came up with this idea and, more importantly, (b) why taking the columns in the above table as coefficients in a system of linear equations gives us the correct solution.
If someone could explain this to me, I would be immensely grateful!
Let's say that $$x^i = \sum_{j = 0}^5 c_{i,j} n^j. \tag{1}$$
Let $C$ be the matrix $(c_{i,j})$ and let $X = (x^0,\dots,x^6)^T$ and $N = (n^0, \dots, n^5)^T$. Equation $(1)$ says that
$$ X = CN. $$
Now let $A = (a_0, \dots, a_6)$. Then $AX = a_0x^0 + \dots + a_6x^6.$ So we want
$$ AX = ACN = 0. $$
Since $n^0,\dots,n^5$ are linearly independent, this means that $AC = 0$. If you expand this product you get
$$ AC = (b_0, \dots, b_5) = (0,\dots,0) $$
where
$$ b_k = \sum_{j = 0}^6 a_j c_{i,k} = 0. $$
Some additional thoughts:
Spivak sets $a_6 = 1$ when solving $\sum_{j = 0}^6 a_j c_{i,k} = 0$. This avoids the solution $A = (0,\dots,0)$.
As Bill Dubuque pointed out in the comments: this works because $\mathbf{Q}[2^{1/6}]$ is a 6-dimensional vector space and $x^0,\dots,x^6$ is seven vectors (necessarily linearly dependent). If you use fewer powers of $x$ you will still get the equation $AC = 0$ but only $A = (0,\dots,0)$ will be a solution.