# If $a, b$ are relatively prime proof.

Prove that if $a$ and $b$ are relatively prime integers and $ab$ is a perfect square so are $a$ and $b$. Show by counterexample that the relatively prime condition is necessary.

I dont know how to start this proof. Also the second "counterexample" part is messing me up. Thanks for any help!

• Is $2\times 18$ a perfect square? – egreg Jun 7 '14 at 15:48
• Counterexample: Let's pick $a = b = 2$. Then $ab = 4$ which is a perfect square, and hence so are $a$ and $b$. Hm... Something seems off there – Sten Jun 7 '14 at 15:48
• @egreg and Sten, ($2$ and $18$) and ($2$ and $2$) are not relatively prime. – Rocket Man Jun 7 '14 at 15:48
• @AJStas - That's the counterexample part – Sten Jun 7 '14 at 15:51
• Minor comment: The theorem as stated is false, for $(-4)(-9)$ is a perfect square, but neither $-4$ nor $-9$ is a perfect square. Easy fix: specify that $a$ and $b$ are positive integers. – André Nicolas Jun 7 '14 at 16:22

Counterexample (hint): take $a=b$ (hint: not any $a$ will do)

Proof (hint): write $ab=c^2$ and consider the decomposition of $c$ into prime factors; each of these occurs either in $a$ or in $b$ but not in both.

• ---------------------- – Vladimir Jun 7 '14 at 15:51
• I admitted fault above. OOPS! :) – Rocket Man Jun 7 '14 at 15:53
• @Vladimir this doesn't work for just any $a,b$ as a counterexample, for instance $a=b=4$. – DanZimm Jun 7 '14 at 15:54
• Sure this doesn't; I should have written "hint" there, too – Vladimir Jun 7 '14 at 15:57
• @Vladimir just bustin chops, realize now my comment sounds jerkish, sorry! – DanZimm Jun 7 '14 at 16:01

First, you must restrict to $\,a,b\in \Bbb N\,$ else it is false, e.g. $\, (-1)(-4) = 2^2$ but $\,-4\,$ is not a square.

Theorem $\ a,b\,$ coprime, $\, ab=n^2\Rightarrow\, a,b\,$ are squares, if $\,a,b,n\in \Bbb N.$

Proof $\$ By induction on $\,n.\,$ Clear if $\,n=1.\,$ Else $\,n > 1,\,$ so some prime $\,p\mid n\,$ so $\,p^2\mid n^2\!= ab,\,$ $\rm\color{#c00}{thus}$ $\,p^2\mid a\,$ or $\,p^2\mid b,\,$ by $\,a,b\,$ coprime. Wlog $\,p^2\mid b,\,$ thus $\,ab=n^2\Rightarrow\ a(b/p^2) = (n/p)^2$ by canceling $\,p^2.\,$ Since $\,n/p < n,\,$ by induction there are $\,c,d\in\Bbb N$ such that $\, a = c^2,\ b/p^2 = d^2,\,$ so $\,b = (pd)^2.\$ QED

Remark $\$ The $\rm\color{#c00}{key\ property}$ used is that $\,p^2\mid ab\,\Rightarrow\,p^2\mid a\,$ or $\,p^2\mid b,\:$ if $\,a,b\,$ are coprime. This is an immediate consequence of the Fundamental Theorem of Arithmetic (existence and uniqueness of prime factorizations), or equivalent well-known properties, e.g. one can iterate Euclid's Lemma $\ p\mid ab\,\Rightarrow\, p\mid a\,$ or $\,p\mid b.\,$ The same holds true for $\,k$'th powers of primes, so the proof generalizes from squares to $\,k$'th powers and, further, from $\,\Bbb Z\,$ to any UFD (e.g. $\,F[x],\,$ a polynomial ring over a field). In the general case one must allow for unit factors, i.e. the result is that $\,a = uc^2,\ b = u^{-1} d^2$ for some $\,c,d\,$ and some unit (invertible) $\,u.\,$ We eliminated $\, u = \pm1 \in \Bbb Z\,$ by requiring $\,a,b > 0.$

Here is some help on the proof, I see there is already help for the counterexample.

If $a$ and $b$ are relatively prime then consider the prime factorization of each

$$a = p_1^{a_1} \cdots p_k^{a_k}$$ $$b = q_1^{b_1} \cdots q_m^{b_m}$$

since they are relatively prime they can share no prime factors. That is $p_i \ne q_j$ for any $i$ and $j$. Now

$$ab = p_1^{a_1} \cdots p_k^{a_k}q_1^{b_1} \cdots q_m^{b_m}$$

is a perfect square. What does this say about the exponents? (Hint: Think about parity)

• Does that mean exponents cannot be equal? – user02398409 Jun 7 '14 at 15:56
• The square root is the same as $\frac{1}{2}$ power. That is taking the square root cuts your exponents in half. When I cut my exponents in half I still need them to be integers. Half of an integer only still an integer if it is what? – John Machacek Jun 7 '14 at 16:00
• So only the exponents can be evens – user02398409 Jun 7 '14 at 16:00
• Correct, very good! – John Machacek Jun 7 '14 at 16:02

A perfect square has only prime factors with an even exponent, like $86436=2^2\cdot3^2\cdot7^4$.

If $a$ and $b$ have no common prime factor, then all their own exponents must be even. Like $9604=2^2\cdot7^4$ and $9=3^2$.

But when $a$ and $b$ have common prime factors with an odd exponent, the product will have an even exponent as well. Like $1372=2^2\cdot7^3$ and $63=3^2\cdot7$.

Beware that you can also have non-relatively-primes $a$ and $b$ giving a perfect square and being perfect squares themselves, like $196=2^2\cdot7^2$ and $441=3^2\cdot7^2$.

Consider $a=p^{\alpha_1}_1p^{\alpha_2}_2\cdots~p^{\alpha_r}_r$ and $b=q^{\beta_1}_1q^{\beta_2}_2\cdots~q^{\beta_s}_s$. Since $gcd(a,b)=1$ we have $\{p_1,p_2,\cdots,p_r\} \cap \{q_1,q_2,\cdots,q_s\} = \phi$. Now $ab=p^{\alpha_1}_1p^{\alpha_2}_2\cdots~p^{\alpha_r}_r\times q^{\beta_1}_1q^{\beta_2}_2\cdots~q^{\beta_s}_s$ and $ab$ is a perfect square hence all exponents of $p_i's$ and $q_j's$ are even for $1\leq i\leq r$, $1\leq j\leq s$. Hence $a$ and $b$ are also square since exponent are even.