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

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.

-

– Gone 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? – Gone 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. – Gone Aug 21 '10 at 3:14

## 5 Answers

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

6
@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. – Gone 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. – Gone 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?

-

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$. – Gone 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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 85, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9458761811256409, "perplexity_flag": "head"}