Two Discrete Mathematic Proofs I Need Help With

[tuttleforty77]

Homework Statement

Prove that at least one of 2*10⁵⁰⁰ + 15 or 2*10⁵⁰⁰ + 16 is not a perfect square. Can you say specifically which one is not a perfect square?

Consider the proof that √2 is irrational. Could you repeat the same proof for √3? What about √4?

Homework Equations

n/a

The Attempt at a Solution

For the first problem I have no clue where to start. I'm thinking it has something to do with the +15 and +16 at the end, but I'm not 100% sure on that.

For the second one I know that you can prove that the √n is irrational for all integers that are not a perfect square, I'm just not sure how to prove it. Would it be similar to the proof of the √2 being irrational, just tweaked a bit because of the variable n?

√n = p / q (where p / q is expressed in its lowest terms)
n = p² / q²
n * q² = p²
and this is where I get stumped :(

 

[tuttleforty77]

So I think I figured out the first problem. You can prove that one of them is in fact not a perfect square because the only two perfect squares that differ by 1 are the numbers 1 and 0. Right?

 

[jgens]

Hopefully you can prove that at least one of them is not a perfect square. To show which one is definitely not a perfect square, note that

2*10⁵⁰⁰+15 = 20*10⁴⁹⁹+15 = 5[4*10⁴⁹⁹+3]

And see if you can make something work with that.

For the second problem, try starting with 3 before considering n. To prove the case for n you're going to want to use the fundamental theorem of arithmetic.

 

[Dick]

So I think I figured out the first problem. You can prove that one of them is in fact not a perfect square because the only two perfect squares that differ by 1 are the numbers 1 and 0. Right?

Right. To figure out which one is definitely not a perfect square, you might want to figure out what they are mod 4. For the second one you should review the proof sqrt(2) is irrational and see if it extends.

 

[tuttleforty77]

I think I may have figured it out, but I am so sleep deprived at this point I'm not positive I didn't mess up algebra at some point.

Assume \sqrt{n} is rational
\sqrt{n} = p / q
n = p² / q²
q²n = p²
so p is a multiple of n
so we can say p = an

Therefore: p² = a² n²

q²n = a² n²
q² = (a²n²)/n
q² = n(a²)
from this q is a multiple of n
but if they were both multiple’s of n, that contradicts our original assumption that p/q was in its lowest terms

 

[Office_Shredder]

So the square root of 4 is not rational?

 

[Hurkyl]

Can you tell me why each step should be valid?

 

[tuttleforty77]

sorry, I should have included for any integer n, \sqrt{n} is irrational if and only if n is not a perfect square.

As for validating each step:
Assume \sqrt{n} is rational
\sqrt{n} = p / q <--Definition of an integer
n = p² / q² <--Squaring both sides
q²n = p² <--Multiplying both sides by q²
so p is a multiple of n <--I believe p² must be divisible by n, and thus so must p
so we can say p = an <--defining a new variable for p in terms of n
Therefore: p² = a² n² <--Calculating p²

q²n = a² n² <--Replacing p²in the equation
q² = (a²n²)/n <--dividing both sides by n
q² = n(a²) <-- the end result, where I believe q² must now be divisible by n, and thus q is aw well

 

[Hurkyl]

sorry, I should have included for any integer n, \sqrt{n} is irrational if and only if n is not a perfect square.

You never use the hypothesis "n is not a perfect square" in the argument that follows -- so if it's valid, it will prove that sqrt(4) is irrational.

So, this gives you something you can do yourself without relying on others to point out your mistakes -- check each rationale and see which one doesn't work if n happens to be a perfect square.

How would you rank your confidence in the validity of each step?

 

[tuttleforty77]

I'm fairly confident in most of my steps. The only one I'm unsure of is:

so p is a multiple of n <--I believe p² must be divisible by n, and thus so must p
so we can say p = an <--defining a new variable for p in terms of n

I believe there is a theorem where if x² is divisible by n then x is divisible by n

 

[Hurkyl]

Not coincidentally, that's the step that fails for n=4. (Well, and the similar step for q)

You are remembering a theorem, but you have only remembered part of it.

 

[tuttleforty77]

I'm going to have to find this theorem, i can't remember the rest for the life of me. However I think a little sleep would help clear my head out, so I will be back to work on this in a few hours. I greatly appreciate you steering me in the right direction!

 

[tuttleforty77]

Yay sleep, i believe this proof will get me to the correct answer.

The part of the theorem I forgot last night was that if x is prime and x | n² then x | n

By the way the theorem was euclid's first theorem(euclid's lemma), of which i use a corollary of in this proof.

The corollary is: If a and c are relatively prime, then c|ab implies c|b.

Anyway, here's my proof now:

Assume √(n) = a / b where a and b are relatively prime and b ≠ 1 (a non-integer rational number).

n = a2 / b2
nb2 = a2

From this we can conclude that because a2 is an integer multiple of b2, b2 divides a2.
For any two integers, if b2 divides a2 then b divides a.
Logically, if the two numbers are relatively prime and b divides a, then b must be 1.
However, this contradicts with our above statement that b ≠ 1.
Therefore, √(n) cannot equal any rational non-integer rational number.

Since the realm of real numbers contains only irrational, rational and integer numbers, and we have eliminated the non-integer rational numbers, the √(n) must therefore be either irrational or an integer. The only way √(n) will be an integer is if n is a perfect square.