If for invertible matrices $A$ and $X$, $XAX^{-1}=A^2$ then eigenvalues of $A$ are $n^{th}$ roots of unity.

Since similar matrices have the same eigenvalues, for any eigenvalue $b$ of $A$, the numbers $b^2, b^4, b^8, ...$ are also eigenvalues of $A$ (since by iteration, $A$ is similar to all those powers of itself and $b^k$ is an eigenvalue of $A^k$).

Also, $b$ is non-zero since $A$ is invertible.

But there are only finitely many eigenvalues of $A$, so that sequence of powers of $b$ must have repeats in it, i.e. $b^j = b^k$ for some $j<k$ and that yields that $b$ is a root of unity (since it's not $0$).

Since each eigenvalue is a root of unity, just take the least common multiple of the exponents to get a value of $n$ that works.

(sorry I don't know how to format well, so I've written mostly in English prose)