Two integers and thus their squares have no common factors

  • I
  • Thread starter Happiness
  • Start date
  • #1
673
29
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:

Answers and Replies

  • #2
DrClaude
Mentor
7,754
4,255
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.
 
  • #3
673
29
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.

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?
 
  • #4
DrClaude
Mentor
7,754
4,255
:oops: Missed that part of your post. Never mind.
 
  • Like
Likes ProfuselyQuarky
  • #5
fresh_42
Mentor
Insights Author
2021 Award
16,427
15,469
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.
 
  • #6
673
29
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.

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:
  • #7
fresh_42
Mentor
Insights Author
2021 Award
16,427
15,469
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.
 
  • #8
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2021 Award
21,523
12,827
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.
 
  • Like
Likes FactChecker
  • #9
673
29
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.

I don't follow the last part. Why must ##a## be unity if it divides ##pq##?
 
  • #10
fresh_42
Mentor
Insights Author
2021 Award
16,427
15,469
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.
 
  • #11
673
29
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.

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:
  • #12
fresh_42
Mentor
Insights Author
2021 Award
16,427
15,469
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.
 
  • #13
673
29
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.

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:
  • #14
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2021 Award
21,523
12,827
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.

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
 
  • #15
mathman
Science Advisor
8,046
535
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.
 
  • #16
mathwonk
Science Advisor
Homework Helper
11,307
1,522
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:
  • #17
673
29
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.

##a=12## divides ##36=p^2## but ##12## is not a square number.
 
  • #18
Erland
Science Advisor
741
138
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.
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.
 
  • #19
37
8
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:
  • #20
673
29
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.

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.

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.
 
  • #21
37
8
Actually reading your post in full detail and the image from the book of square root of m = r = p/q, that is exactly what I proved in my above reply.
 
  • #22
673
29
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.

I think that's what the book is trying to do, to generalize the proof to all other integers ##m##. But this can't be done (probably) without using the fundamental theorem of arithmetic (or something else equally advanced), which is not needed in the case when ##m=2##.
 
  • #23
37
8
I think that's what the book is trying to do, to generalize the proof to all other integers ##m##. But this can't be done (probably) without using the fundamental theorem of arithmetic (or something else equally advanced), which is not needed in the case when ##m=2##.
I dare say that the same process can be used for square root of 3.
Let square root 3 = p/q.
3 = p^2/q^2
p^2 = 3q^2, showing p^2 has factor of 3, since it is squared, 3 can't stand by itself, there must be another 3, indicating that p also has a factor of 3.
Now q^2 = p^2/3, since we have established that there are at least two 3's in p^2, then q^2 also has at least one 3 in its factors, and by same logic above, q must also have a 3 in its factors.
We again arrive at p and q both have factor of 3 and yet we said in beginning they shouldn't.

By this logic process, I can prove it for any number not just m = 2.
 
  • #24
37
8
But just to put it in variables.
if square root m = r = p/q.
Then m = r^2 = p^2/q^2
Then m*q^2 = p^2, and that means p^2 has m as one of the factors. Since p^2 is a perfect square, there must be another m as a factor, and that means p also has m as a factor.
Now q^2 = p^2/m. Since we have established that p^2 has at least 2 m's as factors, then p^2/m would still end up with a factor m times something, which means q^2 has m as factor. By the same squaring logic, q also has m as factor.
In the beginning we assumed p and q to have no common factors but now we found they both have a common factor m, thus square root m cannot be rational.
 
  • #25
673
29
But just to put it in variables.
if square root m = r = p/q.
Then m = r^2 = p^2/q^2
Then m*q^2 = p^2, and that means p^2 has m as one of the factors. Since p^2 is a perfect square, there must be another m as a factor, and that means p also has m as a factor.
Now q^2 = p^2/m. Since we have established that p^2 has at least 2 m's as factors, then p^2/m would still end up with a factor m times something, which means q^2 has m as factor. By the same squaring logic, q also has m as factor.
In the beginning we assumed p and q to have no common factors but now we found they both have a common factor m, thus square root m cannot be rational.

The part in bold is the essence of your proof, which should be proved, not just stated. Are you using the fundamental theorem of arithmetic subconsciously?

Your proof can be fine tuned by using the fact that if a prime number ##b## divides ##cd## then it divides ##c## or it divides ##d##. Apply this to your proof, we have ##m## divides ##p^2## so ##m## divides ##p##.

But this is only true when ##m## is prime. We have not fully generalized the proof to all integers ##m##.
 
  • #26
37
8
The pa rt in bold is the essence of your proof, which should be proved, not just stated. Are you using the fundamental theorem of arithmetic subconsciously?

Your proof can be fine tuned by using the fact that if a prime number ##b## divides ##cd## then it divides ##c## or it divides ##d##. Apply this to your proof, we have ##m## divides ##p^2## so ##m## divides ##p##.

But this is only true when ##m## is prime. We have not fully generalized the proof to all integers ##m##.

Hmm if the fundamental theorem is, quoting you, "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", then I do not believe I was using it.

I was simply deducing that since p^2 is perfect square, and if I can divide an m out of p^2, then p must also has m as factor. This is only excepted when m is a perfect square itself, such as m = 4, but then in that case, square root of 4 is simply 2, and it does not fall under the premise of this topic since 2 is a rational number.

And m does not have to be prime, as long as it is not a perfect square.
Say m = 6 = 2 x 3, then p^2 also needs a 6. Let me see if I can make this look more proof-like...
 
Last edited:
  • #27
673
29
Hmm if the fundamental theorem is, quoting you, "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", then I do not believe I was using it.

I was simply deducing that since p^2 is perfect square, and if I can divide an m out of p^2, then p must also has m as factor. This is only excepted when m is a perfect square itself, such as m = 4, but then in that case, square root of 4 is simply 2, and it does not fall under the premise of this topic since 2 is a rational number.

And m does not have to be prime, as long as it is not a perfect square.
Say m = 6 = 2 x 3, then p^2 also needs a 6. Let me see if I can make this look more proof-like...

Have you considered ##m=12## divides ##p^2=36## but not ##p=6##?
 
  • #28
Erland
Science Advisor
741
138
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.
How do you know 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##"?
I think that if you include a proof of that in a proof of the proposition in the book, you get a proof which is not significantly simpler than the proof in the book. Try to write down your own proof of the proposition in the book, and you will see...
In both cases, the fundamental theorem of arithmetic is used, at least implicitly.
 
  • #29
673
29
How do you know 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##"?
I think that if you include a proof of that in a proof of the proposition in the book, you get a proof which is not significantly simpler than the proof in the book. Try to write down your own proof of the proposition in the book, and you will see...
In both cases, the fundamental theorem of arithmetic is used, at least implicitly.

I didn't say my proof is simple. I said it is more straightforward. And my proof doesn't use the fundamental theorem of arithmetic implicitly, it uses it openly!

The author most likely made an inverse error when he wrote down his proof.
 
  • #30
Erland
Science Advisor
741
138
Btw, "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##" is wrong in general.
##\sqrt 4## is rational and ##2## is a prime factor of ##4##, but ##\sqrt 2## is not rational.
You can probably express what you mean more precisely and get it right, but will you then really get a proof of the proposition in the book which is simpler, or more straightforward, than the proof in the book?
 

Related Threads on Two integers and thus their squares have no common factors

  • Last Post
Replies
11
Views
3K
Replies
1
Views
914
Replies
14
Views
2K
Replies
3
Views
2K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
7
Views
547
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
15
Views
3K
Replies
4
Views
883
Top