# I Two integers and thus their squares have no common factors

1. May 26, 2016

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

Last edited: May 26, 2016
2. May 26, 2016

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

3. May 26, 2016

### Happiness

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. May 26, 2016

### Staff: Mentor

Missed that part of your post. Never mind.

5. May 26, 2016

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

6. May 26, 2016

### Happiness

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
7. May 26, 2016

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

8. May 26, 2016

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

9. May 26, 2016

### Happiness

I don't follow the last part. Why must $a$ be unity if it divides $pq$?

10. May 26, 2016

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

11. May 26, 2016

### Happiness

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
12. May 26, 2016

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

13. May 26, 2016

### Happiness

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
14. May 26, 2016

### PeroK

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. May 26, 2016

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

16. May 26, 2016

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

Last edited: May 27, 2016
17. May 27, 2016

### Happiness

$a=12$ divides $36=p^2$ but $12$ is not a square number.

18. May 27, 2016

### Erland

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. May 27, 2016

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

Last edited: May 27, 2016
20. May 27, 2016

### Happiness

21. May 27, 2016

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

22. May 27, 2016

### Happiness

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. May 27, 2016

### FQVBSina

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. May 27, 2016

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

25. May 27, 2016

### Happiness

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

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted