# Math Help - Mathematical proofs

1. Originally Posted by Possible actuary
I am having some trouble getting a proof started by proving or disproving.

Given: For every positive irrational number b, there exists an irrational number a with 0<a<b.

I believe that this statement is true. The book suggests that to start the proof by: Let b be a positive irrational number. Consider a=b/2.

I am having a hard time getting this one started.

Thanks
You really should post new questions in a new thread.

here, there is not much to do after the hint the book gave.

For every positive irrational number b, there exists an irrational number a with 0<a<b

Proof:
Let b be any positive irrational number. Consider a = b/2. Note that a<b, and since a is obtained by dividing an irrational number by a rational number, a is irrational. And since a is half of a positive number, we have a>0. Thus we have 0<a<b, where a and b are irrational, as desired
QED

2. Originally Posted by Possible actuary
I just ran the truth table and I want to make sure I have this logic correct. We can prove P=>Q&R by doing a contrapositive by saying ~Q or ~R => ~P because they are logically equivalent.
correct

but keep the statement compact, that is (~Q or ~R) => ~P

3. Did you learn how to manipulate congruence equations without changing them to regular equations with divisibility?

(I edited the last proof i gave, i added a line a<b, make sure you see it)

4. Originally Posted by Jhevon
Did you learn how to manipulate congruence equations without changing them to regular equations with divisibility?
That does not sound familar. We have a foreign lady for our teacher so understanding her is difficult at times. I know she feels that she can't express some thoughts and ideas as well as she needs to. So, she may have tried to tell/teach us that but it sounds jiberish to me.

5. Let me show you an example of what I mean. remember this proof?
Originally Posted by Jhevon

Let n be an integer. Prove that if n is not congruent to 0 (mod 3), then n^2 is congruent to 1 (mod 3).

Proof:

We employ a direct proof. assume n is not congruent to 0 (mod 3), then 3 does not divide (n - 0) = n. therefore, n = 3c + r, where r is the remainder when we divide by 3, thus r = 1 or 2 (note, if r is 0 it means the number was divisible by 3, if r is 3, it means the number is divisible by 3). thus we have 2 cases: (1) n = 3c + 1, and (2) n = 3c + 2

case 1: n = 3c + 1

if n = 3c + 1, then n^2 - 1= (3c + 1)^2 - 1 = 9c^2 + 6c + 1 - 1 = 3(3c^2 + 2c).
since 3c^2 + 2c is an integer, 3|n^2 - 1 and so n^2 is congruent to 1 (mod 3).

case 2: n = 3c + 2

if n = 3c + 2, then n^2 - 1 = (3c + 2)^2 - 1 = 9c^2 + 6c + 4 - 1 = 3(3c^2 + 2c + 1)

since 3c^2 + 2c + 1 is an integer, 3|n^2 - 1, and so n^2 is congruent to 1 (mod 3).

So we see in both cases where n is not congruent to 0 (mod 3), n^2 is congruent to 1 (mod 3).

QED
Let's try to do it by directly manipulating the mod equations.

Let n be an integer. Prove that if n is not congruent to 0 (mod 3), then n^2 is congruent to 1 (mod 3).

We employ a direct proof. We define "n = x (mod 3)" to be n is congruent to x (mod 3). We define "n != x (mod 3)" to be n is not congruent to x (mod 3).

Now assume n != 0 (mod 3). Then n = 1 (mod 3) or n = 2 (mod 3).

Case 1: n = 1 (mod 3)
if n = 1 (mod 3) then by squaring both sides we obtain n^2 = 1^2 (mod 3), that is n^2 = 1 (mod 3)

Case 2: n = 2 (mod 3)
if n = 2 (mod 3) then by squaring both sides we obtain n^2 = 2^2 (mod 3), that is n^2 = 4 (mod 3). Since in a modulus equation, we can add or subtract the modulus as much as we want, this means that n^2 = 4 - 3 (mod 3), that is n^2 = 1 (mod 3).

So we see in both possible cases, n^2 = 1 (mod 3), as desired.

QED

6. I understand it up to this point where then n=1 (mod 3) or n=2(mod3). I don't know how you go those.

Originally Posted by Jhevon
Then n = 1 (mod 3) or n = 2 (mod 3).

Case 1: n = 1 (mod 3)
if n = 1 (mod 3) then by squaring both sides we obtain n^2 = 1^2 (mod 3), that is n^2 = 1 (mod 3)

Case 2: n = 2 (mod 3)
if n = 2 (mod 3) then by squaring both sides we obtain n^2 = 2^2 (mod 3), that is n^2 = 4 (mod 3). Since in a modulus equation, we can add or subtract the modulus as much as we want, this means that n^2 = 4 - 3 (mod 3), that is n^2 = 1 (mod 3).

So we see in both possible cases, n^2 = 1 (mod 3), as desired.

QED

7. Originally Posted by Possible actuary
I understand it up to this point where then n=1 (mod 3) or n=2(mod3). I don't know how you go those.
well, remember modulus equations deal with a lot with remainders.

remember, when we say n = 2 (mod 3) for instance we mean, 3|n-2 what that actually means is that if we divide n by 3 the remainder is 2. (do you see why?)

so for mod 3 there are three possibilities:

n = 0 (mod 3)
n = 1 (mod 3)
n = 2 (mod 3)

since when dividing by 3, there can only be three possible remainders, either you have a remainder of 0 (in this case, n is divisible by 3) or you have a remainder of 1 or 2 (in these cases, n is not divisible by 3)

so if i assume n is not congruent to 0 mod 3, that is, it is not divisible by 3, then n has to be one of the other 2

got it?

8. Whey you said, We define "n = x (mod 3)" to be n is congruent to x (mod 3). We define "n != x (mod 3)" to be n is not congruent to x (mod 3). Did you mean n! is not congruent to x? If so that makes sense other wise I don't understand that part. Why did you pick n! = x (mod 3)?

I understand the remainder concept that mod 3 has 3 possibilities.

9. Originally Posted by Possible actuary
Whey you said, We define "n = x (mod 3)" to be n is congruent to x (mod 3). We define "n != x (mod 3)" to be n is not congruent to x (mod 3). Did you mean n! is not congruent to x? If so that makes sense other wise I don't understand that part. Why did you pick n! = x (mod 3)?

I understand the remainder concept that mod 3 has 3 possibilities.
no what i said there was not a part of the proof, i did that for you. when i said n != x (mod 3), i did not mean n!, notice that the "!" was attached to the equal sign, not the n. i was just making you aware of my notation. is used "!=" to mean "not congruent" since i don't have the symbol for not congruent (which is the equivalent sign with a strike through it". and i used "=" for congruent since i don't have the symbol for congruent (which is the equivalent sign).

10. Catching on. Okay, we really didn't go through modulus that well. How is that we can add and subtract modulus as much as we want?

11. Originally Posted by Possible actuary
Catching on. Okay, we really didn't go through modulus that well. How is that we can add and subtract modulus as much as we want?
well, as for the rigorous mathematical proof that shows we can do this in all cases, i don't have (or know) that. so let's just try to use common sense to figure this out--since math is a lot about common sense well, not all of it, but a lot of it

okay,

let's use mod 3 as an example again.

let's say you got n = 4 (mod 3). i claim that is the same as saying n = 4 - 3 (mod 3) which is n = 1 (mod 3)

so now let's think about it. n = 4 (mod 3) means that when we divide n by 3 we get a remainder of 4. but wait, if there is a remeainder of 4, that means we could have gotten another 3 out of it, and be left with a remainder of 1. ah, well if that's true, then n = 1 (mod 3) since we can "take out" a modulus out of 4, it is the same as subtracting the modulus.

so basically, once we go in excess to the point where we can take the modulus out of the remainder, it means we might as well have divided into the remainder more, leaving a smaller remainder. so that's the common sense answer

12. ok got it

13. Originally Posted by Possible actuary
ok got it
and of course this goes in the opposite way. we could rewrite n = 4 (mod 3) as n = 7 (mod 3) since essentially they are the same thing. both of them just mean when you divide n by 3 the remainder is 1. we can just write it in different ways for convenience

Page 2 of 2 First 12