Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $a$ and $b$ be positive integers. Prove that: If $a^2$ divides $b^2$, then $a$ divides $b$.

Context: the lecturer wrote this up in my notes without proving it, but I can't seem to figure out why it's true. Would appreciate a solution.

share|improve this question
3  
Do you have the fundamental theorem of arithmetic at your disposal? –  yunone Aug 15 '12 at 20:18
    
Yep! We covered that a couple weeks ago. –  confused Aug 15 '12 at 20:20
2  
Hint: if $a^2|b^2$ then $b^2=?$ and $?$ is a perfect square so ... –  Mark Bennet Aug 15 '12 at 20:22
3  
Hint: If $b^2 = k a^2$ then using FTA what can you say about $k$? Perfect square. Why? Something about the even powers of primes. –  user2468 Aug 15 '12 at 20:25
1  
There are many prior answers on the irrationality of square roots, e.g. see here and here and here. –  Bill Dubuque Aug 15 '12 at 21:53
show 6 more comments

5 Answers

up vote 40 down vote accepted

By the fundamental theorem of arithemtic, you can write $a$ and $b$ as a product of primes, say $$ a=p_1^{\alpha_1}\cdots p_r^{\alpha_r},\qquad b=p_1^{\beta_1}\cdots p_r^{\beta_r} $$ where $\alpha_i,\beta_i\geq 0$. Allow the exponents to possibly be $0$ if such a prime $p_i$ occurs in the factorization of one integer but not the other.

So $a^2=p_1^{2\alpha_1}\cdots p_r^{2\alpha_r}$ and $b^2=p_1^{2\beta_1}\cdots p_r^{2\beta_r}$. Since $a^2\mid b^2$, by unique factorization, necessarily $2\alpha_i\leq 2\beta_i$ for each $i$. That implies $\alpha_i\leq\beta_i$ for all $i$, and so $a\mid b$.

share|improve this answer
    
Thanks very much! Took me a while just to work through and understand that proof (a little embarrassing). –  confused Aug 15 '12 at 20:38
4  
@Anthony Glad to help, and welcome to math.se. By the way, if an answer suits you, you can accept it by clicking the checkmark to the left. This essentially marks the question as "done," but feel free to wait a while as other, and better, answers may come along later. –  yunone Aug 15 '12 at 20:41
    
This method actually proves that $a^n \mid b^n \implies a \mid b$ for any $n \geq 1$ as I showed here. –  JavaMan Jan 15 '13 at 5:41
    
I don't understand why 2αi≤2βi, and that too "necessarily". –  slider Jan 27 at 1:03
    
Is it necessary that the prime factorisation of $a$ and $b$...will have equal number of primes and the same primes? $b$ can have more primes than $a$... –  Hawk Apr 8 at 7:05
add comment

To say that $a^2$ divides $b^2$ is to say that $n=b^2/a^2 = (b/a)^2$ is an integer. Now integers only have square roots which are integers or irrational. Since $b/a$ is rational, it must be an integer, which is to say that $a$ divides $b$.

share|improve this answer
    
Thanks! Very cool. –  confused Aug 15 '12 at 20:51
9  
Hmm... if I wanted to prove that the square root of an integer was either an integer or irrational, I'd probably do it by proving the OP's statement, making this circular. Do you have a different proof in mind? –  Micah Aug 15 '12 at 21:55
    
@Micah see Bill's comment. –  user2468 Aug 15 '12 at 22:19
    
+1. Really very simple proof, that makes no appeal to the Funda-Theorem of Arithmetic. –  Iyengar Aug 16 '12 at 13:27
1  
@Iyengar, the standard proof that integers only have square roots that are integers or irrational, that proof uses the Fundamental Theorem. –  Gerry Myerson Aug 16 '12 at 23:40
add comment

Call a positive integer $y$ bad if for some positive $x$, we have $x^2\mid y^2$ but $x \nmid y$.

If there are bad positive integers, there is a smallest bad one, say $b$. Since $b$ is bad, there is a positive integer $a$ such that $a^2 \mid b^2$ but $a \nmid b$.

It is clear that $a \ne 1$. So some prime $p$ divides $a^2$. But if a prime divides the product $cd$, it divides $c$ or $d$ or both. Thus $p\mid a$.

Since $a^2\mid b^2$, we have $p\mid b^2$, and therefore $p\mid b$.

Let $a=pa_1$ and $b=pb_1$. Since $a^2\mid b^2$, we have $(pa_1)^2=q(pb_1)^2$ for some integer $q$, and therefore $a_1^2\mid b_1^2$.

But $a_1\nmid b_1$, since if it does, one can easily show that $a\mid b$.

So we have shown that $b_1$ is bad. It is clear that $b_1\lt b$, which contradicts the supposed minimality of $b$.

We conclude that there are no bad positive integers.

share|improve this answer
    
Remark that this is essentially the same proof as that in yunone's answer (by unique factorization), but rearranged into descent form. –  Bill Dubuque Aug 15 '12 at 22:54
    
@BillDubuque: Agreed. It uses the same key step as the standard proof of the Unique Factorization Theorem. –  André Nicolas Aug 15 '12 at 22:58
add comment

The proofs given use the Unique Factorization Theorem, or the existence of GCDs, or some equivalent, but the result is true even in places where there aren't any GCDs, so there must be a proof that doesn't rely on these properties. Here's one that works in the ring $O_K$ of integers in a number field $K$, whether there are GCDs or not.

If $a,b$ are in $O_K$ and $a^2$ divides $b^2$, then $b^2=a^2c$ for some $c$ in $O_K$. So $\sqrt c=b/a$ is in $K$. But $\sqrt c$ is a zero of $x^2-c$, a monic polynomial with algebraic integer coefficients, so $\sqrt c$ is an algebraic integer, so $\sqrt c$ is in $O_K$, so $a$ divides $b$.

share|improve this answer
    
So, you only need to assume the ring to be integrally closed. –  lhf Aug 16 '12 at 13:29
    
@lhf, yes, that sounds about right. –  Gerry Myerson Aug 16 '12 at 13:40
    
"... but the result is true even in places where there aren't any GCDs." This is incorrect. Let $K$ be a field, and let $R=K[x^2,x^3]=\{a_0 + a_2 x^2 + a_3 x^3 + \cdots + a_n x^n \,\vert\,a_i \in K\}$ be the subring of $K[x]$ that has no linear terms. Then $(x^2)^2 \vert (x^3)^2$, but $x^2\nmid x^3$. –  user5137 Aug 16 '12 at 17:05
    
@Jack, sorry, I thought it would be clear that I was saying that the result is true even in some places where there aren't any GCDs. Thanks for providing an example of a ring where the result fails. –  Gerry Myerson Aug 16 '12 at 23:34
add comment

Here's an alternative proof only relying on a more general definition of greatest common divisors (in commutative monoids or commutative rings). In particular, we say that $gcd(a,b)=d$ if:

  • $d$ is a common divisor of $a$ and $b$ (ie $d\vert a$ and $d \vert b$), and
  • Given any other common divisor $d'$ of $a$ and $b$, we have $d'\vert d$

Throughout this proof, we'll assume that we're in a commutative monoid for which every pair of elements has a greatest common divisor (or, if you'd prefer, you can imagine just sticking to $\mathbb{N}$ under multiplication).

So, suppose that $a^2 \vert b^2$, and let $gcd(a,b)=d$. Then, we have $d\alpha =a$ and $d\beta = b$ for some $\alpha,\beta$. It then follows that $gcd(\alpha,\beta)=1$ (if you're unsure as to why, it would be worth the time to write down a proof using the definition of GCD given above).

Now, since $a^2 \vert b^2$, there exists $k$ such that $a^2 k = b^2$, and hence $\alpha^2 k = \beta^2$. Therefore we have $\alpha \vert \beta^2$ implying that $\alpha \vert \beta$ (if you're not sure as to why, again, it would be worth writing down a proof). However, $gcd(\alpha,\beta)=1$ and $\alpha \vert \beta$ implies that $\alpha=1$ (or, more generally, $\alpha$ is an invertible element in our monoid), hence $gcd(a,b)=a$ and $a \vert b$.

In fact, this same line of argument shows that if $a^m \vert b^m$ for some $m\geq 2$, then $a \vert b$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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