Question

Prove that there is no positive rational number a such that a^2 = 3. You may assume that a positive integer can be written in one of the forms 3k, 3k + 1, 3k + 2 for some integer k. Prove that if the square of a positive integer is divisible by 3, then so is the integer. Then use a similar proof as for sqrt(2).

Answer 1

take square root on both side
a = square root 3
a = 1.73 which is not a rational number

Answer 2

Hmm I remember the sqrt2 proof :)
That's a fun one.

Answer 3

This is from Lang's Basic Mathematics by the way. So I'm looking for something around that level. Nothing too over my head.

Answer 4

This proof relies on fermats infinite descent

Answer 5

\(a^2 = 3\)

Step1 :
By way of contradiction, suppose that \(a\) is rational and is equal to \(\dfrac{x}{y}\) for some two "positive" integers.
\(\left(\dfrac{x}{y}\right)^2 = 3\)

Answer 6

Okay good! This looks similar to the stuff presented in the book.

Answer 7

Step2 :
\(x^2=3y^2\)

This means \(x^2\) is divisible by \(3\). It follows that \(x\) is also divisible by \(3\).
Say, \(x = 3x_1\). Notice that \(\color{red}{x_1\text{ is less than }x}\).
\((3x_1)^2 = 3y^2\)

Answer 8

good so far ?

Answer 9

Yes. I was able to get steps 1 and 2 on my own, though I wasn't sure I was doing them correctly. After that is where it gets messy for me.

Answer 10

The logic in next steps is really beautiful

Answer 11

Again, this is proof by fermat's infinite descent. Has nothing to do with your textbook proof by contradiction

Answer 12

Well, I don't know what that means, but hopefully I'll be able to follow it.

Answer 13

Step3 :
\((3x_1)^2 = 3y^2 \\ \implies 3{x_1}^2=y^2\)

This means \(y^2\) is divisible by \(3\). It follows that \(y\) is also divisible by \(3\).
Say, \(y = 3y_1\). Notice that \(\color{red}{y_1\text{ is less than }y}\).
\(3{x_1}^2 = (3y_1)^2\)

Answer 14

I'm sure you will get it easily :)

Answer 15

see if the first 3 steps make sense

Answer 16

That makes sense!

Answer 17

What do you observe from first 3 steps

Answer 18

\(x_1\lt x\) and \(y_1\lt y\)

yes ?

Answer 19

Yes.

Answer 20

That is true.

Answer 21

Good. Lets do two more steps before concluding

Answer 22

Step4 :
\(3{x_1}^2 = (3y_1)^2 \implies {x_1}^2 = 3y_1^2\)

This means \({x_1}^2\) is divisible by \(3\). It follows that \(x_1\) is also divisible by \(3\).
Say, \(x_1 = 3x_2\). Notice that \(\color{red}{x_2\text{ is less than }x_1}\).
\((3{x_2})^2 = 3{y_1}^2\)

Answer 23

Notice that \(x_2\lt x_1\lt x\)

Answer 24

Continuing the above steps, we get an infinite "decreasing" sequence of \(x_i\)'s and \(y_i\)'s

Answer 25

\[\ldots x_4\lt x_3\lt x_2\lt x_1\lt x\]
and
\[\ldots y_4\lt y_3\lt y_2\lt y_1\lt y\]

Answer 26

We're almost done. Still with me ? :)

Answer 27

Sort of haha.

Answer 28

It seems to make sense. Just kind of a weird.

Answer 29

thing to do.

Answer 30

We're done actually. We just need to conclude

Answer 31

Before concluding, let me ask you a simple question.

Answer 32

what is your favorite large positive integer ?

Answer 33

Sorry, I was going back and re-reading through those steps.

Answer 34

5

Answer 35

that works, but pick something that is really large..

Answer 36

55555

Answer 37

Okay I'm confused on step 3 actually.

Answer 38

At the start of step3, I have just cancelled 3 both sides of the equation

Answer 39

How did you do that on the left side?

Answer 40

Never mind. I figured it out haha.

Answer 41

Nice :)

Answer 42

Now take your favorite integer : 55555

Answer 43

So you would continue doing that same pattern forever, but how would that prove it?

Answer 44

Start with 55555,
can you construct a "decreasing" sequence of positive integers ?

Answer 45

Or rather how would that prove it's true.

Answer 46

I'm explaining you the exact same thing... :)

Answer 47

For example :

...., 3 < 100 < 4956 < 55555

Answer 48

Is that sequence really infinite ?

Answer 49

Well no. Because eventually you would hit zero.

Answer 50

BINGO!

Answer 51

Starting with some finite positive integer, you can NEVER construct an "infinite" decreasing sequence of positive integers.

Answer 52

However we have got two "infinite" decreasing sequence of positive integers earlier :

\[\ldots x_4\lt x_3\lt x_2\lt x_1\lt x\]
and
\[\ldots y_4\lt y_3\lt y_2\lt y_1\lt y\]

Answer 53

Since \(x\) and \(y\) are finite positive integers, above sequences cannot be infinite, yes ?

Answer 54

WOAH.

Answer 55

Thats it! You have learned fermat's infinite descent !

Answer 56

We have arrived at a contradiction. Therefore we conclude that our initial assumption, \(a\) is rational, is wrong.

Answer 57

That ends the proof

Answer 58

So that could be used on any similar problem involving a square right?

Answer 59

Absolutely! fermat's infinte descent hinges on this fact :

The set of positive integers has a lower bound : 1.
We cannot construct an "infinite" sequence of decreasing positive integers.

Answer 60

But hold on, if you had say a^2 = 9

\[x^2 = 9y^2\]
\[ x = 9x_{1}\]
\[(9x_{1})^2 = 9y^2\]

Then you could continue on for infinity right? And we know the sqrt(9) is 3.

Answer 61

You made a mistake. \(x^2\) is divisible by \(9\) need not imply that \(x\) is divisible by \(9\).

Answer 62

really good question though!

Answer 63

For example :
\(3^2\) is divisible by \(9\). But \(3\) is not divisible by \(9\).

Answer 64

Your statement is true for primes though:

If \(x^2\) is divisible by \(a\) and \(a\) is prime, then \(x\) is divisble by \(a\).

Answer 65

So you don't get an infinite sequence :
\(x^2 = 9y^2\)

we can only conclude that \(x=3x_1\) from above equation.

Answer 66

But why is that?

Answer 67

what do you mean ?

Answer 68

Ohhhh.

Answer 69

I see the error.

Answer 70

Feel like doing another proof using fermat's infinite descent ?

Answer 71

I'd love to go through another one.

Answer 72

let me find a neat problem..

Answer 73

Here it is :

prove \(\large \sqrt[3]{2}\) is irrational

Answer 74

I have another question though. The method given in the book to find prove a^2 = 2 involved showing that a/b was an even number over an even number when you tried to put it in the lowest form.

Answer 75

And I was just wondering if you could use that kind of proof for an odd number. Because I was getting lost trying.

I really like the Fermat's Infinite Descent though.

Answer 76

http://www.math.utah.edu/~pa/math/q1.html

Answer 77

That link has the proof that your textbook is talking about

Answer 78

Yes. So that won't work for anything except for an even number?

Answer 79

It works for every irrational number

Answer 80

Including the one we did earlier?

Answer 81

Yes, lets do a quick proof using simple contradiction for \(\sqrt{3}\)

Answer 82

So

\[a^3 = 2\]

\[(\frac{ m }{ n })^3 = 2\]

Answer 83

\[m^3 = 2n^3\]

Answer 84

are you trying fermat's infinite descent ?

Answer 85

Oh I was going to. I guess you could use either?

Answer 86

Sorry if that's a dumb question. I'm kind of new to anything involving proofs.

Answer 87

You could use either. Infinite descent is more powerful. Ppl don't use infinite descent for simple irrationalit proofs like these...

Answer 88

I have used infinite descent here just for some practice haha

Answer 89

Are you facing any problem proving the irrationality of \(\sqrt{3}\) using ur textbook method ?

Answer 90

Yes. Hahaha.

Answer 91

Though I feel like your method looks a bit more impressive haha.

So \[a^2 = 3\]
\[a = \frac{ m }{ n }\]
\[m^2 = 3n^2\]

Answer 92

Thus, m^2 is odd?

Answer 93

Thus, m^2 is divisible by 3

Answer 94

That means m is also divisible by 3, let m = 3k

Answer 95

okay

Answer 96

plug that in the equation and get :
(3k)^2 = 3n^2

3k^2 = n^2

This means n is also divisible by 3

Answer 97

So we see that both m and n are divisible by 3

Answer 98

But haven't you assumed in the start that m and n have no common factors ?