# If $(m,n)=1$ and $mn=r^2$ for $m,n\in\mathbb{Z}^+$, prove that $m$ and $n$ are squares.

Honestly unsure how to proceed with this; I have some thoughts but don't know where to go with them.

$(m,n)=1\Longrightarrow m\nmid n$ and $n\nmid m$. But $mn=r^2$, so $\frac{r^2}{mn}=1$, and $mn\mid r^2$, and certainly $r^2\mid mn$ and by extention, $r\mid mn$.

-
Factor rsquared. Each prime factor must occur an even number of times. Primes must be assigned to m and n with no overlap, so both m and n will be perfect squares. You need to understand this. It is used in the elementary derivation of Pythagorean triples. – Bill Kleinhans Oct 9 '13 at 1:37

Hint: In the prime decomposition of $r^2$, each prime occurs twice. Let $p$ be one of the primes in the decomposition. What can you deduce from knowing $p \mid mn$?

-
$p\mid mn\Longrightarrow p\mid m$ or $p\mid n$... – agent154 Oct 9 '13 at 1:04
Correct. Now as $r^2$ is a perfect square, we know that $p^{2k} \mid r^2$ for some $k$, so $p^{2k} \mid mn$. What can we deduce from this? – Michael Albanese Oct 9 '13 at 1:05
Not sure what you mean by $p^{2k}$.. do you mean some prime squared? – agent154 Oct 9 '13 at 1:07
Not necessarily squared, I just mean the the heighest power of $p$ which divides $r^2$; $p^k$ divides $r$ for some $k$, so $p^{2k}$ divides $r^2$. Consider $r = 12$. We have $r^2 = 144$, and the prime $2$ is a factor of $144$, in fact $2^4 \mid 144$. – Michael Albanese Oct 9 '13 at 1:12
Well, I'm tempted to try and use Euclid's Divsibility Theorem again, but $p^{2k}$ is not prime, so we can't say $p^{2k}\mid m$ or $p^{2k}\mid n$. – agent154 Oct 9 '13 at 1:16

Note the following statemtent holds:

'If an integer is an square it's a product of finite number of squares of prime numbers'


Also it holds other way around:

'If in a product the factors are squares of prime numbers, then also the product is an square.'


Note that this doesn't just hold for prime numbers, but it's easier to use like that in our case.

Now using this we can prime factorize the numbers $m$ and $n$. Also we use the fact $(m,n) = 1$, so all prime factors are different.

$$m = p_1^{a_1}p_2^{a_2}p_3^{a_3}...p_k^{a_k}$$ $$n = q_1^{b_1}q_2^{b_2}q_3^{b_3}...q_l^{b_l}$$

So we know that:

$$mn = r^2$$

Now doing the prime factorization on both sides and using the first property on the RHS, because obviously the prime factors are same, as they are same numbers we get:

$$p_1^{a_1}p_2^{a_2}p_3^{a_3}...p_k^{a_k}q_1^{b_1}q_2^{b_2}q_3^{b_3}...q_l^{b_l} = p_1^{2c_1}p_2^{2c_2}p_3^{2c_3}...p_k^{2c_k}q_1^{2d_1}q_2^{2d_2}q_3^{2d_3}...q_l^{2d_l}$$

Divide the equation with the LHS we get:

$$1 = p_1^{2c_1-a_1}p_2^{2c_2-a_2}p_3^{2c_3-a_3}...p_k^{2c_k-a_k}q_1^{2d_1-b_1}q_2^{2d_2-b_2}q_3^{2d_3-b_3}...q_l^{2d_l-b_l}$$

Because the only factor of $1$ is $1$ it's obvious that every term on the RHS is $1$. So we have:

$$p_1^{2c_1-a_1} = 1 \iff 2c_1-a_1=0 \iff 2c_1=a_1$$

We do the same on all factors and we get that $a_1,a_2,a_3...a_k, b_1,b_2,b_3...b_l$ are multiple of two.

So using the second property we know that $m$ and $n$ are square numbers.

-

Here's the solution I came up with. I feel like I have (almost) all the important details, but I don't know if I explained it properly..

Let the canonical form of $r$ be as follows: \begin{equation*} r=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots p_{r}^{\alpha_{r}} \end{equation*} Therefore, the canonical form of $r^{2}$ is \begin{equation*} r^{2}=p_{1}^{2\alpha_{1}}p_{2}^{2\alpha_{2}}\cdots p_{r}^{2\alpha_{r}} \end{equation*} Given that $r^{2}=mn$, it follows that $mn=p_{1}^{2\alpha_{1}}p_{2}^{2\alpha_{2}}\cdots p_{r}^{2\alpha_{r}}$. If we break down $m$ and $n$, $m=p_{1}^{\beta_{1}}p_{2}^{\beta_{2}}\cdots p_{r}^{\beta_{r}}$ and $n=p_{1}^{\gamma_{1}}p_{2}^{\gamma_{2}}\cdots p_{r}^{\gamma_{r}}$. But since $(m,n)=1$, either $\beta_{i}=0$ or $\gamma_{i}=0$. In the case where $\beta_{i}=0$, $\gamma_{i}=2\alpha_{i}$, and where $\gamma_{i}=0$, $\beta_{i}=2\alpha_{i}$. Therefore, \begin{align*} m&=(p_{1}^{\beta_{1}}p_{2}^{\beta_{2}}\cdots p_{r}^{\beta_{r}})^{2}\\ n&=(p_{1}^{\gamma_{1}}p_{2}^{\gamma_{2}}\cdots p_{r}^{\gamma_{r}})^{2} \end{align*} And $m$ and $n$ are squares.

-
Looks good to me. – Michael Albanese Oct 14 '13 at 0:03
You should accept this answer (if you don't find any of the other answers acceptable). – Michael Albanese Jun 12 '14 at 5:28