----------------------------------- rar Mon Mar 29, 2010 9:18 pm Mathematical Foundations Help? ----------------------------------- 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 Mon Mar 29, 2010 9:39 pm RE:Mathematical Foundations Help? ----------------------------------- 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 Mon Mar 29, 2010 9:55 pm Re: RE:Mathematical Foundations Help? ----------------------------------- 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). Whoa what happened here lol Alright I'll try it out thanks. ----------------------------------- Brightguy Mon Mar 29, 2010 10:16 pm Re: Mathematical Foundations Help? ----------------------------------- 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 Mon Mar 29, 2010 10:20 pm RE:Mathematical Foundations Help? ----------------------------------- 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! :D 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 Mon Mar 29, 2010 10:29 pm RE:Mathematical Foundations Help? ----------------------------------- 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 Mon Mar 29, 2010 10:29 pm Re: Mathematical Foundations Help? ----------------------------------- Show a>=b and b= 0 b - a >= 0 what is another way of saying a != b ? ----------------------------------- rar Mon Mar 29, 2010 10:39 pm RE:Mathematical Foundations Help? ----------------------------------- 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 Mon Mar 29, 2010 10:40 pm Re: RE:Mathematical Foundations Help? ----------------------------------- 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 Mon Mar 29, 2010 10:44 pm Re: RE:Mathematical Foundations Help? ----------------------------------- 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). 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! [/code]