Primes and Squares again

• Oct 2nd 2009, 01:23 AM
dlbsd
Primes and Squares again
Q: Show that if a, b are positive integers such at (a,b)=1 and ab is a square, then a and b are also squares.

Suppose a and b are not squares, then a=h*k and b=p*q where h,k,p,q are all unique primes. (Is this the right approach to this proof?)
• Oct 2nd 2009, 03:46 AM
Taluivren
Hi,

Hint: A number is a perfect square iff all exponents in its prime decomposition are even.

Use this on ab. Since (a,b)=1, it is clear how prime decompositions of a and of b must look like.
• Oct 2nd 2009, 04:01 AM
aman_cc
Quote:

Originally Posted by dlbsd
Q: Show that if a, b are positive integers such at (a,b)=1 and ab is a square, then a and b are also squares.

Suppose a and b are not squares, then a=h*k and b=p*q where h,k,p,q are all unique primes. (Is this the right approach to this proof?)

Let \$\displaystyle ab=x^2\$
Let \$\displaystyle p\$ be a prime, such that \$\displaystyle p|a\$
Now \$\displaystyle p\$ can't divide \$\displaystyle b\$ as \$\displaystyle (a,b)=1\$
So,\$\displaystyle p|x\$
\$\displaystyle \Rightarrow p^2|x^2\$
\$\displaystyle \Rightarrow p^2|ab\$
\$\displaystyle \Rightarrow p^2|a\$

Thus power of prime in a(and by similar logic in b) are all even. Thus either is a perfect sqaure as well.

This is wrong ! Please see below from post by BingK
• Oct 2nd 2009, 06:09 AM
dlbsd
Quote:

Originally Posted by aman_cc
Thus power of prime in a(and by similar logic in b) are all even. Thus either is a perfect sqaure as well.

Could you explain this to me?
So \$\displaystyle p^2|a\$ which means there is an integer h such that \$\displaystyle a=p^2 * h\$

So the power of the prime is 2 but what about h?
• Oct 2nd 2009, 06:54 AM
aman_cc
Quote:

Originally Posted by dlbsd
Could you explain this to me?
So \$\displaystyle p^2|a\$ which means there is an integer h such that \$\displaystyle a=p^2 * h\$

So the power of the prime is 2 but what about h?

This is wrong, please see post below from BingK

The proof is valid for any p. So in your specific question -
case 1: h is prime - then be same logic you can show \$\displaystyle h^2|a\$. But as that is not the case hence h can't be prime.
so h is composite - then also if q is a prime such that \$\displaystyle q|h\$ then you can show that \$\displaystyle q^2|a\$. Infact h itself is a perfect sqaure - as it should be

The idea of the proof is that for "any" prime ,\$\displaystyle p\$, which divides \$\displaystyle a\$, \$\displaystyle p^2\$ also divides a. So in the prime- factorization of a all the powers will be even.
Logic for a can be replicated for b. Thus the statement will be true for ab as well. If all powers of prime are even then the number is a perfect square. Using this fact we conclude ab is a perfect square.

Hope it helps.
• Oct 3rd 2009, 06:28 AM
Bingk
I think there's a bit of a problem with your logic that if \$\displaystyle p^2|a\$ then all the powers in the prime factorization of \$\displaystyle a\$ will be even. If you think about it \$\displaystyle p^2|p^3\$, and \$\displaystyle 3\$ is not even ...

But if you use Taluivren's hint, you can take the prime decomposition of \$\displaystyle ab\$, and all the powers have to be even. Since \$\displaystyle (a,b)=1\$, we can rearrange the prime decomposition of \$\displaystyle ab\$ so it is written as the prime decomposition of \$\displaystyle a\$ multiplied by the prime decomposition of \$\displaystyle b\$. Then, we look at the respective prime decompositions and notice that the powers are all even. Again, by the hint, we have that \$\displaystyle a\$ and \$\displaystyle b\$ are also perfect squares.
• Oct 3rd 2009, 07:16 AM
aman_cc
Quote:

Originally Posted by Bingk
I think there's a bit of a problem with your logic that if \$\displaystyle p^2|a\$ then all the powers in the prime factorization of \$\displaystyle a\$ will be even. If you think about it \$\displaystyle p^2|p^3\$, and \$\displaystyle 3\$ is not even ...

But if you use Taluivren's hint, you can take the prime decomposition of \$\displaystyle ab\$, and all the powers have to be even. Since \$\displaystyle (a,b)=1\$, we can rearrange the prime decomposition of \$\displaystyle ab\$ so it is written as the prime decomposition of \$\displaystyle a\$ multiplied by the prime decomposition of \$\displaystyle b\$. Then, we look at the respective prime decompositions and notice that the powers are all even. Again, by the hint, we have that \$\displaystyle a\$ and \$\displaystyle b\$ are also perfect squares.

@Bingk - I get what you are saying. Yes - it is incorrect. Thanks for pointing that out.