Can a number have different prime factorizations?

Question

Given a number $n$, can $n$ be decomposed into different prime factors? For example:

$c\times d = n$, where $c$ and $d$ are both prime factors.

Could there also be a $e\times f = n$ where $e$ and $f$ are also prime and do not equal $c$/$d$?

Answer 1

No:

We first need a Lemma: if $p$ is prime and $p$ divides $ab$ then $p$ divides $a$ or $p$ divides $b$.

Proof: Assume that $a$ and $n$ are relatively prime and that $n$ divides $ab$. By Bezout's identity, there exist $r$ and $s$ such that $ra + sn = 1$ which upon multiplying by $b$ yields $rab + snb = b$. $n$ divides $ab$ (by hypothesis) which itself divides the first term on the left. Further, $n$ divides the second term on the left. Therefore, $n$ divides $b$. To prove the lemma, take $p = n$ and note that either $p$ divides $a$ (in which case we're done) or $p$ is coprime to $a$ (as it is prime) and therefore by the above discussion $p$ divides $b$.

Now to answer your question:

Assume by way of contradiction that $n = p_1...p_n = q_1...q_n$ with the $p_i$ and $q_i$ here not necessarily distinct and further assume without loss of generality that $p_1<p_2<...<p_n$, $q_1<q_2<...<q_n$ and that $p_1<q_1$. $p_1$ clearly divides $n$. Thus, by our lemma above, $p_1$ divides $q_i$ for some $i$. But $p_1<q_i$ are both prime (therefore they are coprime) so that $p_1 = 1$, a contradiction.

Answer 2

As others have pointed out, this is impossible in the integers. It may not be obvious that this is a special property of the integers. There are structures with similar notions of primes and of factorization where prime factorizations are not unique.

For a simple example, consider the set $\{1, 4, 7, 10, 13, 16, \ldots\}$. If we think about multiplication only in this set, 4 is prime, because we have left out 2. The number 28 factors uniquely into $4 \times 7$. But 100 has two different factorizations: $$100 = 4 \times 25 = 10 \times 10$$ and none of 4, 10, or 25 factors further in this system.

For a better example, consider the set of numbers of the form $$a + b \sqrt{-5}$$ where $a$ and $b$ are integers. This set supports addition as well as multiplication. In this system, the number 6 has two different factorizations into prime elements:

$$6 = 2 \times 3 = (1 + \sqrt{-5})(1 - \sqrt{-5})$$

This is the standard go-to example that you will find in almost any basic algebraic number theory textbook. Occasionally you might find the example of $2 \times 5 = (\sqrt{10})^2$, but that presents at least one more pedagogical difficulty than the $1 \pm \sqrt{-5}$ example.

Great mathematicians like Leonhard Euler were unaware this sort of thing is possible, and it derailed one of the earliest attempts at a proof of the Fermat conjecture.

And so mathematicians developed the concept of ideals. In the domain mentioned just now, we see that although the number 6 has two distinct factorizations, the ideal generated by 6 has a unique factorization into prime ideals:

$$\langle 6 \rangle = \langle 2, 1 + \sqrt{-5} \rangle^2 \langle 3, 1 - \sqrt{-5} \rangle \langle 3, 1 + \sqrt{-5} \rangle.$$

I doubt you have studied ideals yet, but something tells me you would have done so soon regardless.

Answer 3

I think you are ready to start learning the difference between prime numbers and irreducible numbers. What I'm going to say in this answer will seem very basic to lots of other people here, but just a couple of years ago I did not fully understand this stuff. Not that I fully understand it now, but I understand it much better than before.

I will assume that you understand that $-1$ and $1$ are units, not primes, and certainly not composites. These are the units of "the integers," which consist of the positive integers $1, 2, 3, \ldots$; $0$; and the negative integers $-1, -2, -3, \ldots$ For short, we write $\mathbb{Z}$.

Then, given a number $p \in \mathbb{Z}$ other than $-1, 0, 1$, and some numbers $a, b$ also in $\mathbb{Z}$, we say that

• $p$ is irreducible if for any choice of $a, b$ such that $p = ab$, either $a$ or $b$ is a unit, but not both. For example, $p = -7$ is irreducible, since in $1 \times -7 = -1 \times 7 = -7$ both $1$ and $-1$ are units, and there is no other choice of $a, b$ such that $ab = -7$.
• $p$ is prime if whenever $p \mid ab$, then also one or both of $p \mid a$, $p \mid b$ hold true. For example, $-7$ is prime, and we see that, for example, $-7 \mid 28$, $28 = 2^2 \times 7$, and $-7 \mid 7$.

To further reinforce this point, consider $-14$, which is neither irreducible nor prime. It's easy enough to see that it is irreducible: $-14 = -2 \times 7 = 2 \times -7$, and neither of those expressions have units. And we see that it is not prime, for $-14 \mid 28$, $28 = 2^2 \times 7$, but $-14 \nmid 2^2$, $-14 \nmid 7$ either.

It's really important to note that in $\mathbb{Z}$, primes and irreducibles are the same, so a number having two distinct factorizations into primes is by definition impossible. $-2 \times 7$ does not count as a distinct factorization of $-14$ apart from $2 \times -7$ because all we've done is multiply both factors by the unit $-1$.

I was not going to mention $\mathbb{Z}[\sqrt{-5}]$, since that might be getting quite a bit ahead in your book. But since MJD mentioned it, I might as well remark that some numbers in that domain have distinct factorizations into irreducibles. But some irreducibles in that domain are also prime.

And furthermore, ideals generated by numbers with distinct factorizations have unique factorizations into ideals. But that's really getting ahead in your book.

At this point it might be much easier for you to understand domains that have numbers that are prime but not irreducible. For example, the finite domain $0, 1, 2, 3, 4, 5, 6, 7, 8, 9$, which is sometimes notated $\mathbb{Z}_{10}$.

In $\mathbb{Z}_{10}$, addition and multiplication are adjusted so that the results stay in the domain, e.g., $4 + 7 = 1$. If you remember the multiplication tables you learned as a child, you will see that in this domain, $5$ is prime, and also "composite:" $5 = 3 \times 5 = 5^2 = 7 \times 5 = 9 \times 5$.

Answer 4

It depends first of all on how you define "prime". And it also depends on what domain you're talking about; almost everyone seems to have assumed, rightly or wrongly, that you're talking about the integers $\ldots, -3, -2, -1, 0, 1, 2, 3, \ldots$

All integers are trivially divisible by 1 and $-1$, so we don't really care about that. And in any case, we no longer consider 1 to be a prime number, but that's another can of worms. Also, an integer is trivially divisible by itself and by itself multiplied by $-1$.

The popular definition for primes is that a prime is not divisible by any number in the domain that is smaller in some sense, other than the trivial divisors I've already mentioned. For the integers, the usual sense of comparison (for the purpose of factorization) is the absolute value function.

This definition is what some people call "irreducible" rather than "prime". They use a stronger definition for primes, one that requires for a number to be called prime that it always divides at least one of the nontrivial factors of any other number that it divides. In symbols, we have that if $p \mid ab$, then either $p \mid a$ or $p \mid b$.

So if you're using this latter, stronger definition of primes, then $c \times d = e \times f = n$ such that neither $e = c/d$ nor $f = c/d$ is impossible by definition regardless of what domain you're talking about.

But if you're talking about the integers, then the distinction between prime and irreducible is irrelevant, because all primes are irreducible and all irreducibles are prime. We say that the integers form a unique factorization domain. This fact is called the fundamental theorem of arithmetic. See https://proofwiki.org/wiki/Fundamental_Theorem_of_Arithmetic for a proof.

Some of the other answers mention domains in which multiple distinct factorizations into irreducibles are possible, since not all irreducibles are prime in those domains. So if you're using prime to mean irreducible, then yeah, what you're asking for is possible in many domains, but not in the integers.