[number theory] prove that x^2+y^2=3 has no rational points

[RossH]

Homework Statement

The actual problem is: "Does x^2+y^2=3 have any rational points? If so, find a way to describe all of them. If not, prove it."

Homework Equations

None

The Attempt at a Solution

I found a book on Google Books (can't find it again) that said that this circle has no rational points, so I have been working at proving this. If this book is wrong, I would only need to find one rational point to prove that the circle has infinite rational points, as the center is rational and any line through that single rational point with a rational slope would give a rational point wherever it intersects the circle.

Anyway, to prove that there are no rational points:

First, to test my theory that there are no rational points, I wrote a program. I chose a bunch of random rational x values, solved for y, and tested the values for rationality. I found nothing rational, so that was inconclusive.

I also tried a proof by contradiction. The definition of a rational point is that both values have to be rational and the definition of rational is that the number can be formed by m/n where m and n are both integers. So I tried plugging into an equation:
(x/a)^2+(y/b)^2=3 and simplifying, but this didn't seem to get me anywhere. A proof by contradiction would require an impossibility but I kept getting functions no matter how much I algebra'd it.

Next I tried a proof by induction. My theory was that I could plug in x=n=0 and at each inductive step plug in n=n+lim(k->inf)(1/k), but obviously this doesn't work (for too many reasons). Also, I would need some function or method to test if the value was rational, which I just don't see. Since theoretically it is impossible to get a step of any size and still test all the points on the circle, I have thrown away the possibility of a proof by induction. (I'm really bad at them though, so I might be missing something).

I don't really know where to go from here. Obviously this is open ended and it is quite possible that my theory and that book I found were wrong and there is a rational point on this circle. If anybody could point me in the right direction, I would appreciate it. Thank you!

 

[Dick]

Do you know sqrt(3) is irrational? Try and use that.

 

[dextercioby]

Let's point him further in the right direction. Assume x, y rational, so that

$$x=\frac{m}{n} \, , \, y=\frac{p}{q} \, , \, m,n,p,q\in\mathbb{N}, \, , \, n,q\neq 0$$

Then what equation do you get ?

 

[RossH]

Do you know sqrt(3) is irrational? Try and use that.

Let's point him further in the right direction. Assume x, y rational, so that

$$x=\frac{m}{n} \, , \, y=\frac{p}{q} \, , \, m,n,p,q\in\mathbb{N}, \, , \, n,q\neq 0$$

Then what equation do you get ?

Both of these are kind of what I was trying to do with my proof by contradiction. So then I would get m²/n²+p²/q²=3. Integer squared is integer, so this means that integer1/integer2+integer3/integer4=3. The left side is a rational number (because integer/integer is rational and sum of rationals is rational) and the rhs (3) is a rational number. The place where I run into problems is the next step:
sqrt(rational_lhs)=sqrt(3): irrational. But the sqrt(rhs) can feasibly be irrational because the square root of an integer can be irrational, so this is not necessarily a contradiction.
Does it have something to do with the bounds, that 0=<x,y=<sqrt(3)?

 

[Hurkyl]

I usually first try attacking Diophantine equations like this with modular arithmetic. (You may find it convenient to turn it into an integer equation instead of a rational number equation -- I hope I'm not spoiling anything when I say it's x² + y² = 3 z²)

 

[RossH]

I usually first try attacking Diophantine equations like this with modular arithmetic. (You may find it convenient to turn it into an integer equation instead of a rational number equation -- I hope I'm not spoiling anything when I say it's x² + y² = 3 z²)

I'm not quite sure where you are going with this. I understand the concept of modular arithmetic and I know what a Diophantine equation is, but I don't see why this is one. Isn't one of the criteria for a Diophantine equation that the variables can only be integers? That is not the case here. Also, how does the last equation fit into the problem? Perhaps I am not yet far enough in math for the concepts that you are presenting and my professor was looking for a simpler solution or a different direction. (I've taken Calc A,B,C, Linear Algebra, Stats) Thank you for your help.

 

[epenguin]

See Polya small book 'How to solve it'. 5 tips. One was 'have you ever seen anything like it?'

If you have been set this problem you will have seen the proof that √2 is irrational.

Try using similar kind of argument about parity (evenness and oddness).

It is a bit more complicated than √2 as you have more numbers and possibilities (which turn out to be impossibilities). I did it, well I think I did, without needing to use irrationality of √3 though if there is a way using that does nothing wrong if it gives result.

If you succeed take advantage of other Polya tip: when you have answered the question it's not finished. Can you extend your result and state a more general one? Like √2 is only one lousy number, your result is only one lousy circle. Impress your Prof. and yourself!

 

[RossH]

See Polya small book 'How to solve it'. 5 tips. One was 'have you ever seen anything like it?'

If you have been set this problem you will have seen the proof that √2 is irrational.

Try using similar kind of argument about parity (evenness and oddness).

It is a bit more complicated than √2 as you have more numbers and possibilities (which turn out to be impossibilities). I did it, well I think I did, without needing to use irrationality of √3 though if there is a way using that does nothing wrong if it gives result.

If you succeed take advantage of other Polya tip: when you have answered the question it's not finished. Can you extend your result and state a more general one? Like √2 is only one lousy number, your result is only one lousy circle. Impress your Prof. and yourself!

I've been studying that proof for a while due to your suggestion. It makes sense that I could use it to prove this, but I've run into a wall. What I have so far is this:

1) x^2 + y^2 = 3
2) Assume that x and y are rational, meaning that for both there exists integers a,b,c,d such that a/b=x, c/d=y
3) Then both x and y can be written as irreducible fractions. x=a/b such that a and b are coprime and y=c/d with c and d coprime.
4) It follows that a^2/b^2 + c^2/d^2 = 3
5) And a^2*d^2+c^2*b^2 = 3*b^2*d^2

EDITED: (snip)

My problem is that both sides at (5) could be even or odd. A square number can be even or odd and an 3k can be even or odd. I multiplied both sides by b^2*d^2 so that I would just be dealing with integers, but I'm not sure where to go from here. I just don't know where to get the replacement step. In the sqrt(2) proof there was the step where you replaced one of the variables with 2k because you knew it was even, but I can't see any guarantee of any kind of parity here.
I also looked at the other proof for the irrationality of sqrt(2) but I figured that this one was the most relevant, so decided to work with it.

 

[epenguin]

I've been studying that proof for a while due to your suggestion. It makes sense that I could use it to prove this, but I've run into a wall. What I have so far is this:

1) x^2 + y^2 = 3
2) Assume that x and y are rational, meaning that for both there exists integers a,b,c,d such that a/b=x, c/d=y
3) Then both x and y can be written as irreducible fractions. x=a/b such that a and b are coprime and y=c/d with c and d coprime.
4) It follows that a^2/b^2 + c^2/d^2 = 3
5) And a^2*d^2+c^2*b^2 = 3*b^2*d^2

EDITED: (snip)

My problem is that both sides at (5) could be even or odd. A square number can be even or odd and an 3k can be even or odd. I multiplied both sides by b^2*d^2 so that I would just be dealing with integers, but I'm not sure where to go from here. I just don't know where to get the replacement step. In the sqrt(2) proof there was the step where you replaced one of the variables with 2k because you knew it was even, but I can't see any guarantee of any kind of parity here.
I also looked at the other proof for the irrationality of sqrt(2) but I figured that this one was the most relevant, so decided to work with it.

Both sides could be even or odd. But in each case, then what about the terms on each side? (Actually there is a symmetry than means you don't have to consider all cases but only half of them, but you'll see that when you get there).
Actually I did it by subtraction one term from both sides, aka bringing it to the other side, and expressing it in factorised form but I don't think this is obligatory.

 

[Dick]

I've been studying that proof for a while due to your suggestion. It makes sense that I could use it to prove this, but I've run into a wall. What I have so far is this:

1) x^2 + y^2 = 3
2) Assume that x and y are rational, meaning that for both there exists integers a,b,c,d such that a/b=x, c/d=y
3) Then both x and y can be written as irreducible fractions. x=a/b such that a and b are coprime and y=c/d with c and d coprime.
4) It follows that a^2/b^2 + c^2/d^2 = 3
5) And a^2*d^2+c^2*b^2 = 3*b^2*d^2

In step 5 you've got an equation of the form x^2+y^2=3*z^2. You want to prove this has no solutions. Hint: if it has ANY solutions then it has solutions where x, y and z are not all divisible by 3.

 

[RossH]

Sorry if I don't make sense at places in this post. It's a little late and I'm a little tired. :(

In step 5 you've got an equation of the form x^2+y^2=3*z^2. You want to prove this has no solutions. Hint: if it has ANY solutions then it has solutions where x, y and z are not all divisible by 3.

I'm not quite sure why this is true. And when I try to solve it, it does have solutions. For example, I got Z=(+/-)sqrt(x^2+y^2)/sqrt(3). Does this mean that it is impossible for Z to be an integer? Is that conclusive enough?

Both sides could be even or odd. But in each case, then what about the terms on each side? (Actually there is a symmetry than means you don't have to consider all cases but only half of them, but you'll see that when you get there).
Actually I did it by subtraction one term from both sides, aka bringing it to the other side, and expressing it in factorised form but I don't think this is obligatory.

Hmm, I tried the parity test like you suggested. While most of the situations were not in parity, some were:

5) And a^2*d^2+c^2*b^2 = 3*b^2*d^2
6) It is not possible that at any time both a and b are even and both c and d are even because then the fractions would not be irreducible. Hence, there are only a few circumstances that must be considered.

If:

a is even, b is odd, c is even, d is odd: right side is odd, left side is even.
a is odd, b is even, c is odd, d is even: right side is even, left side is even.
a is odd, b is odd, c is odd, d is odd: right side is odd, left side is even
a is even, b is odd, c is odd, d is even: right side is odd, left side is odd
a is odd, b is even, c is even, d is odd: right side is even, left side is odd

 

[Hurkyl]

For the record, working mod 4 or mod 8 usually tells you a lot more useful information than working mod 2 when squaring is involved.

 

[epenguin]

Hmm, I tried the parity test like you suggested. While most of the situations were not in parity, some were:

5) And a^2*d^2+c^2*b^2 = 3*b^2*d^2
6) It is not possible that at any time both a and b are even and both c and d are even because then the fractions would not be irreducible. Hence, there are only a few circumstances that must be considered.

If:

a is even, b is odd, c is even, d is odd: right side is odd, left side is even.
a is odd, b is even, c is odd, d is even: right side is even, left side is even.
a is odd, b is odd, c is odd, d is odd: right side is odd, left side is even
a is even, b is odd, c is odd, d is even: right side is odd, left side is odd
a is odd, b is even, c is even, d is odd: right side is even, left side is odd

Check your 5th line. Mistake?

That would leave your second. Evens on both sides. So write it out explicitly b' = 2b, d' = 2d and see what this suggests to do.

I think you would do well then to check against Hurkyl's suggestion which may be same thing but then you may see it as logical.

Note that, as mentioned before, there is some superfluity in the cases you consider, that is you have two fractions which you have called a/b and c/d but you could have called them the other way round so to speak, so there is no difference between them. Essence of algebra.

 

[Dick]

I'm not quite sure why this is true. And when I try to solve it, it does have solutions. For example, I got Z=(+/-)sqrt(x^2+y^2)/sqrt(3). Does this mean that it is impossible for Z to be an integer? Is that conclusive enough?

I mean no integer solutions. And no, that's not conclusive. What are the possible values for n^2 mod 3 if n is an integer?

 

[RossH]

I mean no integer solutions. And no, that's not conclusive. What are the possible values for n^2 mod 3 if n is an integer?

a^2*d^2+c^2*b^2 = 3*b^2*d^2

I'm really sorry if I'm being dense here.
The rhs obvious always is congruent to 0 modulus 3.
A number that has the form 3k when squared will have the form 3(3k^2), so it will be congruent to 0 (mod 3).
A number that has the form 3k+1 when squared will have the form 9k^2+6k+1 or 3(3k^2+2k)+1, so it will be congruent to 1 (mod 3).
And a number that has the form 3k+2 when squared will have the form 9k^2+6k+4 or 3(3k^2+2k) + 4, so it will be congruent to 4 (mod 3), which is congruent to 1 (mod 3).

This argument also works for two numbers multiplied, that is 3m*3n=6mn=3(2mn) is congruent to 0 (mod 3).
(3m+1)(3n+1) = 9mn+3m+3n+1=3(3mn+m+n)+1 is congruent to 1 (mod 3).
(3m+2)(3n+2)=9mn+6m+6n+4=3(3mn+2m+2n)+4 is congruent to 4 (mod 3) is congruent to 1 (mod 3).

Therefore, the left side can only be congruent to the right side (mod 3) if both terms are congruent to 0 (mod 3). Since the terms cannot be 0, because they are being used in division, they must be divisible by 3. Therefore, the fractions are not irreducible and there are no rational solutions to this circle.

Does that work!? Did I get it!?

 

[Dick]

a^2*d^2+c^2*b^2 = 3*b^2*d^2

I'm really sorry if I'm being dense here.
The rhs obvious always is congruent to 0 modulus 3.
A number that has the form 3k when squared will have the form 3(3k^2), so it will be congruent to 0 (mod 3).
A number that has the form 3k+1 when squared will have the form 9k^2+6k+1 or 3(3k^2+2k)+1, so it will be congruent to 1 (mod 3).
And a number that has the form 3k+2 when squared will have the form 9k^2+6k+4 or 3(3k^2+2k) + 4, so it will be congruent to 4 (mod 3), which is congruent to 1 (mod 3).

This argument also works for two numbers multiplied, that is 3m*3n=6mn=3(2mn) is congruent to 0 (mod 3).
(3m+1)(3n+1) = 9mn+3m+3n+1=3(3mn+m+n)+1 is congruent to 1 (mod 3).
(3m+2)(3n+2)=9mn+6m+6n+4=3(3mn+2m+2n)+4 is congruent to 4 (mod 3) is congruent to 1 (mod 3).

Therefore, the left side can only be congruent to the right side (mod 3) if both terms are congruent to 0 (mod 3). Since the terms cannot be 0, because they are being used in division, they must be divisible by 3. Therefore, the fractions are not irreducible and there are no rational solutions to this circle.

Does that work!? Did I get it!?

You are almost there. If x^2+y^2=3*z^2, then x and y must be divisible by 3, as you've shown. Now you want to show z is also divisible by 3. Hint: if x is divisible by 3 then x^2 is actually divisible by 9. Remember how the proof sqrt(3) is irrational works.

 

[RossH]

You are almost there. If x^2+y^2=3*z^2, then x and y must be divisible by 3, as you've shown. Now you want to show z is also divisible by 3. Hint: if x is divisible by 3 then x^2 is actually divisible by 9. Remember how the proof sqrt(3) is irrational works.

The rhs takes the form 3*b^2*d^2=3k, and therefore is divisible by 3 because 3 is a factor of 3k. Is this not enough?
EDIT: Never mind. I see what you mean now.

 

[RossH]

You are almost there. If x^2+y^2=3*z^2, then x and y must be divisible by 3, as you've shown. Now you want to show z is also divisible by 3. Hint: if x is divisible by 3 then x^2 is actually divisible by 9. Remember how the proof sqrt(3) is irrational works.

I think I have it. I've added a few lines to the bottom if you don't want to read the whole thing. Everything else is the same. Thank you so much for all of your help.

Because the terms on the left side are divisible by 3, their squares are all divisible by nine, as (3k)^2=9k^2.
The sum of terms divisible by nine is also divisible by 9: 9m+9n=9(m+n)
Therefore the left side 3*b^2*d^2 is divisible by nine. Removing the three: 9k=3*b^2*d^2 shows that b^2*d^2 is divisible by 3: 3k=b^2*d^2
Therefore all terms are divisible by 3 and the fractions are not irreducible, hence there are no rational solutions to the circle x^2+y^2=3

 

[Chizhek]

(1) A positive integer is a sum of two squares of integers if and only if in its prime factorization every prime of the form 4j+3 (in the following, a BAD prime) appears with an even exponent. This is the "two square theorem" of Fermat.

(2) Just as every positive integer has a unique prime factorization in which every prime appears with a non-negative integer exponent (where only finitely many primes appear with non-zero exponents), so every positive rational number has a unique prime factorization in which every prime appears with an integer exponent, positive, negative, or zero (again only finitely many primes appear with non-zero exponents).

(3) There is also the Fermat's "two square theorem" for rational numbers: a positive rational number is a sum of two squares of rational numbers if and only if in its prime factorization every bad prime appears with an even exponent.
Proof.
Suppose that x = a^2 + b^2, where a and b are rational numbers, not both zero. We can assume that a and b are non-negative; more, we can assume that a = m/k and b= n/k, where m and n are non-negative integers, not both zero, and k is a positive integer; then x = (m^2+n^2)/k^2. In the prime factorization of the numerator m^2 + n^2 every bad prime appears with an even exponent, while in the prime factorization of the denominator k^2 EVERY prime appears with an even exponent; it follows that in the prime factorization of x every bad prime appears with an even exponent.
Conversely, suppose that in the prime factorization of a positive rational number x every bad prime appears with an even exponent. Let m be the product of all factors p^e in the prime factorization of x with positive exponents e, and let n be the product of all q^(-f),
where q^f is a factor of the prime factorization of x with a negative exponent f. Then x = m/n = mn/n^2, where in the prime factorization of mn every bad prime appears with an even exponent, therefore mn is a sum of two squares of integers, whence x is a sum of two squares of rational numbers.

(4) It must be now clear why x^2 + y^2 = 3 has no rational solutions. The same is true of x^2 + y^2 = a, where a = 19, 17/3, 15/13, 22/7, 51, ... You can produce examples by truckload.

Have a nice day. Have fun.

 

[Eval]

It looks like people are making this too complicated (sorry if I am wrong :/). I usually attack these problems using parity. First, I suggest checking x and y parities. In base 2, x and y can only have 2 parities, so this should not be difficult. You will get a result that yields parity of another base (4, specifically). This should tell you what forms x²+y² can take.

I know that the parity route has already been suggested, but the method of going about this seems a bit overdone.