If $\forall x \in G, \exists k \in \mathbb Z^+ \backepsilon xa=a^kx $, then $\langle a \rangle$ is a normal subgroup In Pinter's A Book of Abstract Algebra, Chapter 14 Exercise E3 asks the reader to prove the following statement:

If $a$ is any element of $G$, $\langle a \rangle$ is a normal subgroup of $G$ iff $a$ has the following property: $\forall x \in G, \exists k \in \mathbb Z^+ \backepsilon xa=a^kx $

For this biconditional, I have no issue demonstrating the implication that:
if $\langle a \rangle$ is a normal subgroup, then $\forall x \in G, \exists k \in \mathbb Z^+ \backepsilon xa=a^kx $.
However, it is the other implication that I am struggling with...specifically:
if $\forall x \in G, \exists k \in \mathbb Z^+ \backepsilon xa=a^kx $, then $\langle a \rangle$ is a normal subgroup. 
Here is the issue that I am running into:
Given the antecedent, I can premultiply by $x^{-1}$ to arrive at:
$a=x^{-1}a^kx$ , which is equal to $a = (x^{-1})a^k(x^{-1})^{-1}$
At first glance this seems just fine...but then I realized that due to the existential quantifier, I am pretty sure that I have no way of knowing if all elements of $\langle a \rangle$ will make it into $a^k$. At most, I can say that at least one element of $\langle a \rangle$ has all of its conjugates in $\langle a \rangle$...for example, if $k$ is the same integer for all values of $x$. 
Any suggestions?

Hint: $ xa^nx^{-1}=a^{nk}$ can you prove this?
