# 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.

• Why can't we have $a=0$ (or $m$)? Oct 18, 2013 at 1:55
• Oh right, if a = 0 or a = 1, then the underlying problem that I'm trying to solve follows trivially. I'll change that. Oct 18, 2013 at 2:00

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$.
• Wait, is this still true if a is not a power of 6? I suppose I should just use the original question, which is that 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$. Oct 18, 2013 at 2:20
• 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 $(x, p)=1$ which I get from $(a, p^k) = 1$. So I don't really need to reason about the 6th power anymore, just the square and the cube. Squares are nice, right? Oct 18, 2013 at 2:34