Proving Total Order of D(n) Homework

[Sharps]

Homework Statement

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?

Homework Equations

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?

 

[Hurkyl]

For nonzero s and t, n is prime

Really?

For the cases where s=0 or t=0

You've already written a counterexample in this thread.

 

[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.

 

[Hurkyl]

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

 

[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?

 

[Sharps]

I got it.

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

Nice.

 

[Hurkyl]

I got it.

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

Nice.

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