# Proving Total Order

1. Nov 23, 2008

### Sharps

1. The problem statement, all variables and given/known data
Let n be a positive integer and let D(n) be the set of all positive integers d such that d divides n. For example, D(10)={1,2,5,10}. It's easily shown that the divides relation (xRy if x divides y) is a partial ordering on D(n), but for what n is the D(n) totally ordered?

2. Relevant equations

3. The attempt at a solution
I've already verified that for all n, D(n) is a partial ordering. I've also made the observation that, for all n=2^s + 3^t where s,t are natural numbers D(n) is totally ordered. However, I'm having a difficult time proving this. For nonzero s and t, n is prime and D(n) is clearly totally ordered. For the cases where s=0 or t=0, it's more difficult to prove. Any suggestions? Is this the right way to go about this?

2. Nov 23, 2008

### Hurkyl

Staff Emeritus
Really?

You've already written a counterexample in this thread.

3. Nov 23, 2008

### Sharps

That's my mistake....typo. I meant to say that all prime numbers can be written as a 2^s + 3^t. Also, I've found a counterexample to that criterion, namely 125. So it's back to the drawing board.

What I know:

1.) For all n such that n is prime, D(n) is totally ordered.
2.) Not much else. I've written D(n) up to n=32, and found that the following non-prime n also give totally ordered sets:

4, 8, 9, 16, 25, 27, 32

but have no idea how to find some unifying criteria now.

Arrgh! I understand that once I find a criteria, I must show that for all a,b in D(n) a/b or b/a, but I need to find that criteria first.

4. Nov 23, 2008

### Hurkyl

Staff Emeritus
Well, this is all about divisibility, right? We know a lot about divisibility -- the fundamental theorem of arithmetic being the most important structural fact.

5. Nov 23, 2008

### Sharps

Yah, I was thinking about that. I know that all natural numbers greater than one have a unique prime factorization. So, I suppose that if D(n) contains 2 primes, they will not divide one another. Can I go from there?

6. Nov 23, 2008

### Sharps

I got it.

Any n with unique prime factorization containing only one prime factor (not counting its multiplicities) will be totally ordered.

Nice.

7. Nov 24, 2008

### Hurkyl

Staff Emeritus
Yep, that sounds right! And all of your examples are, in fact, prime powers!