Mathematical Foundations Help?

[rar]

I'm in a Mathematical Foundations course and I'm having trouble figuring out how to do this proof.

I have to prove that (for all x in the set of the Natural Numbers excluding 1) if (there exists a t) where 10 = xt and (there exists an s) where 15 = xs then (there exists a q) where 5 = xq.

Does anyone have any idea of how I could do this? If so, help would be GREATLY appreciated.

[A.J]

Well, this problem can be restated as follows:

If x|a and x|b, then x|gcd(a, b) (for positive integers x, a, and b, naturally).

[edit]solution redacted[/edit]
[edit2]A.J. suggested proof-by-contradiction[/edit]

I hope this helps.

[rar]

A.J @ Mon Mar 29, 2010 9:39 pm wrote:

Well, this problem can be restated as follows:

If x|a and x|b, then x|gcd(a, b) (for positive integers x, a, and b, naturally).

[edit]solution redacted[/edit]
[edit2]A.J. suggested proof-by-contradiction[/edit]

I hope this helps.

Whoa what happened here lol

Alright I'll try it out thanks.

[Brightguy]

Technically you didn't state the universe for s, t, q. But the point is that you can exhibit q using s and t. Hint: 5=15-10.

[rar]

Brightguy @ Mon Mar 29, 2010 10:16 pm wrote:

Technically you didn't state the universe for s, t, q. But the point is that you can exhibit q using s and t. Hint: 5=15-10.

I figured this out before reading your post, so I'm guessing I got it right!


My next question has to do with proving:

If a - b is an element of the Natural Numbers (including 0) and b - a is an element of the Natural Numbers (including 0) then a = b

Advice on proving this?

[Tony]

What's awesome about proves by contradiction is that you simply negate the conclusion that you are trying to prove, and you get a free piece of information.

[Brightguy]

Show a>=b and b<=a.

One line and I miss LaTeX already.

[rar]

I do like proofs by contradiction for that reason. Sometimes I fail to see where it helps though..

[rar]

I ended up with

Assume (looking for a contradiction, so a - b is an element of Naturals, or 0, and b - a same thing, but a != b)

therefore a - b != 0 and b - a != 0
therefore a - b element of naturals (same with b - a)
therefore a - b + b - a element of naturals (adding 2 naturals, still an element of naturals)
therefore 0 element of naturals
however, 0 is NOT an element of naturals (stated above, since a - b != 0 and b - a != 0)
Contradiction

Valid??

[Tony]

Write out all the information that you have, and see what you can do with it

a != b
a - b >= 0
b - a >= 0

what is another way of saying a != b ?

[rar]

and one more question

Prove 2 and 3 are minimal in N - {1} under the partial ordering given by a|b provided (there exists a t in naturals) such that b = at.


So prove if there exists a natural number 't' such that 2 = xt then x = 2

(then the same for 3)

[rar]

Tony @ Mon Mar 29, 2010 10:37 pm wrote:

Write out all the information that you have, and see what you can do with it

a != b
a - b >= 0
b - a >= 0

what is another way of saying a != b ?

Wouldn't that be a - b != 0?

[A.J]

rar @ Mon Mar 29, 2010 9:55 pm wrote:

A.J @ Mon Mar 29, 2010 9:39 pm wrote:

Well, this problem can be restated as follows:

If x|a and x|b, then x|gcd(a, b) (for positive integers x, a, and b, naturally).

[edit]solution redacted[/edit]
[edit2]A.J. suggested proof-by-contradiction[/edit]

I hope this helps.

Whoa what happened here lol

Alright I'll try it out thanks.

[edit] whoops...I just realized that my post was edited for giving too much away...my bad[/edit]

Basically, try assuming the opposite of what you want to prove, and see if you reach a contradictory statement later on.

For example, if you want to prove that there are infinitely many prime numbers, you could start by assuming that there are a finite number of them. So, assume {p_1, p_2, p_3, ..., p_n} are all the prime numbers there are. Now consider the number q = [p_1 * p_2 * p_3 * ... * p_n] + 1. Now q is either prime or composite. Dividing q by any of the primes p_1 -> p_n yields a remainder of 1. Thus, q isn't composite, so it is a prime that isn't listed in the above list (or is factored by a prime not in the above list) contradicting the fact that this list contains all the primes that exist. Thus, there are infinitely many primes.

Try something like that:

code:

1) Assume opposite of intended 2) Look at implications of assumption 3) Find contradiction!