Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I Two integers and thus their squares have no common factors

  1. May 26, 2016 #1
    Integers ##p## and ##q## having no common factors implies ##p^2## and ##q^2## have no common factors. Could you prove this without using the fundamental theorem of arithmetic (every integer greater than 1 either is prime itself or is the product of prime numbers, and that this product is unique, up to the order of the factors)?

    Note that this isn't the same as saying integers ##p## and ##q## having a common factor implies ##p^2## and ##q^2## have a common factor, which is straightforward.

    The above proposition is obtained from the following proof (last paragraph, line 1). I believe the book does't use the fundamental theorem of arithmetic because if it does (implicitly require it for the above proposition) then it might as well use it right from the start for the following proof, i.e., let ##m## be a product of primes.
    Screen Shot 2016-05-26 at 3.31.59 pm.png

    Note that ##p^2## has more factors than ##p##. For example, ##12## is a factor of ##p^2=36## but not of ##p=6##. That's why the proposition is not immediately obvious.
     
    Last edited: May 26, 2016
  2. jcsd
  3. May 26, 2016 #2

    DrClaude

    User Avatar

    Staff: Mentor

    I'm not a mathematician, but I'll have a go. The experts on PF will surely chime in, especially if I say something wrong!

    If p and q have no common factor, then their prime factorization involves distinct sets of prime factors. Since taking the power doesn't change the set of prime factors, pn and qn have no common factor if p and q have no common factor.
     
  4. May 26, 2016 #3
    That's true, but that's also using the fundamental theorem of arithmetic!

    If the book assumes the reader knows the theorem, then why not use it for the proof, i.e., let ##m## be a product of primes?
     
  5. May 26, 2016 #4

    DrClaude

    User Avatar

    Staff: Mentor

    :oops: Missed that part of your post. Never mind.
     
  6. May 26, 2016 #5

    fresh_42

    Staff: Mentor

    One can show that ##p## is the only possible proper divisor of ##p^2## only by using the definition of a prime:
    ##p## is prime if and only if it is no unit and ##p \, | \, ab ⇒ p \, | \, a \; ∨ \; p \, | \, b##
    So every common divisor of ##p^2## or ##q^2## has to be ##p## and ##q## which is ruled out.
    (One can avoid the proof by contradiction and show that the divisor then will have to be a unit.)

    Of course this is the same property that is used to proof the fundamental theorem so one has to be careful to distinguish between them.
     
  7. May 26, 2016 #6
    But ##p## and ##q## don't need to be prime, they only need to be coprime.

    But your argument does make some progress. ##p^2## and ##q^2## cannot have a common divisor that is prime. Otherwise, that prime divisor will divide both ##p## and ##q## and we have a contradiction. But what is required for the proof is that ##p^2## and ##q^2## cannot have any common divisor.
     
    Last edited: May 26, 2016
  8. May 26, 2016 #7

    fresh_42

    Staff: Mentor

    How about this:
    ##p## and ##q## being coprime means there are numbers ##x,y## such that ##1=xp+yq##. Let us assume ##a## divides both, ##p^2## and ##q^2.##
    Thus ##a \, | \, xp^2 = (p - ypq)## and ##a \, | \, xp^2q = (pq - ypq^2)##. Because ##a \, | \, q^2## it has to divide ##pq## as well. Therefor ##a## has to be a unit.
     
  9. May 26, 2016 #8

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    if the FTA were false then there would exist a number with two distinct prime factorisations and you could thereby construct p and q as a counterexample to the proposition. Thus, one way or another, the proof hinges on the FTA.
     
  10. May 26, 2016 #9
    I don't follow the last part. Why must ##a## be unity if it divides ##pq##?
     
  11. May 26, 2016 #10

    fresh_42

    Staff: Mentor

    You're right. I assumed ##a## to be prime which I must not do without using the theorem. Seems to be more complicated than I first thought. Surely one has to use the argumentation of the theorem' proof somehow without using the result. Let me have a closer look.

    Edit: If ##a \, | \, pq## then ##a \, | \, 1 = 1^2 = (xp+yq)^2 = x^2p^2 + y^2q^2 + 2xypq,## i.e. ##a## is a unit.
     
  12. May 26, 2016 #11
    Then I think the proof provided by the book is not a good one, because using the fundamental theorem of arithmetic right from the start is more straightforward, i.e., letting ##m## be a product of primes and then arguing that if ##\sqrt{m}## is rational then ##\sqrt{p_i}## is also rational, where ##p_i## is one of the primes in the prime factorisation of ##m##, which soon leads to a contradiction.

    Then the proof provided only looks simple but it's actually not complete without invoking the fundamental theorem of arithmetic. In other words, it look as though it is simpler than those methods that use the fundamental theorem of arithmetic, but it's actually not.
     
    Last edited: May 26, 2016
  13. May 26, 2016 #12

    fresh_42

    Staff: Mentor

    I'm not quite sure whether the equivalence between ##p## and ##q## are coprime and the existence of the equation ##1 = xp +yq## already uses the theorem. One could define coprime this way, but one can as well define it by there is no proper common divisor.
    The question essentially comes down on: "Does the Euclidean division implicitly make use of the fundamental theorem of Arithmetic?"
    I don't think so but I'm not sure.
     
  14. May 26, 2016 #13
    Good job.

    But I doubt this is what the author had in mind when he wrote his proof because he didn't introduce the Bezout's identity or the fundamental theorem of arithmetic in any preceding sections. Probably he overlooked the fact that either one (or something else equally or more advanced) has to be used in his proof.

    He must have ironically made an inverse error, having warned readers about it in the next section.
     
    Last edited: May 26, 2016
  15. May 26, 2016 #14

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    The proof in the book states without further note that "##p## and ##q##, hence ##p^2## and ##q^2## have no common factors". This depends on the FTA. Also, this is essentially the proof in a nutshell, as it shows that proper rationals square to proper rationals, never to whole numbers. QED
     
  16. May 26, 2016 #15

    mathman

    User Avatar
    Science Advisor
    Gold Member

    Can we start from [itex]a|p^2[/itex], then [itex]a=b^2[/itex], where b is an integer? If so assume a divide both squares, then b divides both.
     
  17. May 26, 2016 #16

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper

    as suggested above, it does not use the FTA to say that two integers n,m are relatively prime iff there exist integers a,b with an+bm = 1. then cubing this equation gives 1 = a^3n^3 + 3a^2n^2bm + 3 anb^2m^2 + b^3m^3 = n^2X + m^2Y, so n^2 and m^2 are also rel prime.
     
    Last edited: May 27, 2016
  18. May 27, 2016 #17
    ##a=12## divides ##36=p^2## but ##12## is not a square number.
     
  19. May 27, 2016 #18

    Erland

    User Avatar
    Science Advisor

    What do you mean? How do we get a simpler proof than the book's by beginning with the assumption that ##m## is a product of primes?

    As has been pointed out, the proof in the book does depend upon the fundamental theorem of arithmetic.
     
  20. May 27, 2016 #19
    You can prove it by proving square root of 2 is irrational.

    The ancient greeks thought that all numbers can be represented by a fraction of two integers. So square root of 2 should be able to be expressed as p/q, given p and q are integers prime to each other (no common factors). Now if we square both sides we have 2 = p^2/q^2.

    Rearrange we get 2q^2 = p^2 which means p^2 has a factor of 2 and q^2, which makes p^2 even.

    If p^2 is even, then p must also be even because only even numbers can square into even numbers.

    Similarly, we have q^2 = p^2/2. We showed p^2 is even then there are at least two factors of 2 in p^2 (since p is also even). p^2 divided one 2 still has one 2 left, then q^2 is even. By previous statement, only even can square into even, so q is also even.

    Now we have a problem, we stated in the beginning that p and q have no common factors but now we found a common factor of 2. That proves square root of 2 is irrational.

    But as you can see the middle process answered your question.
     
    Last edited: May 27, 2016
  21. May 27, 2016 #20
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Two integers and thus their squares have no common factors
  1. Square of Integer (Replies: 2)

Loading...