The only gap in Piotr Migdal's answer is the fact that for every eigenvalue $\lambda$ of $A^n$, there is a $\lambda$-eigenvector of $A^n$ which is an eigenvector of $A$. Here is a proof. Let $\lambda$ be an eigenvalue of $A^n$. Let $U$ be the set of all $\lambda$-eigenvectors of $A^n$ (and $0$). It is a subspace. If $A^nv=\lambda v$, then $A^n Av=AA^n v=\lambda Av$, so $AU\subseteq U$. Then $A$ has an eigenvector $u$ in $U$. The end of the proof is as in Migdal's answer. Let $\lambda$ be an eigenvalue of $A^n$. Then (by the above) there exists a non-zero vector $v$ such that $A^nv=\lambda v$ and $Av=\mu v$ for some $\mu$. Then $A^n v=\mu^nv=\lambda v$, so $v=\mu^n$ - every eigenvalue of $A^n$ is the $n$th power of an eigenvalue of $A$.

Comment This proof does use the Fundamental Theorem of algebra: we need to know that every subspace invariant under $A$ contains an eigenvector of $A$. For non-algebraically closed fields, the result is not true of course.

The only gap in Piotr Migdal's answer is the fact that for every eigenvalue $\lambda$ of $A^n$, there is a $\lambda$-eigenvector of $A^n$ which is an eigenvector of $A$. Here is a proof. Let $\lambda$ be an eigenvalue of $A^n$. Let $U$ be the set of all $\lambda$-eigenvectors of $A^n$ (and $0$). It is a subspace. If $A^nv=\lambda v$, then $A^n Av=AA^n v=\lambda Av$, so $AU\subseteq U$. Then $A$ has an eigenvector $u$ in $U$. The end of the proof is as in Migdal's answer. Let $\lambda$ be an eigenvalue of $A^n$. Then (by the above) there exists a non-zero vector $v$ such that $A^nv=\lambda v$ and $Av=\mu v$ for some $\mu$. Then $A^n v=\mu^nv=\lambda v$, so $\lambda=\mu^n$ - every eigenvalue of $A^n$ is the $n$th power of an eigenvalue of $A$.

Comment This proof does use the Fundamental Theorem of algebra: we need to know that every subspace invariant under $A$ contains an eigenvector of $A$. For non-algebraically closed fields, the result is not true of course.

The only gap in Piotr Migdal's answer is the fact that for every eigenvalue $\lambda$ of $A^n$, there is a $\lambda$-eigenvector of $A^n$ which is an eigenvector of $A$. Here is a proof. Let $\lambda$ be an eigenvalue of $A^n$. Let $U$ be the set of all $\lambda$-eigenvectors of $A^n$ (and $0$). It is a subspace. If $A^nv=\lambda v$, then $A^n Av=AA^n v=\lambda Av$, so $AU\subseteq U$. Then $A$ has an eigenvector $u$ in $U$. The end of the proof is as in Migdal's answer. Let $\lambda$ be an eigenvalue of $A^n$. Then (by the above) there exists a non-zero vector $v$ such that $A^nv=\lambda v$ and $Av=\mu v$ for some $\mu$. Then $A^n v=\mu^nv=\lambda v$, so $v=\mu^n$ - every eigenvalue of $A^n$ is the $n$th power of an eigenvalue of $A$.

The only gap in Piotr Migdal's answer is the fact that for every eigenvalue $\lambda$ of $A^n$, there is a $\lambda$-eigenvector of $A^n$ which is an eigenvector of $A$. Here is a proof. Let $\lambda$ be an eigenvalue of $A^n$. Let $U$ be the set of all $\lambda$-eigenvectors of $A^n$ (and $0$). It is a subspace. If $A^nv=\lambda v$, then $A^n Av=AA^n v=\lambda Av$, so $AU\subseteq U$. Then $A$ has an eigenvector $u$ in $U$. The end of the proof is as in Migdal's answer. Let $\lambda$ be an eigenvalue of $A^n$. Then (by the above) there exists a non-zero vector $v$ such that $A^nv=\lambda v$ and $Av=\mu v$ for some $\mu$. Then $A^n v=\mu^nv=\lambda v$, so $v=\mu^n$ - every eigenvalue of $A^n$ is the $n$th power of an eigenvalue of $A$.

Comment This proof does use the Fundamental Theorem of algebra: we need to know that every subspace invariant under $A$ contains an eigenvector of $A$. For non-algebraically closed fields, the result is not true of course.