# Homework Help: Number Theory WOP

1. Feb 15, 2012

### dashhh

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 $\in$ 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 $\in$ 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$_{o}$, what value would be the comparing s?

2. Feb 15, 2012

### tiny-tim

welcome to pf!

hi dashhh! welcome to pf!
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

3. Feb 15, 2012

### HallsofIvy

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

4. Feb 15, 2012

### dashhh

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$_{o}$<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
5. Feb 16, 2012

### tiny-tim

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