2
$\begingroup$

Problem:

If $\gcd(a, b) = 1$ and If $ab = x^2$ ,prove that $a$, $b$ must also be perfect squares; where $a$,$b$,$x$ are in the set of natural numbers

I've come to the conclusion that $a \ne b$ and $a \ne x$ and $b \ne x$ but I guess that won't really help me.. I understand that if the $\gcd$ between two numbers if $1$ then they obviously have no common divisors but where do I go from this point?

Any tips at tackling this would be great. It looks quite easy though I'm still trying to get my hand around these proofs! Any pointers in the right direction would be great.

Thank you in advance,

$\endgroup$
  • $\begingroup$ You just wrote "$b\ne b$." I really hope that's not what you meant. $\endgroup$ – apnorton Feb 14 '14 at 3:51
  • 1
    $\begingroup$ I've noticed that you have asked quite a few questions recently. I wanted to make sure that you are aware of the quotas 50 questions/30 days and 6 questions/24 hours, so that you can plan posting your questions accordingly. (If you try to post more questions, stackexchange software will not allow you to do so.) For more details see meta. $\endgroup$ – user61527 Feb 14 '14 at 3:52
  • $\begingroup$ Hi Tyler! I really appreciate the heads up. I'm working away at an assignment right now. I've gotten most of the problems down but I still have only a few left. Thanks so much again! $\endgroup$ – A A Feb 14 '14 at 4:08
3
$\begingroup$

Fundamental theorem of arithmetic says that every number has a unique prime factorization.

If gcd(a,b) = 1, then all of these factors are unique (no prime factor is shared between a and b). What does this say about $x^2$?

Hint 2:

Let $a_i$ be a prime factor of a and $b_i$ be a factor of b. Then,

$$ab = \prod {a_{i}^{m_i}}\prod {b_{i}^{n_i}}$$

But $x$ has to have a unique factorization in the form,

$$ x = \prod {x_{i}^{e_i}} $$, where $m, n, e$ are integer exponents. Keep in mind it is unique and we can order these factors in any way we please. What does this say about $x^2$ compared to $ab$?

$\endgroup$
  • $\begingroup$ Hmm, x^2 must then: 1) have unique prime factors $\endgroup$ – A A Feb 14 '14 at 4:14
  • $\begingroup$ I'll edit my post with another hint. $\endgroup$ – Chantry Cargill Feb 14 '14 at 4:17
  • $\begingroup$ I think I may have it: x^2 = (p1^ip2^i2...pn^i2)^2 = (p1^2i2*p2^2i3*...pn^2in) = ab a and b must be factors of x^2, and all the factors of x^2 are squares, therfore a and b must be squares. Hmm, Does this sound correct to you? $\endgroup$ – A A Feb 14 '14 at 4:54
  • 1
    $\begingroup$ Yes, more or less! Just make sure that it's clear that you can order the factors of $x^2$ such that the primes match up with a and b. Then the root will just be ab. $\endgroup$ – Chantry Cargill Feb 14 '14 at 5:11
4
$\begingroup$

Below is an approach employing universal gcd laws (associative, commutative, distributive), some of which you may need to (simply) prove before you can use this method. But once you do so, you will gain great power. Below we explicitly show that $\rm\:a,b\:$ are squares by taking gcds. Namely

Lemma $\rm\ \ \color{#0a0}{(a,b,c) = 1},\,\ \color{#c00}{c^2 = ab}\ \Rightarrow\ a = (a,c)^2,\,\ b = (b,c)^2\ $ for $\rm\:a,b,c\in \mathbb N$

Proof $\rm\ \ (c,b)^2 = (\color{#c00}{c^2},b^2,bc) = (\color{#c00}{ab},b^2,bc) = b\color{#0a0}{(a,b,c)} = b.\ $ Similarly for $\,\rm(c,a)^2.\ \ $ QED

Yours is the special case $\rm\:(a,b) = 1\ (\Rightarrow\ (a,b,c) = 1)$.

Generally $\rm\: \color{#c00}{ab = cd}\: \Rightarrow\: (a,c)(a,d) = (aa,\color{#c00}{cd},ac,ad) = a\: (a,\color{#c00}b,c,d) = a\:$ if $\rm\:(a,b,c,d) = 1.\:$ For more on this and closely related topics such as Euler's four number theorem (Vierzahlensatz), Riesz interpolation, or Schreier refinement see this post and this post.


Compare the following Bezout-based proof (this is a simplified form of the proof in Rob's answer). For comparison, I append an ideal-theoretic version of the proof of the more complex direction.

Note that $\ 1=\overbrace{a{\rm u}+b\,{\rm v}}^{\large (a,b)}\,\ \overset{\large \times\,a}\Rightarrow\ a = \color{#c00}{a^2}{\rm u}+\!\!\overbrace{ab}^{\Large\ \ \color{#c00}{c^2}}{\rm v} \ \,$ so $\,\ d=(a,c)\mid a,c\,\Rightarrow\, d^2\!\mid \color{#c00}{a^2,c^2}\,\Rightarrow\, d^2\!\mid a$

Conversely $\ d = (a,c)= au+cv\,\ \Rightarrow\,\ d^2=\,\color{#c00}{a^2}u^2+2\color{#c00}acuv+\color{#c00}{c^2}v^2\ \ $ thus $\ \ \color{#c00}{a\mid c^2}\ \Rightarrow\,\ \color{#c00}a\mid d^2$

$\quad\ \ {\rm i.e.}\quad (d)= (a,c)\ \ \Rightarrow\ \ (d^2) \subseteq\, (a,c^2)\,\subseteq\, (a)\ \ $ by $\ \ a\mid c^2\,\ \ $ [simpler ideal form of prior]

Notice how the ideal version eliminates the obfuscatory Bezout coefficients $\,u,v$.

$\endgroup$
  • $\begingroup$ Hi Bill! Thank you for the response! Your way ahead of me, I'm not too familiar with the notation used/ $\endgroup$ – A A Feb 14 '14 at 4:53
  • 1
    $\begingroup$ Bezouted.$\ \ $ $\endgroup$ – robjohn Feb 14 '14 at 10:16
  • $\begingroup$ @AA I use the standard notation $\ (a,b,\,\ldots)\, =\, \gcd(a,b,\,\ldots).\,$ I added another Bezout-based proof. $\ $ $\endgroup$ – Bill Dubuque Feb 15 '14 at 4:50
3
$\begingroup$

Here is a proof using Bezout's Identity.

Let $x^2=ab$ and $\gcd(a,b)=1$, where $a,b\gt0$.

There are $u,v$ so that $$ au+bv=1\tag{1} $$ Let $s_a=\gcd(x,a)$. Rewriting $(1)$, we have $$ \begin{align} s_a\left(\dfrac{a}{s_a}\right)u+bv=1 &\implies s_a^2\left(\dfrac{a}{s_a}\right)^2u^2=1-b(2v-bv^2)\tag{2}\\ &\implies s_a^2\left(\dfrac{a}{s_a}\right)^2u^2a+ab(2v-bv^2)=a\tag{3}\\ &\implies s_a^2\left(\dfrac{a}{s_a}\right)^2u^2a+s_a^2\left(\dfrac{x}{s_a}\right)^2(2v-bv^2)=a\tag{4}\\[8pt] &\implies s_a^2\mid a\tag{5} \end{align} $$ Justification:
$(2)$: Move $bv$ to the right side and square
$(3)$: Move $b(2v-bv^2)$ to the left side and multiply by $a$
$(4)$: $x^2=ab$
$(5)$: $s_a^2$ divides each term on the left side

There are $u_a,v_a$ so that $$ \begin{align} xu_a+av_a=s_a &\implies\frac{x}{s_a}u_a+\frac{a}{s_a}v_a=1\tag{6}\\ &\implies\frac{x^2}{s_a^2}u_a^2=1-\frac{a}{s_a}\left(2v_a-\frac{a}{s_a}v_a^2\right)\tag{7}\\ &\implies\frac{ab}{s_a^2}u_a^2+\frac{a}{s_a}\left(2v_a-\frac{a}{s_a}v_a^2\right)=1\tag{8}\\ &\implies abu_a^2+as_a\left(2v_a-\frac{a}{s_a}v_a^2\right)=s_a^2\tag{9}\\[7pt] &\implies a\mid s_a^2\tag{10} \end{align} $$ Justification:
$\ \:(6)$: Divide by $s_a$
$\ \:(7)$: Move $\frac{a}{s_a}v_a$ to the right side and square
$\ \:(8)$: Move $\frac{a}{s_a}\left(2v_a-\frac{a}{s_a}v_a^2\right)$ to the left side, $x^2=ab$
$\ \:(9)$: Multiply by $s_a^2$
$(10)$: $a$ divides each term on the left side

Combining $(5)$ and $(10)$ yields $a=\gcd(x,a)^2$. Symmetry yields, $b=\gcd(x,b)^2$.

$\endgroup$
  • $\begingroup$ I simplified it a bit - see my answer. In $\,(2\!-\!5)\,$ it suffices to use the Bezout identity itself (vs. its square). In $(6\!-\!10)$ it's simpler to immediately square the Bezout identity (vs. rearrange it first). $\endgroup$ – Bill Dubuque Feb 15 '14 at 4:47

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.