6
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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 $\endgroup$
    – Bill Dubuque
    Commented Aug 21, 2010 at 2:19
  • $\begingroup$ @Bill: Can you explain why that inference isn't correct? $\endgroup$
    – Cam
    Commented Aug 21, 2010 at 2:21
  • $\begingroup$ How did you go from the 2nd last equation to the last? $\endgroup$
    – Bill Dubuque
    Commented Aug 21, 2010 at 2:33
  • $\begingroup$ @Bill: By making silly mistake :) - thanks for offering the correct solution. $\endgroup$
    – Cam
    Commented Aug 21, 2010 at 2:41
  • $\begingroup$ 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. $\endgroup$
    – Bill Dubuque
    Commented Aug 21, 2010 at 3:14

7 Answers 7

Reset to default
6
$\begingroup$

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$. We can eliminate this highbrow language to obtain the following conceptual proof at high-school level.

Theorem $\ $ Let $\;\rm n\in\mathbb N.\;$ Then $\;\rm r = \sqrt{n}\;$ is $\rm\color{#90f}{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\}$. Note $\,\rm D\,$ is $\rm\color{#0a0}{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\, \color{#c00}{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 natural in $\rm D,\,$ we infer that $\ \rm d\mid \color{#c00}{dr}, \ $ i.e. $\rm\ \color{#90f}{r = (dr)/d \in\Bbb Z}.\ $ QED

Lemma $\ $ Suppose $\,\rm D\subset\mathbb Z \,$ is $\rm\color{#0a0}{closed\ under\ subtraction}$ and $\,\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,\, $ so $\rm D$ contains a positive integer. Let $\,\rm d\,$ be the least positive integer in $\,\rm D.\,$ Since $\rm\: d\mid n \!\iff\! d\mid{-}n,\,$ if $\rm\ c\in D\,$ is $\rm\color{#90f}{not}$ divisible by $\,\rm d\,$ then we may assume $\,\rm c\,$ is positive, and the least such. Then $\rm\, c-d > 0 \,$ is in $\rm D,\,$ $\rm\color{#90f}{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 $\rm\color{#c00}{closed}$ under multiplication by $\rm\,\color{#c00}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.

$\endgroup$
5
$\begingroup$

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

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

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

$\endgroup$
4
  • $\begingroup$ 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$. $\endgroup$
    – Cam
    Commented Aug 21, 2010 at 2:54
  • $\begingroup$ @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. $\endgroup$
    – Bill Dubuque
    Commented Aug 21, 2010 at 3:21
  • $\begingroup$ @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. $\endgroup$
    – Cam
    Commented Aug 21, 2010 at 15:04
  • $\begingroup$ 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. $\endgroup$
    – Bill Dubuque
    Commented Aug 21, 2010 at 15:40
2
$\begingroup$

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?

$\endgroup$
1
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Bill Dubuque
    Commented Aug 20, 2010 at 21:56
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Considering the high quality of the other answers, this adds very little to the discussion. $\endgroup$
    – Mike Pierce
    Commented Jun 4, 2015 at 0:13
0
$\begingroup$

Does not exist $p,q$ integers such that $3q^2=p^2$ because $v_3{3q^2}=odd$ but $v_3{p^2}=even$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .