2

Question on a proof's review:

Proof by contradiction:

Suppose $a$ is not an integer. Then $a=p/q$ where $p$ and $q$ are coprime, $q$ is not 0, and $q$ is not 1.

Then $a^2 = p^2/q^2$.

This is as far as I've gotten, my t.a. says I'm on the right track, I just need help reasoning why my conclusion leads to a contradiction.

Please help.

user122661
  • 983
  • Can you show that $a^2$ is a rational number? – joebloggs May 07 '14 at 18:53
  • @joebloggs "$a^2$ is an integer" is the assumption. >Integers are rational... – snulty May 07 '14 at 18:56
  • Here's a useful hint. The key point is $a^2$ is an integer by assumption. So where you have $a^2=p^2/q^2$, multiply across by $q^2$. Now you have $p^2=a^2q^2$, and all three of $p^2$, $q^2$ and $a^2$ are integers, so you can use what you know about divisibility in the integers – snulty May 07 '14 at 18:58
  • @Snulty correct. I meant to say, rational, non-integer. $a^2$ is an integer by assumption. So if you could lead to $a^2$ is a rational, non-integer, it would be a contradiction. – joebloggs May 07 '14 at 19:00
  • @joebloggs fair enough. – snulty May 07 '14 at 23:26

2 Answers2

4

Hint $\ \ (p/q)^2 \in\Bbb Z\,\Rightarrow\, \color{}q\mid \color{#c00}p\cdot\color{#0a0}p\overset{\large (q,\color{#c00}p)=1}{\underset{\large \rm Euclid}\Rightarrow} q\mid\color{#0a0}p\,\Rightarrow\, \color{}p/q\in\Bbb Z\ \ $ QED

Bill Dubuque
  • 272,048
3

Hint Let $m$ be a prime number dividing $q$. Then $m|q^2|p^2$ thus $m|p$. Do you see the contradiction?

Here is the complete proof:

As $q \neq 1$ there exists a prime number $m$ dividing $q$.

Then, as $m|q$ we have $m|q \cdot q=q^2$.

As $p^2=a^2q^2$ and $a^2$ is integer, we have $q^2|p^2$.

Therefore $m|q^2$ and $q^2|p^2$. This implies $m|p^2$.

Since $m$ is prime and $m|p \cdot p$ then $m|p$.

This proves that $m|p$. As $m|q$, this contradicts the fact that $p,q$ are relatively prime.

P.S. If you want a constructive proof, the same idea can be combined with the Fundamental Theorem of Arithmetic to prove that if $q^2|p^2$ then $q|p$.

Exactly as above you can first prove that all primes dividing $q$ must also divide $p$, and then you can prove that their power in $q$ is smaller than their power in $p$. I preferred the contradiction proof since it is much shorter.

N. S.
  • 132,525
  • 1
    Would the downvoter please explain? – N. S. May 07 '14 at 18:43
  • 1
    I did not downvote, but here's a guess: there is no explicit justification of the crucial inference: $, m\mid p^2,\Rightarrow, m\mid p.\ $ Such justification is essential for proofs at this level (or at least an explicit remark that it needs justification when hinting). – Bill Dubuque May 07 '14 at 18:50
  • @BillDubuque Funny, I thought it was because I gave too many details, I tried to make it a hint instead of a complete answer... And that implication is just the definition of prime numbers ..... – N. S. May 07 '14 at 18:52
  • Question: If $gcd(p,q) = 1$ does this mean that the $gcd(p^2,q^2) = 1$ as well? – user122661 May 07 '14 at 18:54
  • too many details? This answer is almost cryptic. your are skipping way too many steps. In particular, I don't think this is a helpful answer. I am downvoting. –  May 07 '14 at 18:54
  • @user122661 Yes, there a a few ways to see that, e.g. by uniqueness of prime factorizations, Euclid's Lemma,or Bezout's Identity, or Gauss's Lemma, or the Distributive Law for gcds, etc. There are probably a few hundred posts here with proofs. – Bill Dubuque May 07 '14 at 18:57
  • Alright, so I'll assume that in the proof, does that fact ($gcd(p^2,q^2) = 1$) lead us to our contradiction? I assume it does, as the gcd of an integer would be the integer itself (unless the integer in question is 1, in which case the original conditions on $a$ contradict). – user122661 May 07 '14 at 18:58
  • @MathcanbeFun No offense, but for a homework question I think one needs to leave the OP something to prove.. ANd here are the steps I am skipping:1) $m|q \Rightarrow m|q^2$... 2) $m|q^2$ and $q^2|p^2$ implies $m|p^2$ and finally 3) $m|p^2$ and $m$ prime implies $m|p$... Which of these three steps is not starightforward but cryptic? – N. S. May 07 '14 at 18:59
  • OK, I guess I should erase this answer as it seems to be considered junk.... – N. S. May 07 '14 at 19:00
  • @N.S. For one example of why one may need more detail, see the erroneous proof just posted (which is quite common). But I think users should be more constructive before downvoting. We should try to work with the author to improve answers before downvoting them. – Bill Dubuque May 07 '14 at 19:00
  • I will un downvote this answer, plus I will upvote if N.S. provides more details. thanks. –  May 07 '14 at 19:02
  • @MathcanbeFun Please don't upvote it, if you do I erase the extra details. – N. S. May 07 '14 at 19:05
  • @MathcanbeFun For a homework question is a bad idea to include a complete proof, at least IMO... I tried to guide the student towards a solution instead of solving the problem for him/her... And I really think that the missing details were pretty straightforward... – N. S. May 07 '14 at 19:07
  • I understand, but sometimes beginners have diffilcuties with proofs. maybe if you already know the material, then a hint is good enough and even healthy. I hope you understand me and sorry for downvoting at the beginning. cheers –  May 07 '14 at 19:09
  • @MathcanbeFun I don't mind the downvotes, but I would prefer if the downvoter explains his/her issues with the proof ;) – N. S. May 07 '14 at 19:13
  • @N.S. I agree about giving away too much in a hint. It would have sufficed to write something like $,m\mid p^2,\Rightarrow,m\mid p,$ because $,p,$ is $,\ldots$ or something like that, and say something about how the proof depends crucially on the Fundamental Theorem of Arithmetic (uses both the existence and uniqueness of prime factorizations). It can fail in rings that lack these properties, i.e. rings not UFDs. – Bill Dubuque May 07 '14 at 19:13
  • @BillDubuque Actually $m|p^2 \Rightarrow m|p$ depends only on the definition of prime numbers. The FTA appears in the proof in a very hidden way: it enters the proof when we speak about $p,q$ being relatively prime, UFD is needed to make sure the gcd is well defined... But I agree, the proof can be rewritten without the GCD, using the FTA directly ;) – N. S. May 07 '14 at 19:27
  • @N.S. I suspect that FTA/UFD appears hidden because you overlooked a key invocation of it, viz. that atoms (irreducibles) are prime. This is equivalent to the uniqueness of factorizations into atoms (the nontrivial half of FTA/UFD, the existence of factorizations into atoms is trivial in $,\Bbb Z).$ – Bill Dubuque May 07 '14 at 20:29