# 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 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 possible denominators $\,\rm d\,$ for $\,\rm r, \,$ i.e. $\,\rm D = \{ d\in\mathbb Z \,:\: dr \in \mathbb Z\}$. Notice $\,\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\$ by $\rm\ (dr)r = dn\in\mathbb Z, \,$ by $\,\rm r^2 = n\in\mathbb Z.\,$ Thus by the Lemma below, with $\,\rm d =$ least positive element in $\rm D,\,$ we infer that $\ \rm d\mid dr, \$ i.e. $\rm\ r = (dr)/d \in\mathbb Z.\ \$ 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 proof of the theorem 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.

Try to write out the factorization of the right and left handed sides.

Now compare the order of the 3 on the left and right side, one of them is equal, forcing the other side to become odd. Contradiction.

• Considering the high quality of the other answers, this adds very little to the discussion. – Mike Pierce Jun 4 '15 at 0:13