Given a finite cyclic group $G$ and any group $H$, let $\phi_1,\phi_2\colon G\to\mathrm{Aut}(H)$ be homomorphisms such that $\sigma\phi_1(G)\sigma^{-1} = \phi_2(G)$ for some $\sigma\in\mathrm{Aut}(H)$. Let $n\in\mathbb Z$ be chosen so that for all $x\in G$, $\sigma\phi_1(x)\sigma^{-1} = \phi_2(x)^n$. I'd like to show that $\gcd(n,\lvert G\rvert) = 1$.
I know that, given a generator $g$ of $G$, $\phi_1(g)$ and $\phi_2(g)$ must be generators of $\phi_1(G)$ and $\phi_2(G)$, respectively. Then $\sigma\phi_1(g)\sigma^{-1} = \phi_2(g)^n$ must be a generator of $\phi_2(G)$, so $n$ is relatively prime to $\lvert\phi_2(G)\rvert = \lvert\phi_1(G)\rvert$. However, how can I show that $n$ is relatively prime to $\lvert G\rvert$?
What you say cannot be proved.
Suppose you have that $n$ is coprime with $G$. Then you can consider the cyclic group $G'=G \oplus C_n$ (where $C_n$ is the cyclic group of order $n$). Clearly you have the projection $$p:G' \longrightarrow G$$ so now consider $\phi_1'=\phi_1 \circ p$ and $\phi_2'=\phi_2 \circ p$. $G',\phi_1', \phi_2'$ satisfy the same hypothesis of $G,\phi_1, \phi_2$, so your $n$ works for these as well. However, you can easily see that $n$ is not coprime with $|G'|$.