0
$\begingroup$

Let $a$, $b$ be two positive integers. Prove that $a$ and $b$ are both perfect squares if and only if both $\gcd(a,b)$ and $\operatorname{lcm}(a,b)$ are perfect squares.

I believe the proof is based in prime factorization, as if $a$ is a perfect square, then $a = (p_1^{a_1}\cdot\ldots\cdot p_n^{a_n})^2$, and the same goes for the gcd and lcm when they are perfect squares. I'm just a little lost on how to connect the dots and prove both directions.

$\endgroup$
1
  • 1
    $\begingroup$ You are in the right track: any prime number in the gcd will appear squared because $\min (2a_j,2b_j) = 2\min (a_j,b_j)$. Same idea applies for the lcm $\endgroup$ – FormerMath Mar 1 at 21:26
0
$\begingroup$

The crux of the matter is: $m$ and $n$ are both even if and only if both $\min(m, n)$ and $\max(m,n)$ are both even.

(That's obvious, isn't it. If they are both even then the min and the max are one or the other of them and will have to be even. And if the min and max are both even, each one is either the min or the max and the other will be the other extreme and they will both be even.

===

Let $\{p_i\}$ be all the prime factors of either $a$ or $b$.

We can write $a = \prod p_i^{m_i}$. If it turns out that $p_k\not \mid a$ but $p_k\mid b$ this will be okay if we assume we can let $m_k = 0$. And we can write $b = \prod p_i ^{n_i}$ (same caveat.)

Now $G=\gcd(a,b) = \prod p_i^{\min(m_i,n_i)}$ and $L=\operatorname{lcm}=\prod p_i^{\max(m_i,n_1)}$.

Now any one of those is a perfect square if and only if all the powers are even (and $0$ is an even number and $1$ is a perfect square so any concerns we have about what if $p_k$ divides one but not the other are addresses).

So.....

If $a$ and $b$ are both perfect squares then $m_i, n_i$ will all be even so $\min(m_i, n_i)$ and $\max(m_i, n_i)$ will all be even. So $G=\gcd(a,b)$ and $L =\operatorname{lcm}(a,b)$ will both be perfect squares.

And if $G=\gcd(a,b)$ and $L =\operatorname{lcm}(a,b)$ are both perfect squares then $\min(m_i, n_i)$ and $\max(m_i,n_i)$ are all even. SO all $m_i, n_i$ are even, so $a$ and $b$ are both perfect squares.

We can even argue further (although we don't have to-- we are totally done!) that if either $a$ or $b$ aren't both perfect squares there will be at least one $m_i$ or at least one $n_i$ that is odd and that is true if and only if at least one $\max(m_i,n_i)$ or one $\min(m_i,n_i)$ that is odd, so at least one of $G=\gcd(a,b)$ and $L =\operatorname{lcm}(a,b)$ are not a perfect square.

======

The crux of the matter is: $m$ and $n$ are both even if and only if both $\min(m, n)$ and $\max(m,n)$ are both even.

$\endgroup$
1
  • $\begingroup$ This makes a lot of sense! Thank you $\endgroup$ – KMehta Mar 1 at 22:30
0
$\begingroup$

Hint: For any given prime $p$, let the exponent of $p$ in the prime factorization of $a$ be $a_p$ and let the exponent of $p$ in the prime factorization of $b$ be $b_p$ (where $0$ is allowed as an exponent in both cases). In terms of $a_p$ and $b_p$, what are the exponents of $p$ in $\operatorname{lcm}(a, b)$ and in $\gcd(a, b)$ respectively?

$\endgroup$
0
$\begingroup$

\begin{align} \gcd(a,b) &= m^2 \tag{A} \\ \operatorname{lcm}(a,b) &= n^2 \tag{B} \end{align}

Let $p_i$ represent the $i^{\text{th}}$ prime number.

Then we can say

$a = \prod p_i^{\alpha_i}$ where all but a finite number of the $\alpha_i$ are non-zero.

$b = \prod p_i^{\beta_i}$ where all but a finite number of the $\beta_i$ are non-zero.

Then (A) implies $\min(\alpha_i, \beta_i)$ is even for all $i$ and (B) implies $\max(\alpha_i, \beta_i)$ is even for all $i$

It follows that $\alpha_i$ and $\beta_i$ are both even for all $i$; that is to say, $a$ and $b$ are perfect squares.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.