# Show that $3p^2=q^2$ implies $3|p$ and $3|q$

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.

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.

-
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

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

-
Then it's the same problem as before, but with the variables switched - thanks :) –  Cam Aug 20 '10 at 21:20
@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.

-

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...

-
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?

-
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.

-