Primitive polynomials of finite fields there are two primitive polynomials which I can use to construct $GF(2^3)=GF(8)$:
$p_1(x) = x^3+x+1$
$p_2(x) = x^3+x^2+1$
$GF(8)$ created with $p_1(x)$:
0
1
$\alpha$
$\alpha^2$
$\alpha^3 = \alpha + 1$
$\alpha^4 = \alpha^3 \cdot \alpha=(\alpha+1) \cdot \alpha=\alpha^2+\alpha$
$\alpha^5 = \alpha^4 \cdot \alpha = (\alpha^2+\alpha) \cdot \alpha=\alpha^3 + \alpha^2 = \alpha^2 + \alpha + 1$
$\alpha^6 = \alpha^5 \cdot \alpha=(\alpha^2+\alpha+1) \cdot \alpha=\alpha^3+\alpha^2+\alpha=\alpha+1+\alpha^2+\alpha=\alpha^2+1$
$GF(8)$ created with $p_2(x)$:
0
1
$\alpha$
$\alpha^2$
$\alpha^3=\alpha^2+1$
$\alpha^4=\alpha \cdot \alpha^3=\alpha \cdot (\alpha^2+1)=\alpha^3+\alpha=\alpha^2+\alpha+1$
$\alpha^5=\alpha \cdot \alpha^4=\alpha \cdot(\alpha^2+\alpha+1) \cdot \alpha=\alpha^3+\alpha^2+\alpha=\alpha^2+1+\alpha^2+\alpha=\alpha+1$
$\alpha^6=\alpha \cdot (\alpha+1)=\alpha^2+\alpha$
So now let's say I want to add $\alpha^2 + \alpha^3$ in both fields. In field 1 I get $\alpha^2 + \alpha + 1$ and in field 2 I get $1$. Multiplication is the same in both fields ($\alpha^i \cdot \alpha^j = \alpha^{i+j\bmod(q-1)}$. So does it work so, that when some $GF(q)$ is constructed with different primitive polynomials then addition tables will vary and multiplication tables will be the same? Or maybe one of presented polynomials ($p_1(x), p_2(x)$) is not valid to construct field (altough both are primitive)?
 A: The generator $\alpha$ for your field with the first description cannot be equal to the generator $\beta$ for your field with the second description.  An isomorphism between $\mathbb{F}_2(\alpha)$ and $\mathbb{F}_2(\beta)$ is given by taking $\alpha \mapsto \beta + 1$; you can check that $\beta + 1$ satisfies $p_1$ iff $\beta$ satisfies $p_2$.
A: To more directly answer the questions asked:


*

*Yes, in general using different primitive polynomials will change the operations.  If one uses expressions such as αi to refer to field elements (as is done in GAP and Magma, for instance), then the multiplication table stays the same, and the addition table changes.  However, if one uses expressions like α2+α+1 (as is done in Macaulay2 and Maple, for instance) , then addition table stays the same, and the multiplication table changes.  Zech logarithms are used to efficiently convert between the two representations.

*Both of your polynomials p1 and p2 are good.  This is proven in Charles Staats's answer.
A: The situation is not so different in a simpler context, the field of 5 elements, also known as the integers modulo 5. Whether $\alpha$ is $2$ or $3$, the field is $0,1,\alpha,\alpha^2,\alpha^3$, but whether $\alpha+\alpha+1=0$ depends on which $\alpha$ you choose. 
