Two Discrete Mathematic Proofs I Need Help With

1. Sep 9, 2010

tuttleforty77

1. The problem statement, all variables and given/known data
Prove that at least one of 2*10500 + 15 or 2*10500 + 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?

2. Relevant equations
n/a

3. 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 = p2 / q2
n * q2 = p2
and this is where I get stumped :(

2. Sep 9, 2010

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?

3. Sep 9, 2010

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*10500+15 = 20*10499+15 = 5[4*10499+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.

Last edited: Sep 9, 2010
4. Sep 9, 2010

Dick

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.

5. Sep 10, 2010

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 = p2 / q2
q2n = p2
so p is a multiple of n
so we can say p = an

Therefore: p2 = a2 n2

q2n = a2 n2
q2 = (a2n2)/n
q2 = n(a2)
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

6. Sep 10, 2010

Office_Shredder

Staff Emeritus
So the square root of 4 is not rational?

7. Sep 10, 2010

Hurkyl

Staff Emeritus
Can you tell me why each step should be valid?

8. Sep 10, 2010

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 = p2 / q2 <--Squaring both sides
q2n = p2 <--Multiplying both sides by q2
so p is a multiple of n <--I believe p2 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: p2 = a2 n2 <--Calculating p2

q2n = a2 n2 <--Replacing p2in the equation
q2 = (a2n2)/n <--dividing both sides by n
q2 = n(a2) <-- the end result, where I believe q2 must now be divisible by n, and thus q is aw well

9. Sep 10, 2010

Hurkyl

Staff Emeritus
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?

10. Sep 10, 2010

tuttleforty77

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

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

11. Sep 10, 2010

Hurkyl

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

12. Sep 10, 2010

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!

13. Sep 10, 2010

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