Thread: Well Ordering principle

Hi all,

I am having problem of trying to apply the well ordering principle. I know what it is, but i find it difficult to apply it. If anyone knows of any good website that has a lot of useful information, please do let me know. I do not know where to start working on a solution, and i am terribly lost. Below are my questions:

Qns 1:
Use the well-ordering principle to prove that if a and b are positive integers, then there exist integers u,v such that gcd(a,b) = ua+vb.

Qns 2:
Let a, b be integers, not both zero, and d be a positive integer. Prove that d=gcd(a,b) iff

(i) d|a, d|b and
(ii) for all c element of integers, if c|a and c|b, them c|d.

Originally Posted by shaoen01

Hi all,

I am having problem of trying to apply the well ordering principle. I know what it is, but i find it difficult to apply it. If anyone knows of any good website that has a lot of useful information, please do let me know. I do not know where to start working on a solution, and i am terribly lost. Below are my questions:

Qns 1:
Use the well-ordering principle to prove that if a and b are positive integers, then there exist integers u,v such that gcd(a,b) = ua+vb.

Given positive integer a and b there exists integers q and r such that a=qb+r where 0<=r<b. You need this fact. Now let (a,b) = {ax+by|x,y in Z}. The set (a,b) has a positive number, by well-ordering principle choose the smallest positive number d. Define (d) = {dz|z in Z}. Now claim that (a,b) = (d) by showing each is a subset of the other (this is where you use the first line of this post). Once you show (d) = (a,b) the rest is simple, since a in (d) it means d divides a, since b in (d) it means d divides b. If c is a divisor of a and b then c is a divisor of ax+by thus c is in (a,b) so c is in (d) thus d divides c, which proves d the greatest common divisor.

Induction and Well-Ordering are equivalent, so if you can't figure out how to use well-ordering you should be able to use induction. However it might be easier to do some questions with well-ordering.

ThePerfectHacker:
Thanks for the help! Can i ask did you use the variable b on purpose in "a=qb+r"? Is there any special significance? Can i ask if the question writes gcd(a,b), is it safe to assume b<a? Thanks

Originally Posted by shawn

Induction and Well-Ordering are equivalent, so if you can't figure out how to use well-ordering you should be able to use induction. However it might be easier to do some questions with well-ordering.

Is there anyway to know in which situation i should use well-ordering or mathematical induction. I have some problems with understanding strong mathematical induction. Thanks

Originally Posted by shaoen01

Is there anyway to know in which situation i should use well-ordering or mathematical induction. I have some problems with understanding strong mathematical induction. Thanks

You can use either in any case...they are equivalent Although Well-ordering is usually harder to do than strong induction, but for some questions it just makes more sense.

Here's a little comparison of regular and strong induction that might help you understand it better:
Strong induction versus weak induction

And here's a link that might help clarify the well-ordering principle: Well Ordering Principle

Hope it helps.

Shawn:
Thanks for the links, based on my understand strong mathematical induction requires the step of proving by introducing another variable. So instead of one variable b, we have another additional variable a. So if "a value"<=a<b, so if all values of a is true, then b will also be true considering that b>a right? Hope that makes some sense ...

Originally Posted by shaoen01

Shawn:
Thanks for the links, based on my understand strong mathematical induction requires the step of proving by introducing another variable. So instead of one variable b, we have another additional variable a. So if "a value"<=a<b, so if all values of a is true, then b will also be true considering that b>a right? Hope that makes some sense ...

Yes, you introduce another "dummy variable"...in your inductive step you have to assume that it is true for all values of k before k+1, not just for k.