Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Number Theory WOP

  1. Feb 15, 2012 #1
    I've just begun number theory and am having a lot of trouble with proofs. I think I am slowly grasping it, but would appreciate some clarification or any tips on the following please.

    Show that if a and b are positive integers, then there is a smallest positive integer of the form a - bk, k [itex]\in[/itex] Z

    The answer given is:
    Let a and b be positive integers and let

    S = {n:n is a positive integer and n = a - bk for some k [itex]\in[/itex] Z}

    Now S is nonempty since a + b = a - b(-1) is in S. By the well ordering principle, S has a least element.

    So, are they implying that k is the smallest element? or a - b(-1) as a whole is the smallest element?

    I'm unsure as to how they are showing that it is the smallest element though. Given that either of the two options above would be S[itex]_{o}[/itex], what value would be the comparing s?
  2. jcsd
  3. Feb 15, 2012 #2


    User Avatar
    Science Advisor
    Homework Helper

    welcome to pf!

    hi dashhh! welcome to pf! :wink:
    no, they're not saying anything about the smallest element

    they're only saying that a smallest element exists

    that's all the well ordering principle proves :smile:
  4. Feb 15, 2012 #3


    User Avatar
    Science Advisor

    Neither. They are saying that a- bk, for that particular k, is the smallest element.

  5. Feb 15, 2012 #4
    It would seem you are contradicting one another?
    Or am i confused all over again?

    EDIT: My only understanding of WOP is that you need S[itex]_{o}[/itex]<S
    This is all we have learnt so far, so based on the fact we should be able to understand (at least vaguely) what is going on with what we are supposed to know, I don't see how this should make sense yet. Is it due to being lacking in the area of proofs?

    I should also mention I have actually looked at other resources etc, not just lecture notes.
    Last edited: Feb 15, 2012
  6. Feb 16, 2012 #5


    User Avatar
    Science Advisor
    Homework Helper

    from http://en.wikipedia.org/wiki/Well-ordering_principle

    the well-ordering principle states that every non-empty set of positive integers contains a smallest element​

    it doesn't say what it is, nor how to find it, it only says that it exists
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook