Diagonalizable matrices A and B with $\mathrm{Tr}(A^k)=\mathrm{Tr}(B^k)$ have the same characteristic polynomial?

The equalities $\text{Tr}(A^k)=\text{Tr}(B^k)$ for all $k$ imply that $\text{Tr}(P(A))=\text{Tr}(P(B))$ for all polynomials $P$.

Let $\lambda$ be an eigenvalue of $A$. If $\lambda$ is not an eigenvalue of $B$, then we can choose a polynomial such that $P(\lambda)=1$, and $P(\mu)=0$ for every other eigenvalue of $A$ and all eigenvalues of $B$. Then we would get $\text{Tr}(P(A))>0$, $\text{Tr}(P(B))=0$, a contradiction. This reasoning implies that $A$ and $B$ have the same lists of eigenvalues. And they have to appear with the same multipliticites: because if $\lambda$ is an eigenvalue of $A$ with multiplicity $n$ and of $B$ with multiplicity $m$, then choosing $P$ with $P(\lambda)=1$ and $P=0$ on all other eigenvalues we have $$ n=\text{Tr}(P(A))=\text{Tr}(P(B))=m. $$ So $A,B$ have the same eigenvalues, with the same multiplicities. In particular, they have the same characteristic polynomial.

Edit: of course, as user1551 points out in his answer, my answer only works for fields where polynomials separate points.

The statement is false. Consider $A=I_2$ and $B=0$ over $GF(2)$, the field with two elements $1$ and $0$ (with $1+1=0$). Both $A$ and $B$ are diagonal matrices, hence diagonalisable. Also, $\newcommand{\tr}{\operatorname{tr}}\tr(A^k)=\tr(I_2)=1+1=0=\tr(B^k)$ for every positive integer $k$. Yet $A$ and $B$ are not similar to each other. Similar counterexamples apply to other fields and other dimensions when $\tr(I_n)=0$.

The statement is true when the underlying field is infinite. See Martin's or Igor's answers. Martin's answer does not work in all finite fields because we can have $\tr(P(A))=0$ even when $P(A)=I$. Igor's answer does not work in all finite fields because writing the characteristic polynomial of a matrix $X$ in terms of $\tr(X^k)$ requires integer division, which can fail when the field is finite. To illustrate, consider the characteristic polynomial of a $2\times2$ matrix $X$ with eigenvalues $\lambda_1$ and $\lambda_2$. The characteristic polynomial is $x^2 - (\lambda_1+\lambda_2) + \lambda_1\lambda_2$. Formally, $$ \lambda_1\lambda_2 = \frac12\left[(\lambda_1+\lambda_2)^2 - (\lambda_1^2+\lambda_2^2)\right] = \frac12\left( \tr(X)^2 - \tr(X^2) \right), $$ but you cannot divide by $2$ over $GF(2)$ because $2=0$.

Since the elementary symmetric functions can expressed through power symmetric functions (in a completely algorithmic way), and the power symmetric functions of the eigenvalues are precisely the traces of $A^k,$ while the elementary symmetric functions are the coefficients of the characteristic polynomial, we are done. What is amusing is that the Newton relations can be proved from the Cayley-Hamilton theorem by taking traces.