PART 1. I consider the generic case. The problem is as follows We randomly choose $B\in M_2(\mathbb{Z})$ and let $A=B^k$. $k,A$ are known and $B$ is unknown; find the $X$'s such that $X^k=A$.

i) Calculate $p(x)$, the characteristic polynomial of $A$, and let $q(y)=p(y^k)$.

ii) Factorise in irreducibles over $\mathbb{Z}$: $q(y)=q_1(y)\cdots q_l(y)$.

Generically, when $k$ is odd, there is exactly one factor $q_i$ of degree $2$ and, when $n$ is even, there are exactly two factors $q_i,q_j$ of degree $2$ corresponding to $2$ opposite values ​​of $X$.

For example, let $q_1(y)$ be one factor of degree $2$ and let $Q$ be its companion matrix. Then, there is an unknown matrix $R\in M_2(\mathbb{Q})$ s.t. $A=RQ^kR^{-1}$.

iii) Solve the equation $RQ^k-AR=0$ ($4$ linear equations in the $4$ unknowns $(r_{i,j})$'s). Generically, we obtain a vector space solution of dimension $2$, that is, a set of solutions that depends on $2$ parameters $u,v$.

iv) Randomly choose $u,v$; we obtain (except if we are very unlucky; in this case, make another choice) a particular matrix $R$ and we deduce the essential solution $X=RQR^{-1}$.

PART 2. If $k$ is not given,we calculate $\delta=\det(A)$; we are looking for the $k$ such that $\delta$ is a power $k^{th}$. There is only a finite number of possible values ​​of $k$, except when $\delta=\pm 1$.

For $\delta=1$, every value of $k$ gives an essential solution. For $\delta=-1$, each odd value of $k$ gives an essential solution.

PART 3. If we randomly choose $A$, then, generically, $\delta$ is not a power; moreover, if by extraordinary $\delta$ is a power $k^{th}$, then, genereically, the matrix $R$ cannot be made invertible.

PART 1. I consider the generic case. The problem is as follows We randomly choose $B\in M_2(\mathbb{Z})$ and let $A=B^k$. $k,A$ are known and $B$ is unknown; find the $X$'s such that $X^k=A$.

i) Calculate $p(x)$, the characteristic polynomial of $A$, and let $q(y)=p(y^k)$.

ii) Factorise in irreducibles over $\mathbb{Z}$: $q(y)=q_1(y)\cdots q_l(y)$.

Generically, when $k$ is odd, there is exactly one factor $q_i$ of degree $2$ and, when $n$ is even, there are exactly two factors $q_i,q_j$ of degree $2$ corresponding to $2$ opposite values ​​of $X$.

For example, let $q_1(y)$ be one factor of degree $2$ and let $Q$ be its companion matrix. Then, there is an unknown matrix $R\in M_2(\mathbb{Q})$ s.t. $A=RQ^kR^{-1}$.

iii) Solve the equation $RQ^k-AR=0$ ($4$ linear equations in the $4$ unknowns $(r_{i,j})$'s). Generically, we obtain a vector space solution of dimension $2$, that is, a set of solutions that depends on $2$ parameters $u,v$.

iv) Randomly choose $u,v$; we obtain (except if we are very unlucky; in this case, make another choice) a particular matrix $R$ and we deduce the essential solution $X=RQR^{-1}$.

PART 2. If $k$ is not given,we calculate $\delta=\det(A)$; we are looking for the $k$ such that $\delta$ is a power $k^{th}$. There is only a finite number of possible values ​​of $k$, except when $\delta=\pm 1$.

Correction. For $\delta=\pm 1$, cf. the Silverman's post.

PART 3. If we randomly choose $A$, then, generically, $\delta$ is not a power; moreover, if by extraordinary $\delta$ is a power $k^{th}$, then, generically, the matrix $R$ cannot be made invertible.

PART 1. I consider the generic case. The problem is as follows We randomly choose $B\in M_2(\mathbb{Z})$ and let $A=B^k$. $k,A$ are known and $B$ is unknown; find the $X$'s such that $X^k=A$.

i) Calculate $p(x)$, the characteristic polynomial of $A$, and let $q(y)=p(y^k)$.

ii) Factorise in irreducibles over $\mathbb{Z}$: $q(y)=q_1(y)\cdots q_l(y)$.

Generically, when $k$ is odd, there is exactly one factor $q_i$ of degree $2$ and, when $n$ is even, there are exactly two factors $q_i,q_j$ of degree $2$ corresponding to $2$ opposite values ​​of $X$.

For example, let $q_1(y)$ be one factor of degree $2$ and let $Q$ be its companion matrix. Then, there is an unknown matrix $R\in M_2(\mathbb{Q})$ s.t. $A=RQ^kR^{-1}$.

iii) Solve the equation $RQ^k-AR=0$ ($4$ linear equations in the $4$ unknowns $(r_{i,j})$'s). Generically, we obtain a vector space solution of dimension $2$, that is, a set of solutions that depends on $2$ parameters $u,v$.

iv) Randomly choose $u,v$; we obtain (except if we are very unlucky; in this case, make another choice) a particular matrix $R$ and we deduce the essential solution $X=RQR^{-1}$.

PART 2. If $k$ is not given,we calculate $\delta=\det(A)$; we are looking for the $k$ such that $\delta$ is a power $k^{th}$. There is only a finite number of possible values ​​of $k$, except when $\delta=\pm 1$.

For $\delta=1$, every value of $k$ gives an essential solution. For $\delta=-1$, each odd value of $k$ gives an essential solution.

PART 3. If we randomly choose $A$, then, generically, $q$ has no factors of degree $2$.

PART 1. I consider the generic case. The problem is as follows We randomly choose $B\in M_2(\mathbb{Z})$ and let $A=B^k$. $k,A$ are known and $B$ is unknown; find the $X$'s such that $X^k=A$.

i) Calculate $p(x)$, the characteristic polynomial of $A$, and let $q(y)=p(y^k)$.

ii) Factorise in irreducibles over $\mathbb{Z}$: $q(y)=q_1(y)\cdots q_l(y)$.

Generically, when $k$ is odd, there is exactly one factor $q_i$ of degree $2$ and, when $n$ is even, there are exactly two factors $q_i,q_j$ of degree $2$ corresponding to $2$ opposite values ​​of $X$.

For example, let $q_1(y)$ be one factor of degree $2$ and let $Q$ be its companion matrix. Then, there is an unknown matrix $R\in M_2(\mathbb{Q})$ s.t. $A=RQ^kR^{-1}$.

iii) Solve the equation $RQ^k-AR=0$ ($4$ linear equations in the $4$ unknowns $(r_{i,j})$'s). Generically, we obtain a vector space solution of dimension $2$, that is, a set of solutions that depends on $2$ parameters $u,v$.

iv) Randomly choose $u,v$; we obtain (except if we are very unlucky; in this case, make another choice) a particular matrix $R$ and we deduce the essential solution $X=RQR^{-1}$.

PART 2. If $k$ is not given,we calculate $\delta=\det(A)$; we are looking for the $k$ such that $\delta$ is a power $k^{th}$. There is only a finite number of possible values ​​of $k$, except when $\delta=\pm 1$.

For $\delta=1$, every value of $k$ gives an essential solution. For $\delta=-1$, each odd value of $k$ gives an essential solution.

PART 3. If we randomly choose $A$, then, generically, $\delta$ is not a power; moreover, if by extraordinary $\delta$ is a power $k^{th}$, then, genereically, the matrix $R$ cannot be made invertible.