Two integers and thus their squares have no common factors

[Happiness]

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.

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.

 

[DrClaude]

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, pⁿ and qⁿ have no common factor if p and q have no common factor.

 

[Happiness]

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, pⁿ and qⁿ 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?

 

[DrClaude]

Missed that part of your post. Never mind.

 

[fresh_42]

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.

 

[Happiness]

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.

 

[fresh_42]

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.

 

[PeroK]

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.

 

[Happiness]

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$?

 

[fresh_42]

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.

 

[Happiness]

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.

 

[fresh_42]

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.

 

[Happiness]

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.

 

[PeroK]

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

 

[mathman]

Can we start from $a|p^2$, then $a=b^2$, where b is an integer? If so assume a divide both squares, then b divides both.

 

[mathwonk]

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.

 

[Happiness]

Can we start from $a|p^2$, then $a=b^2$, 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.

 

[Erland]

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.

 

[FQVBSina]

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.

 

[Happiness]

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.

 

[FQVBSina]

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.

 

[Happiness]

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$.

 

[FQVBSina]

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.

 

[FQVBSina]

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.

 

[Happiness]

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$.

 

[FQVBSina]

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...

 

[Happiness]

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$?

 

[Erland]

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.

 

[Happiness]

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.

 

[Erland]

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?

 

[Happiness]

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?

Sorry, I don't follow you.

 

[Erland]

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$

I just pointed out that this is wrong in general. $m=4$, whose only prime factor is $2$, is a counterexample.

I suggest that you write down your own proof of the proposition in the book in full, to see if it really is simpler or more straightforward than the proof in the book, quoted in your OP.

 

[Happiness]

I just pointed out that this is wrong in general. $m=4$, whose only prime factor is $2$, is a counterexample.

Isn't this expected in a proof by contradiction?

I suggest that you write down your own proof of the proposition in the book in full, and see if it really is simpler or more straightforward than the proof in the book, quoted in your OP.

My proof is more straightforward, but I don't want to convince you that because I understand it is subjective. More crucially, the proof given in the book is not complete. It's deceivingly complete but it's not. The fundamental theorem of arithmetic is not even mentioned in the proof.

As mentioned by PeroK, the book states without further note the most essential part of the proof.

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

 

[Erland]

Isn't this expected in a proof by contradiction?

No, a proof by contradiction should lead to a contradiction in the end, it should not use invalid arguments in its body. But of course, I have not seen your full proof, which might clear this issue up.

More crucially, the proof given in the book is not complete. It's deceivingly complete but it's not. The fundamental theorem of arithmetic is not even stated in the proof.

I agree. Perhaps the author takes the fundamental theorem of arithmetic for granted. Since I am not familiar with the rest of the book, I don't know how appropriate that is.

 

[PeroK]

My proof is more straightforward, but I don't want to convince you that because I understand it is subjective. More crucially, the proof given in the book is not complete. It's deceivingly complete but it's not. The fundamental theorem of arithmetic is not even mentioned in the proof.

As mentioned by PeroK, the book states without further note the most essential part of the proof.

I've seen the proof in the book and similar variations many times. Often it is to show that $\sqrt{2}$ is irrational, or to show that $\sqrt{p}$ is irrational, where $p$ is prime, or (in this case) to show that $\sqrt{m}$ is either a whole number or irrational. Often, they make a big fuss over the proof, with contradiction or reductio ad absurdum. And it all looks quite complicated.

I remember being surprised the first time I noticed that the simple argument involving squares having no new prime factors proves the general case with a minimum of effort.

I don't think this is particularly important, but to see how much fuss can be made of this issue, look at a recent Insight:

https://www.physicsforums.com/insights/irrationality-for-dummies/

I think you should keep the simple proof you've found in your back pocket and move on!