# Prime Factorisation

A prime is a value in a ringlet whose principal ideal (the collection of all multiples of the value) is a prime ideal – a proper ideal for which r.s in the ideal implies either r or s is in the ideal. Thus, at least in a commutative ringlet, any r.s equal to a prime c (or to any multiple of it) has c as a divisor of one of r, s; so no prime has any proper divisors.

Note, however, that I don't define that a value with no proper divisors is prime; in particular, units have no proper divisors, yet are not prime. Even aside from units, in a ringlet that's not a principal ideal ringlet, there may be some values with no proper divisor that aren't primes, hence prime factorisation isn't guaranteed to exist for all values. I'll describe a value with no proper divisors as indivisible; this shall at least include both primes and units. Other authors may define prime to mean indivisible, in which case they'll get subtly different results, typically having prime factorisation in more cases, in particular some where such factorisation isn't unique. Such authors prove the property I use as definition as a theorem (known as Euclid's Lemma), arising from the lack of proper divisors; doing so depends on particular properties of the ring in which this holds. (We are usually mostly interested in {integers}, where only units (i.e. ±1), primes and their additive inverses are indivisible.)

In a division ringlet (where every non-zero value is invertible) there are no proper ideals so none of this discussion arises – all non-zero values are units – so the interesting case for the discussion of primes is when (at least) some values of the ringlet are not invertible. The most important particular case is the usual arithmetic on whole numbers, most of which don't have whole number inverses; in this case, we're dealing with a commutative multiplication which, where 0 isn't involved, is cancellable. We are thus particularly interested in integral ringlets that aren't division ringlets (i.e. the non-zero multiplication is cancellable but incomplete).

## Preliminaries

The product of a prime and an invertible value generates the same principal ideal as the given prime, so the product is also prime; however, since it generates the same principal ideal, it is essentially equivalent to the prime we started with. In practice, we're only interested in primes modulo this equivalence; what matters are the prime ideals they generate.

In {naturals}, 0 and 1 generate ideals that aren't proper and 1 is the only invertible natural; the other naturals with no proper divisors are prime. Since the characteristic of any ringlet without proper zero-divisors lacks proper divisors, the homomorphic embedding of {naturals} in any ringlet with characteristic > 1 and no proper zero-divisors has a prime ideal as its kernel. The quotient of {naturals} by this kernel is a ring and, by the preceding, has no proper zero-divisors, so it's an integral domain; since the image of {naturals} under the homomorphism is a sub-ringlet of our ringlet and isomorphic to this quotient, every ringlet of characteristic > 1 with no proper zero-divisors has a sub-ringlet of its center that's an integral domain. A ringlet of characteristic 0 likewise has a sub-ringlet of its center that's isomorphic to {naturals}, which is an integral ringlet.

### Dividing products of lists

Prime factorisation's aim is to express any value as the product of a list of primes; repeated prime factors of the value appear several times in the list. (Product is the bulk action of multiplication; product([a,b,…y,z]) = a.b.….y.z.) As primes are only unique up to invertible multiplication and, when multiplication is commutative, permuting a list's entries doesn't change its product, we need to know a few things about how products of lists relate to primes.

The empty list's product is 1; any factor of 1 generates a principal ideal that includes all multiples of 1, hence is the whole ringlet so isn't proper (thus, in particular, isn't prime); so no prime divides the product of an empty list. If a prime divides the product of a list of length one, the product is the single entry and the prime does divide that entry. For a list of length two, the definition of primeness says that if a prime divides the list's product then it divides some entry in the list. Now suppose we have some natural n for which every list, of length less than 1+n with a multiple of a prime c as product, has a multiple of c as an entry; we already see that this holds for n = 2. If c divides the product of a list (: r |1+n) then c divides product(:r:n).r(n), hence either product(:r:n) or r(n) by the definition of prime-ness; if c divides r(n) then it divides some entry in r; otherwise, it divides the product of the shorter list (:r:n) and, by the inductive hypothesis, divides some entry in (:r:n); either way, it divides some entry in r. Thus we can induce that any prime that divides the product of a list necessarily divides some entry in that list (which is thus necessarily non-empty).

For the rest of this subsection, say that two values balance precisely if each is the result of multiplying the other by some invertible value; and let shuffle be an action on a list that permutes it and replaces each entry with one that balances with it, i.e. multiplying each entry by an invertible value. Any combination of shuffles is a shuffle; and every shuffle has an inverse that shuffles the result back to the original. The uniqueness we can hope for, for prime factorisation, is just uniqueness modulo such shuffling.

In an integral ringlet, the product of a list of values always balances with the product of any list obtained from it by shuffling (multiplication is commutative, so permutation makes no difference; and multiplying entries by invertible values just multiplies the product by the product of these values, which is invertible). So suppose we have some natural n for which, whenever a list of primes with length less than n has product that balances with the product of another list of primes, the second list has the same length as the first and each can be obtained from the other by shuffling.

Now consider two lists ({primes}: f |n) and ({primes}: g :) whose products balance. If n is 0, f is empty, its product is 1, g's product is invertible, every entry in g is invertible; but no invertible is prime, so g actually has no entries and is equal to f. Otherwise, n is 1+m for some natural m and the product of g is a multiple of f(m), which is prime: so some entry of g is a multiple of f(m); in particular, g has at least one entry, so is non-empty. Now, entries in g are prime, so f(m) isn't a proper factor of this entry in g, so this entry in g balances with f(m). Apply a cyclic permutation to the entries in g, that moves this one to the end of the list (and those that appeared after it to the start), then replace this one with f(m); this is a shuffle. The product of this list balances with that of f and g, so it's just some invertible times the product of f; cancelling the factors of (non-zero) f(m) we find that our shuffled g, when we leave off its last element, is a list whose product balances that of (:f:m), which has length m < n, so this truncated shuffled g is in fact a shuffle of (:f:m); our shuffle of g is then a shuffle of f, hence so is g.

So, by induction, any two lists of primes whose products balance are in fact shuffles of one another, at least in an integral ringlet. When the only invertible in our integral ringlet is 1 (as in the case of {naturals}), this means they are simply permutations of one another.

## Factorising

Consider any non-zero value v of a ringlet that's not invertible. Its principal ideal V is proper, since it has a non-zero element and doesn't have 1 as an element, so isn't the whole ringlet. Each of its proper factors has a principal ideal that subsumes V. If we have some non-empty collection B of proper factors of v, for which a, b in B implies either a is a proper factor of b or b is a proper factor of a, then the principal ideals of the members of B form a chain, whose union is necessarily an ideal; since each of the ideals united is proper, none has any invertible members, so nor has the union; and each has some non-zero members, hence so has the union, which is thus also proper. In a principal ideal ringlet, this ideal is necessarily principal, so there is some value in our ring that is a divisor of all members of B; and a proper divisor of all but possibly itself, if it is in fact a member of B. This value is necessarily non-invertible (because its ideal is proper) and non-zero (because its ideal has some non-zero member). Zorn's lemma, applied to divides as partial ordering, would now turn this into a statement that every non-zero non-invertible value in a principal ideal domain has a prime divisor.

Since I'm not a fan of variants on the axiom of choice, such as Zorn's, let's look at something a little like a Euclidean ringlet: suppose we have a ringlet R with a mapping ({naturals}: d |R) for which, for x, y in R, x is a proper factor of y implies d(x) < d(y). For example, the identity will do when R is {naturals}. In such a ringlet, every chain of the variety described above is necessarily finite, since a chain of divisors of r can have at most d(r) members; the chain thus has a member with lowest d, which is a proper factor of all others in the chain. Either this is prime or we can extend the chain (because a non-invertible non-zero non-prime necessarily has a proper factor); and we can only do the latter finitely many times, so we must get to a prime in finitely many steps. In such a ringlet, every non-invertible non-zero member has a divisor that's prime. Furthermore, when we divide it by such a prime divisor, we get a value on which d is smaller, so repeatedly applying this must, in finitely many steps, get us to a case where the prime in question isn't a proper factor: the quotient at the next step is invertible and our original value has been expressed as a finite product of primes (we can multiply one of them by the invertible we end on; the result is necessarily also a prime).

So we can factorise each member of a ringlet R as a product of primes, at least when we have a ({naturals}: d |R) which maps proper divisors to smaller values than their proper multiples; and you're welcome to believe the same holds true in any principal ideal ringlet, if you're willing to stomach the (transfinite) axiom of choice.

Thus, in at least some ringlets, every value has a prime factorisation; and we saw above that, in integral ringlets, prime factorisation is unique (modulo permutation and invertible multipliers). In particular, the natural ringlet (in which only 1 is invertible) has unique (modulo permutation of order) prime factorisation for positive naturals: this is known as the fundamental theorem of arithmetic. A great deal of number theory relies upon it !

More generally, when an integral ringlet supports unique factorisation by irreducibles (i.e. values with no proper factors; not necessarily primes in my terms), I'll call it a unique factorisation ringlet; the case of a ring (i.e. an integral domain with such factorisation) is orthodoxly known as a unique factorisation domain. The above shows that any principal ideal ringlet is a unique factorisation ringlet (and its irreducible factors actually are primes); likewise, a principal ideal domain is a unique factorisation domain.

When the existence of prime factorisations arises from having a principal ideal ringlet, this necessarily implies it's integral and hence that the factorisation is unique; however, a ringlet that isn't a principal ideal ringlet might plausibly support (by some other cause than the argument for a principal ideal ringlet) prime factorisation (with the ideal-based meaning for prime, that I've used here). In such a case, it would be interesting to either find cases of non-unique prime factorisation or prove that the existence of prime factorisations implies uniqueness. Another possibility would be to prove that the existence of prime factorisations implies that we actually do have a principal ideal ringlet.

### Contrary Example

As an example (borrowed from MathWorld) of a ring without unique prime factorisation, consider {lists ({integers}: |2)} with the usual point-wise addition and the contrived multiplication [n, m].[p, q] = [n.p −5.m.q, n.q +m.p]; this forms a ring with z = [0, 0] as additive identity, [−n, −m] as additive inverse for [n, m] and e = [1, 0] as multiplicative identity. (If we multiply [0, 1] by itself, we get [−5, 0] = −5.e; so, if we write 1 for e it makes sense to write √−5 for [0, 1] and to write [n, m] as n +m.√−5.)

Since we need to consider factorisations modulo invertible multiplication, we'll need to know which values are invertible. For [n, m].[p, q] to be e, we must have n.q = −m.p and n.p = 1 +5.m.q, whence −m.p.p = n.q.p = q +5.m.q.q so q = −m.(p.p +5.q.q), in which p.p +5.q.q ≥ 0, so q and m can't both be positive or both be negative; so m.q ≤ 0 and n.p = 1 +5.m.q ≤ 1; we can likewise write 5.n.q.q = −5.m.p.q = p −n.p.p, whence p = n.(5.q.q +p.p), with 5.q.q +p.p ≥ 0, so n and p can't have opposite signs (p could be 0, with n of either sign; otherwise, both are positive or both are negative), so n.p ≥ 0 and we already know n.p ≤ 1; thus, as n and p are whole numbers, n.p is 0 or 1. Since n.p = 1 +5.m.q with m.q a whole number, only the case n.p = 1 is in fact possible. This gives n = p = ±1, q = −m and 5.m.q = 0, implying m = q = 0; so only [±1, 0] are invertible, each being its own inverse. Thus the only invertible values are ±e and primes are only considered modulo sign.

Do we have any zero-divisors: when does [n, m].[p, q] = [0, 0] ? This gives n.p = 5.m.q, n.q +m.p = 0; so m.p.p = −n.q.p = −5.m.q.q, whence m.(p.p +5.q.q) = 0, whence either m = 0 or p = 0 = q. The m = 0 case gives n.p = 0 = n.q so either n = 0 or p = 0 = q; either way, one of our two factors is [0, 0], so our ring has no proper zero-divisors; as it's a ring, this makes it (descalable and) an integral domain.

One more thing we'll need, in understanding this ring, is the function ({naturals}: norm :) defined by norm([n, m]) = n.n +5.m.m; this is a positive definite quadratic form. This leads to

norm([n, m].[p, q])
= norm([n.p −5.m.q, n.q +m.p])
= (n.p −5.m.q).(n.p −5.m.q) +5.(n.q +m.p).(n.q +m.p)
= n.n.p.p −10.n.m.p.q +25.m.m.q.q +5.n.n.q.q +10.n.m.p.q +5.m.m.p.p
= n.n.(p.p +5.q.q) +5.m.m.(p.p +5.q.q)
= (n.n +5.m.m).(p.p +5.q.q)
= norm([n, m]).norm([p, q])

Since every value of our ring except z and e has norm > 1, this implies that any proper factor of a value necessarily has smaller norm than the given factor; and the proper factor's norm divides its multiple's norm, as a natural; which limits the search for potential factors. In particular, we have norm(z) = 0 < norm(±e) = 1 < norm([±2, 0]) = 4 < norm([0, ±1]) = 5 < norm([±1, ±1]) = 6 < norm([±3, 0]) = 9 = norm([±2, ±1]) and every other value of our ring has larger norm than any of these. In particular, since none of {4, 5, 6, 9} divide one another, none of the given values has any proper factors. (Indeed, every proper factor has norm ≥ 4, so every product of proper factors has norm ≥ 16, so no value with norm ≤ 15 has a proper factor.)

Now observe that [1, 1].[1, −1] = [1 +5, 1 −1] = [6, 0] = [2, 0].[3, 0] gives two factorisations of 6.e; the factorisations can't be transformed onto one another by permutation and multiplication by ±e; so, if the given factors are prime, we'll have non-unique prime factorisation.

Had I defined values of a ringlet to be prime if they have no proper factors, this would indeed (thanks to the norm analysis above) be an example of non-unique prime factorisation. However, I've defined prime by the principal ideal containing at least one factor of any product in this ideal, with the result that none of [2, 0], [3, 0], [1, 1] and [1, −1] is in fact prime – the very example given above shows that they are not !

If we now look at the ideal generated by {[2, 0], [1, 1]}, its typical member is [2.p +n −5.m, 2.q +n +m] for some naturals p, q, n, m. The members with zero second component, 2.q +n +m = 0, have first component 2.p +n −5.m = 2.p −2.q −6.m = 2.(p −q −3.m), which is necessarily even; so e is not in this ideal; since it's clearly non-empty, it's thus a proper ideal. However, it ontains [2, 0] and [1, 1], which are coprime (as shown by the norm analysis above); consequently, this ideal is not principal, our ring is not a principal ideal domain and not every value has a factorisation as a product of primes.

Written by Eddy.