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.

This is a problem from "Introduction to Mathematics - Algebra and Number Systems" (specifically, exercise set 2 #9), which is one of my math texts. Please note that this isn't homework, but I would still appreciate hints rather than a complete answer.

The problem reads as follows:

If 3p2 = q2, where $p,q \in \mathbb{Z}$, show that 3 is a common divisor of p and q.

I am able to show that 3 divides q, simply by rearranging for p2 and showing that

$$p^2 \in \mathbb{Z} \Rightarrow q^2/3 \in \mathbb{Z} \Rightarrow 3|q$$

However, I'm not sure how to show that 3 divides p.


Edit:

Moron left a comment below in which I was prompted to apply the solution to this question as a proof of $\sqrt{3}$'s irrationality. Here's what I came up with...

[incorrect solution...]

...is this correct?

Edit:

The correct solution is provided in the comments below by Bill Dubuque.

share|improve this question
    
No, the inference that $p = \sqrt{3}$ is not correct. Instead, assume at the start that $q/p$ is reduced, i.e. ${\rm gcd}(p,q)=1$ then your proof that $3|p,q$ yields a contradiction. For a simple proof for any $\sqrt{n}$ see my post mathoverflow.net/questions/32017 –  Bill Dubuque Aug 21 '10 at 2:19
    
@Bill: Can you explain why that inference isn't correct? –  Cam Aug 21 '10 at 2:21
    
How did you go from the 2nd last equation to the last? –  Bill Dubuque Aug 21 '10 at 2:33
    
@Bill: By making silly mistake :) - thanks for offering the correct solution. –  Cam Aug 21 '10 at 2:41
    
Alternatively you could assume $p$ minimal at the start, then canceling 3 from $p$ and $q$ yields $\sqrt{3} = \frac{q/3}{p/3}$ contra minimality of $p$. There are many variations - see the references in my post linked above. –  Bill Dubuque Aug 21 '10 at 3:14

5 Answers 5

up vote 6 down vote accepted

Write $q$ as $3r$ and see what happens.

share|improve this answer
    
Then it's the same problem as before, but with the variables switched - thanks :) –  Cam Aug 20 '10 at 21:20
7  
@Cam: Exactly. Do you see how that helps you prove that $\sqrt{3}$ is irrational? –  Aryabhata Aug 20 '10 at 21:24
    
I think so. I've edited my question in response (the character limit for comments is too high). Is my solution correct? –  Cam Aug 21 '10 at 1:25

Below is a conceptual proof of the irrationality of square-roots. It shows that this result follows immediately from unique fractionization -- the uniqueness of the denominator of any reduced fraction -- i.e. the least denominator divides every denominator. This in turn follows from the key fact that the set of all possible denominators of a fraction is closed under subtraction so comprises an ideal of $\,\mathbb Z,\,$ necessarily principal, since $\,\mathbb Z\,$ is a $\rm PID$. But we can easily eliminate this highbrow language to obtain the following conceptual high-school level proof:

Theorem $\ $ Let $\;\rm n\in\mathbb N.\;$ Then $\;\rm r = \sqrt{n}\;$ is integral if rational.

Proof $\ $ Consider the set $\rm D$ of all the possible denominators $\rm d$ for $\rm r, \;$ i.e. $\;\rm D = \{\, d\in\mathbb Z \;:\: dr \in \mathbb Z\,\}$. Note $\rm D$ is closed under subtraction: $\rm\, d,e \in D\, \Rightarrow\, dr,\,er\in\mathbb Z \,\Rightarrow\, (d-e)\:r = dr - er \in\mathbb Z.\;$ Further $\rm d\in D \,\Rightarrow\, dr\in D\,$ since $\rm\, (dr)r = dn\in\mathbb Z \;$ by $\;\rm r^2 = n\in\mathbb Z.\;$ Therefore, invoking the Lemma below, with $\rm d $ the least positive element in $\rm D,$ we infer that $\;\rm d\,|\,dr \;$ in $\mathbb Z,\;$ i.e. $\rm\ r = (dr)/d \in\mathbb Z.\quad$ QED

Lemma $\ $ Suppose $\;\rm D\subset\mathbb Z \;$ is closed under subtraction and that $\rm D$ contains a nonzero element.
Then $\rm D \:$ has a positive element and the least positive element of $\rm D$ divides every element of $\rm D\:$.

Proof $\rm\,\ \ 0 \ne d\in D \,\Rightarrow\, d-d = 0\in D\,\Rightarrow\, 0-d = -d\in D.\, $ Hence $\rm D$ contains a positive element. Let $\rm d$ be the least positive element in $\rm D$. Since $\rm\: d\,|\,n \!\iff\! d\,|\,{-}n,\,$ if $\rm\, c\in D$ is not divisible by $\rm d$ then we may assume that $\rm c$ is positive, and the least such element. But $\rm\, c-d\,$ is a positive element of $\rm D$ not divisible by $\rm d$ and smaller than $\rm c$, contra leastness of $\rm c$. So $\rm d$ divides every element of $\rm D.\ $ QED

The theorem's proof exploits the fact that the denominator ideal $\rm D$ has the special property that it is closed under multiplication by $\rm\: r\:.\ $ The fundamental role that this property plays becomes clearer when one learns about Dedekind's notion of a conductor ideal. Employing such yields a trivial one-line proof of the generalization that a Dedekind domain is integrally closed since conductor ideals are invertible so cancellable. This viewpoint serves to generalize and unify all of the ad-hoc proofs of this class of results - esp. those proofs that proceed essentially by descent on denominators. This conductor-based structural viewpoint is not as well known as it should be - e.g. even some famous number theorists have overlooked this. See my post here for further details.

share|improve this answer

Moron's answer certainly covers your question, but as someone who's not your instructor I'd like to see a few more details in your 'proof' of the first half - can you be more specific about how $q^2/3 \in \mathbb{Z} \Rightarrow 3|q$? While that's easy, it's not necessarily trivial, and you've elided some details there...

share|improve this answer
    
Assume 3 does not divide $q$. Then 3 does not divide $q^2$, so $\frac{q^2}{3}$ is not an integer. But this is a contradiction, because by arranging for $p^2$ we see that $p^2=\frac{q^2}{3}$ and $p^2 \in \mathbb{Z}$ so it follows that $\frac{q^2}{3} \in \mathbb{Z}$. Therefore $3|q$. –  Cam Aug 21 '10 at 2:54
    
@Cam: That doesn't answer Steven's query. You need to prove that $3|q^2 \Rightarrow 3|q$. For one simple way see my comment to Katie's post here. –  Bill Dubuque Aug 21 '10 at 3:21
    
@Bill: What about: if $3|q^2$ then 3 is a prime factor of $q^2$, so 3 must be a prime factor of $q$, and therefore $3|q$? Otherwise put, it would be impossible for 3 to be a factor of $q^2$ unless it was a factor of $q$ as well, because 3 is prime. –  Cam Aug 21 '10 at 15:04
    
That works but it implictly assumes a very powerful result - that integers have unique factorization. For a simpler way see my comment to Katie's post. See also my proof here of the general result based upon unique fractionization. –  Bill Dubuque Aug 21 '10 at 15:40

Think about how many times each prime factor must appear on each side of the equation, if you were to break p and q into their prime factorizations. The left side has a 3 in it, how many must the right side have, at least?

share|improve this answer
2  
But using unique factorization is a bit of a sledgehammer. Instead one need only note that $x^2 = 0 \Rightarrow x=0 \pmod 3$ since $x\ne 0 \Rightarrow x = \pm 1 \Rightarrow x^2 = 1 \pmod 3$. –  Bill Dubuque Aug 20 '10 at 21:56

Here we go. $3p^2=q^2$ implies that $3$ divides $q$, since $3$ is prime and if a prime divides a product, it divides one of the factors. But then, if $3$ divides $q$, then we also have that $3^2$ divides $q^2$. Hence, by factoring out the 9 on the rhs, we can cancle the 3 on the left hand side and still be left with a three. i.e $3\alpha=p^2$. But then, $3$ divides p, as required.

share|improve this answer

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.