Suppose we have a relation defined as $xRy$ iff there exists $u, v \in \mathbb{N}$ such that $x^u = y ^v$. To prove transitivity we assume $xRy$ and $yRz$ and need to establish $xRz$. By definition of $R$ we have there exists $a, b, c, d \in \mathbb{N}$ such that $x^a = y^b$ and $y^c = z^d$.
At this point I'm stuck. I tried solving it by prime factorization, but this seems too long. I've seen someone give a proof where he did something like $$ (x^a)^k = (y^b)^k = y^{bk} \stackrel{(1)}{=} (y^c)^k = (z^d)^k $$ where the equality denoted with $(1)$ does not seem to make sense.
So, what is an easy way to show this? I think I'm missing something.
Observe that: $$ x^{ac} = (x^a)^c = (y^b)^c = (y^c)^b = (z^d)^b = z^{bd} $$