What does "non-decreasing" mean in relation to this definition about the prime factorization of numbers?

Question

I'm reading a text on discrete math and came across a theorem which states:

"Every integer greater than 1 can be written uniquely as a prime or as the product of two or more primes where the prime factors are written in order of nondecreasing size."

I understand writing a composite as a prime factorization, no prob. But what is the relevance of "written in order of nondecreasing size"?

What does it mean and how is it useful?

Thanks!

Answer 1

Without this restriction the factorization wouldn't be unique -- most composite numbers would have several different factorizations that simply listed the same prime factors in different orders.

In order to be able to say there is a unique prime factorization, we need to declare that one of these different orders for the prime factors is the "right" one and the others don't count.

There's nothing particularly deep about requiring non-decreasing order of the factors in particular, except that it happens to be a choice of "right" order that is (a) easy to describe and (b) easy to see picks out exactly one of the many possible reorderings of every list of prime factors.

---

Alternatively one could also state the prime factorization theorem as

For every positive integer $N$, there is exactly one multiset of primes whose product is $N$.

That's closer to the intuitive content of the theorem, except that multisets are slightly discriminated against by most mathematicians' preferences about how to express things. Things that can be expressed as sets or ordered sequences are usually more in favor.

Answer 2

They're saying that order doesn't matter. For example, $30 = 2 \cdot 3 \cdot 5 = 2 \cdot 5 \cdot 3$, but we don't want this to mean prime factorization isn't unique. And it has to be "non decreasing" instead of "increasing", because some numbers have more than one factor of the same prime.

Answer 3

That definition probably could be a bit better, but it does work.

"Every integer greater than 1 can be written uniquely as a prime or as the product of two or more primes where the prime factors are written in order of nondecreasing size."

There are two uniquenesses (?!) that are important here:

• The specific set of primes that comprise the prime factorization of a given number greater than 1 is unique.
• Ordering said set or primes in non-decreasing order produces a listing of those primes that is different from any other ordering. That is to say, unique.

The sentence states that "[e]very integer greater than 1 can be written uniquely as a prime or as the product of two or more primes where the prime factors are written in order of nondecreasing size."

This captures both uniquenesses I listed, but it does spend a disproportionate amount of the sentence talking about a (relatively) trivial reordering of the numbers -- which one can do by virtue of the commutative property of multiplication.

The more important uniqueness to understand here is the first one: that the set of primes that factor a given number is unique. A prime factorization of 12 consists of two 2's and one 3, period. No other combination of primes factors 12.

Answer 4

$$ 130635 = 2\cdot7\cdot7\cdot31\cdot43 $$

$$ 130635 = 7\cdot2\cdot43\cdot31\cdot7 $$

The first expression above is non-decreasing order. The second is not.

I'd write non-decreasing with a hyphen or without, thus: nondecreasing. I wouldn't write "non decreasing" as if "non" were a separate word rather than a prefix. But I've noticed persons of youngness doing that. I wonder how English is taught nowadays?