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