How to reason about congruences? If $x^2 \equiv a$ (mod $m$) and $y^3 \equiv a$ (mod $m$), then $\gcd(a,m) = 1$ Generally, I have no high level conception of what is going on in my number theory class. It feels like a loose collection of theorems and techniques that you can use on some problems, but I have trouble linking new theorems to my previous knowledge, or understanding the significance of them, so I forget them or never figure out how to use them. I would prefer more general advice with this as an example, rather than just hints at how to solve this particular problem, because I would inevitably fail to generalize.

If $a\ne z^6$ for any $z$, and $x^2 \equiv a$ (mod $m$) and $y^3 \equiv a$ (mod $m$), then $\gcd(a,m) = 1$

I'm trying to prove a more general statement, and I was going through it with a friend, and she used the above as a part of her proof, but I forgot how she proved it. It is the only step left for my proof.
In general, if you have a congruence $f(x) = a$ (mod $m$), then you take the prime factorization of $m = \prod_i p_i^{k_i}$ and look at $f(x) = a$ (mod $p_i^{k_i}$). But I don't know where to go from there. Hensel's lemma seems to sort of work to drop down to mod $p_i$ in a few cases, but I'm not sure if it works in this case.
In this case I am trying to prove that $\gcd(x,p_i) = 1$ (or y instead of x). If $\gcd(a,p_i^{k_i}) = 1$, then $\gcd(x^2,p_i^{k_i}) = 1$ so $\gcd(x,p_i) = 1$. But how do you get that first step? In general, it seems that for congruences of this form need $a$ and $m$ to be coprime in order to have solutions, but why is that the case? I couldn't find a theorem that works in this particular case either. 
I suppose I should add the original problem just in case someone can find a better solution, or if my method is a dead end.

If there exists $x$, $y$ such that $x^2 \equiv y^3  \equiv a$ mod $m$, then there exists a $z^6 \equiv a$ mod $m$

My proof strategy is to take $z=x^{−1}y^2$ so $z^6=(x^2)^{−3}(y^3)^4=a$ but I need $x^{-1}$ to be well defined so I need $\gcd(x,p)=1$ which I get from $(a,p_k)=1$. Alternatively, if I get that y is coprime, then I can adjust the exponents.
EDIT
This is actually wrong (edit, I think?). Instead we can deal with cases: if $p|a$, then $p^{6n}|a$. If $6n \ge k$, pick $z \equiv 0$, if $6n < k$, factor out the $p^{6n}$ and do the above construction. I can put in more detail in if anyone wants. I would still like an answer to my general question.

The original statement is false (which did not have the $z^6$ restriction).  Let $a=2^6=64$, and $m$ be arbitrary and even, so long as $m>a$.  Then $4^3=64=8^2$, and this is also true modulo $m$.  Yet $gcd(m,a)\ge 2$.
