2
$\begingroup$

I am currently trying to self-study Stephen Abbott's Understanding Analysis. The first exercise asks to prove the irrationality of √3, and I understand the general idea of the contradiction by finding that the relatively prime integers p and q have a common factor. However, I am stuck on the idea that if p^2 is divisible by 3, then p is divisible by 3. Abbott's solution assumes this, but I have also seen proofs that analyze the situations where a and b are even or odd (such as NASA's). Even or odd really is just saying multiple of 2, which confuses me as to why the even/odd method (which is much less concise) would be used.

Sorry for the block of rambling text, I just want to start writing proofs the right way. I guess my real questions are:

If p^2 is divisible by a prime number, is p also divisible by that prime number? Can this just be assumed, or is there a theorem I have to mention in the proof? Why do some proofs analyze the even/odd situations of a and b? Are they more rigorous, and if they are not, why are they used, considering their added length and complexity? Finally, am I simply over thinking the idea of being rigorous and missing the big picture?

$\endgroup$
  • $\begingroup$ even/odd (that is, divisibility by $2$) is used to show $\sqrt{2}$ is irrational. But for $\sqrt{3}$ we consider divisibility by $3$ instead. $\endgroup$ – GEdgar Jun 3 '15 at 0:25
  • 1
    $\begingroup$ If $p^2$ divides a prime, so does $p$. This is a theorem. $\endgroup$ – Akiva Weinberger Jun 3 '15 at 0:26
  • 2
    $\begingroup$ Don't confuse "divides" with "divisible by" $\endgroup$ – GEdgar Jun 3 '15 at 0:28
  • 2
    $\begingroup$ In case it wasn't clear what @ GEdgar's comment is in reference to, it is to @columbus's comment. It should read "if $ab$ is divisible by a prime, $p$, then either $a$ is divisible by $p$ or $b$ is divisible by $p$." Indeed, this is the definition of a prime element in a ring. The definition that says "a prime cannot be expressed as a product of two non-unit integers" is rather the definition of an irreducible element (which happens to be the same as prime for integers). $\endgroup$ – JMoravitz Jun 3 '15 at 0:42
  • 2
    $\begingroup$ "What is the most rigorous proof of..." How does one compare the degrees of rigor of proofs? $\endgroup$ – Did Jun 3 '15 at 6:02
0
$\begingroup$

personally I prefer to prove these results by contrapositive. If $p,q$ are coprime positive integers with $q>1$ then $$ p^{k}/q^{k} $$ is not an integer for any $k>0.$ This immediately implies the irrationality of all roots of $3.$ In fact, it proves that any root of an integer that is not an integer is irrational.

The key is, as everyone has already said, is that $p,q$ coprime implies that $p^{k}$ and $q^k$ are also coprime, and so $p^k/q^k$ is not an integer.

This is implied by that if a prime $m$ divides $ab$ then it divides $a$ or $b.$ So if it divides $p^k$ it divides $p$ and if it divides $q^k$ it divides $q.$ So no prime will divide both of them unless it divides $p$ and $q$ which we ruled out.

How do we prove the result that $m$ must divide $a$ or $b$? Either it divides $a$ and we are done or $m$ and $a$ are co-prime since $m$ is prime. We then have that there exist $\alpha $ and $\beta$ such that $$ \alpha m + \beta a =1. $$ (this follows from the Euclidean algorithm.) So $$ b\alpha m + \beta ab =b $$ Since $m$ divides $ab$ it divides the LHS, so it divides the RHS too.

(See my book "proof patterns" for more discussion.)

$\endgroup$
  • $\begingroup$ Could you explain why the irrationality of all roots of 3 is immediately implied? $\endgroup$ – Bryan Jun 3 '15 at 22:51
  • $\begingroup$ I think I get it now. For example, if we let k be 2, and there is no (p/q)^k that is an integer, and since 3 is an integer, then the sqrt of 3 has no rational solution. Since k can be any real number, all roots of 3 are irrational. Is this the general idea? $\endgroup$ – Bryan Jun 3 '15 at 22:58
  • $\begingroup$ yes that's right and we get for example that the square root of 12 is irrational which is trickier by the other method. $\endgroup$ – Mark Joshi Jun 4 '15 at 1:09
3
$\begingroup$

If a product $ab$ is divisible by a prime $p$, then at least one of the factors is divisible by $p$. If you do not already know this (and Abbott has not proved it prior to this point of the book), then you may need to go back to a more elementary book for its proof.

added
Euclid, Book VII, Propsition 30

$\endgroup$
  • $\begingroup$ This is what I was looking for. I was not aware of this theorem. Do you know its exact name? $\endgroup$ – Bryan Jun 3 '15 at 0:35
  • $\begingroup$ Thank you! Just for verification, I don't need to state that I used Euclid's Lemma during the proof, correct? $\endgroup$ – Bryan Jun 3 '15 at 0:41
  • $\begingroup$ @Bryan You don't need to invoke the high-powered Euclid's Lemma. Instead, you can do a simple remainder-case analysis just like the parity analysis used for $\,\sqrt 2.\ \ $ $\endgroup$ – Bill Dubuque Jun 3 '15 at 0:44
  • $\begingroup$ Could you elaborate what you mean by remainder-case analysis? $\endgroup$ – Bryan Jun 3 '15 at 0:48
  • $\begingroup$ Never mind, Bernard's proof of the lemma explains it perfectly. $\endgroup$ – Bryan Jun 3 '15 at 0:56
0
$\begingroup$

Suppose that $\sqrt{3}$ is rational and $\sqrt{3}=a/b$ then squaring both sides gives you $3b^{2}=a^{2}$. We can suppose that $a/b$ is reduced (so $a$ and $b$ have no common factors). This means, in particular, that it is not the case that both $a$ and $b$ are even. Note that $n^{2}\equiv 0,1\mod 4$, $n^2\equiv 0\mod 4 $ if $n$ is even and $1$ otherwise. Then, look at $3b^{2}\equiv a^{2}\mod 4$. It is inconsistent. Contradiction.

As for the second (tangent) question: if $p|n^{2}$ where $p$ is a prime, then it is true that $p|n$. Think about the prime factorization of $n^{2}$... $n^{2}=(n)^{2}=(p_1^{k_1}...p_{m}^{k_m})^{2}=p_{1}^{2k_1}...p_{m}^{2k_m}$. So $n$ and $n^2$ have exactly the same prime divisors and knowing how $n$ (or $n^2$) factors tells you how $n^{2}$ (or $n$) factors.

$\endgroup$
0
$\begingroup$

Prompted by the title of the question, FYI here is a sketch of another very nice proof.

If $\sqrt3$ is equal to the fraction $$\frac pq$$ which is a quotient of positive integers, then it is also equal to $$\frac{3q-p}{p-q}\ ,$$ which is a quotient of positive integers with smaller denominator.

$\endgroup$
  • $\begingroup$ And this generalizes fairly easily to a proof for any non-square. $\endgroup$ – marty cohen Jan 4 '17 at 23:07
0
$\begingroup$

Lemma: $a^2$ is divisible by $3$ if and only if $a$ is.

Proof: By examining all possible cases:

  • If $a$ is divisible by $3$, $a^2$ is, trivially.
  • If $a$ is not divisible by $3$, $a^2$ is not, either.

Indeed, if $a$ is not divisible by $3$, then $a=3k\pm1$ for some $k$. Then $$a^2=9k^2\pm6k+1=3(3k^2\pm2k)+1$$ has remainder $1$ upon division by $3$.

$\endgroup$
  • $\begingroup$ Thanks for proving the lemma in a very clear way. $\endgroup$ – Bryan Jun 3 '15 at 0:55
  • $\begingroup$ So, for each proof that $\sqrt{p}$ is irrational, you need a new and different lemma. $\endgroup$ – GEdgar Jun 3 '15 at 13:31
  • $\begingroup$ That's a short and clear proof for the case the O.P. submitted. I wouldn't use it as a general proof. There is a very general proof that doesn't even use the Fundamental theorem of arithmetic, nor Euclid's lemma. It consists in proving that $\sqrt n$ is irrational, unless $n$ is a square in $\mathbf N$ and is just based on the well order of $\mathbf N$. $\endgroup$ – Bernard Jun 3 '15 at 13:51
0
$\begingroup$

Let us try a new one. Assume $a = \sqrt{3}b$ for integers a and b, then $a^2 = 3b^2$. Now use uniqueness of prime factorization and count the occurences the prime 3 has in the numbers. if $a = 3^{d}c$ and $b = 3^{g}f$, then we have that $a^2 = 3^{2d}c^2$ and that $3b^2 = 3^{2g+1}f^2$.

We now see that left hand side has even number of 3-factors but right hand side has odd - contradiction.

$\endgroup$
0
$\begingroup$

Here is a very simple general proof that the square root of any integer that is not a perfect square is irrational. For convenience, write $a|b$ (read "a divides b") for "b is divisible by a". The proof depends on Euclid's Lemma, which states that if $gcd(a, b) = 1$ and $a | bc$, then $a | c$.

For positive integers $a$, $b$, and $n$, assume $(\frac a b)^2 = n$, where $gcd(a, b) = 1$ (i.e., the fraction is in lowest terms). Then $a^2 = b^2n$, so $a | (b^2n)$.

By Euclid's Lemma, $a | bn$, and applying the Lemma again, $a | n$. Since $n$ is divisible by $a$, we may divide both sides of $a^2 = b^2 n$ by $a$ to get $a = b^2(\frac n a)$, where $(\frac n a)$ is an integer.

But this means that $b | a$, so $gcd(a, b) = b$. Since we know $gcd(a, b) = 1$, this means that $b = 1$, which implies, in turn, that $n = a^2$. That is, $n$ is the square of an integer, i.e., a perfect square.

We have just proven that any integer that is the square of a rational number is a perfect square. This is logically equivalent to the assertion that any integer that is not a perfect square is not the square of any rational number, i.e., the square root of any integer that is not a perfect square is irrational.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.