Two Discrete Mathematic Proofs I Need Help With

tuttleforty77
Messages
9
Reaction score
0

Homework Statement


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?

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 = p2 / q2
n * q2 = p2
and this is where I get stumped :(
 
Physics news on Phys.org
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?
 
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:
tuttleforty77 said:
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.
 
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
 
So the square root of 4 is not rational?
 
Can you tell me why each step should be valid?
 
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
 
tuttleforty77 said:
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?
 
  • #10
I'm fairly confident in most of my steps. The only one I'm unsure of is:

tuttleforty77 said:
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

I believe there is a theorem where if x2 is divisible by n then x is divisible by n
 
  • #11
Not coincidentally, that's the step that fails for n=4. :smile: (Well, and the similar step for q)

You are remembering a theorem, but you have only remembered part of it.
 
  • #12
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
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.
 
Back
Top