Two integers and thus their squares have no common factors

  • I
  • Thread starter Happiness
  • Start date
  • #1
673
28
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:
  • Like
Likes mooncrater

Answers and Replies

  • #2
DrClaude
Mentor
7,554
3,894
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
28
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,554
3,894
:oops: Missed that part of your post. Never mind.
 
  • Like
Likes ProfuselyQuarky
  • #5
14,368
11,685
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
28
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
14,368
11,685
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
2020 Award
16,171
8,204
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
28
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
14,368
11,685
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.
 
  • Like
Likes Happiness
  • #11
673
28
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
14,368
11,685
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
28
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
2020 Award
16,171
8,204
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
7,899
461
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
2020 Award
11,100
1,302
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:
  • Like
Likes Happiness
  • #17
673
28
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
738
136
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
36
7
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
28
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
36
7
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
28
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
36
7
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
36
7
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
28
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##.
 

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

Replies
1
Views
753
  • Last Post
Replies
4
Views
1K
Replies
3
Views
9K
  • Last Post
Replies
2
Views
3K
Replies
4
Views
743
Replies
17
Views
1K
Replies
3
Views
2K
Replies
14
Views
2K
  • Last Post
Replies
15
Views
2K
Replies
1
Views
1K
Top