The basic structure of the naturals leads to arithmetic on them, combining addition and multiplication in familiar ways that we can formalise to infer some general results that, in particular, apply to the naturals. I here pick up the thread of the naturals and look at the consequences, for them, of some of those general results. As the naturals supply the prime sub-ringlet of every ringlet, these consequences specific to them have at least some relevance to every ringlet.
One technical result we're going to need in a few places is that, for every natural n, there's a power of 2 that's greater than n. Naturally, we can prove a more general result.
So, for any natural k > 1, observe that power(0, k) = 1 > 0 and power(1, k) = k > 1. Suppose, then, that power(n, k) > n for some natural n. Thus power(n +1, k) > k.n and k > 1 so k.n > n, whence k.n ≥ n +1 and power(n +1, k) > k.n ≥ n +1 so power(n +1, k) > n +1. We may now induce that power(n, k) > n for every natural n and every natural k > 1. Therefore, for every natural n and every natural k > 1 there is some power of k that is greater than n.
In fact each positive power is strictly monotonically increasing; as is (: power(n, k) ←n :{naturals}) for any natural k > 1; and any strictly monotonically increasing function from naturals to itself must eventually exceed any given natural. To see why, notice that, within naturals, x > y implies x ≥ y +1; so f(n +1) > f(n) implies f(n +1) ≥ f(n) +1, which forces f's output to increase at least as fast as its input. Inductively, for strictly monotonically increasing ({naturals}: f |{naturals}), consider any natural n for which each i in n has f(i) ≥ i; then f(n) > f(i) ≥ i for each i in n and each i in n is also in f(n), whence f(n) ≥ n. As a result, every monotonically increasing function on the naturals increases at least as fast as the identity and thus exceeds every natural eventually.
Indeed, even any monic function ({naturals}: f |{naturals}) necessarily has some input at which its output exceeds any given natural, since its collection of outputs is infinite and only finitely many of its members lie in any finite set, in particular in any given natural's successor; the infinitely many other outputs of f are thus greater than the given natural. Any strictly monotonically increasing function, power included, is indeed monic; and, once it has produced an output greater than a given natural, all its later outputs must also be greater than it.
One important consequence of the ringlet structure on the naturals, with its cancellable multiplication on non-zero values, is the fundamental theorem of arithmetic – that it's (a principal ideal ringlet and thus) a unique factorisation ringlet. This means that every positive natural number has a unique (modulo order) expression as a product of prime factors. This unique prime factorisation has various strong consequences. Furthermore, when we reduce natural arithmetic modulo one of its prime ideals (each of which is generated by a prime), we get a field. For anyone new to the concept, the first few prime naturals are
each of which is divisible only by itself and 1; and every positive natural can be factorised in terms of such numbers.
The way I've defined primes requires the principal ideal of a prime to be a
proper ideal; this is not true of 1. However, like primes, 1 is indivisible;
that is, there is no natural number less than it that divides it. As a result,
1 shares various properties with the primes, albeit typically in some fatuous or
degenerate sense. So I'll refer to a natural
as indivisible
precisely if it's either 1 or a prime.
The first consequence of prime factorisation is that there's an endless supply of primes in {naturals}. Given any finite set of primes, we can multiply them all together and add 1 to their product; the result of this is not a multiple of any of the primes multiplied together, hence its prime factorisation will supply us with some primes which were not in the finite set we started with. Consequently, there are infinitely many primes in {naturals}. Since only finitely many of these lie in any finite set, including the successor of any given natural, infinitely many of them (and thus, in particular, at least some of them) are greater than any given natural.
The second is that the square of
any rational number, r, is a whole number precisely if
r itself is a whole number. A rational is just p/q for some whole p, q with q
non-zero; since the square of a negative value is the same as the square of the
matching positive, it suffices to examine the case of p natural and q a positive
natural. So let p/q have square n, whence p.p = q.q.n, and consider any prime
factor of q; count how many, i, times it appears in the prime factorisation of
q; it thus appears at least 2.i times in the prime factorisation of q.q.n = p.p,
hence at least i times in the prime factorisation of p; but this means every
prime factor of q is a prime factor of p and p has at least as many factors of
it as q has, so p's prime factorisation actually subsumes q's and p is a
multiple of q, hence p/q is a whole number. Thus any whole number either is
a perfect square
(the square of a whole number) or has an irrational
square root; in particular, √2 is not a rational.
Those familiar with clocks are used to doing arithmetic modulo twenty-four or twelve (hours) and sixty (minutes or seconds); likewise, reckoning what day of the week a given date shall be involves arithmetic modulo seven. In each case, there is a cycle and intervals are reckoned in terms of how many cycles they complete and how far into the next cycle they stretch. Indeed, all of decimal arithmetic is made up of arithmetic modulo ten; the positional notation for arithmetic relies on repeatedly reducing values to a multiple of ten plus a remainder.
Such arithmetic is formalised as reducing the
ringlet of natural arithmetic by the ideal
generated by all the multiples of some one natural,
the modulus
. The naturals
form a Euclidean ringlet, so for any
modulus N and natural n, there are some r in N and natural q for which n = q.N
+r; q is known as the quotient and r as the remainder arising from division of n
by N; as q.N is in the ideal generated by N, n is then identified with r and
every natural is, in the reduced ringlet, identified with some member of the
modulus. The reduced ringlet, when a given natural N is used as modulus, is
known as arithmetic modulo
N.
When we then do arithmetic between remainders, we again identify the result with its remainder. This works because, for any natural modulus b, naturals n, m and remainders r, s in b,
so that arithmetic using numbers identified with r and s always produces values that differ, from the result of doing the same arithmetic just on r and s, by a multiple of the modulus, which we ignore when determining the final remainder.
Even though we start with an incomplete ringlet – {naturals} lacks some differences, e.g. there is no natural you can add to 7 to get 4 – the modular arithmetic on its remainders modulo any positive modulus always forms a ring; for any natural, there is some larger natural that's a multiple of the modulus, hence some natural that can be added to the original to get a multiple of the modulus, with zero remainder; so every remainder has an additive inverse.
Any proper divisor of the modulus has mutliples that are multiples of the modulus, hence identified with 0 modulo the modulus; consequently, any divisors of the modulus are proper zero-divisors in the reduced ring; as a result, the non-zero multiplication on this ring won't be cancellable. This makes the case of prime modulus particularly interesting – precisely because it's when we have no proper zero-divisors and indeed it does have cancellable non-zero multiplication.
Since the naturals form a principal ideal ringlet, any ideal – in particular, the kernel of any ringlet homomorphism from the naturals – is indeed just the set of multiples of some natural; consequently, every quotient of the natural ringlet – in particular, every image of it under a ringlet homomorphism – is either the naturals itself (when the kernel was {0}) or the natural arithmetic modulo some natural.
Any combiner lets us repeatedly
combine a value with itself; it thereby supports an effective action of the
naturals, counting how many uses of the value are combined, on the binary
operator's operands; we can apply the bulk action
of the combiner to any list ({v}: |n) with v an operand and n a natural. The
successive values this produces, as we increase the natural, can only all be
distinct if the combiner has infinitely many values; and, even then, the
succession of values, from a given v, as we vary n, may repeat itself. If a
value ever repeats, it's said to
have order
equal to the smallest positive natural, n, that's the
difference between repeat-counts with the same result; when this happens for a
cancellable combiner, the bulk action applied to ({v}: |n) must in fact be an
additive identify for the combiner. If the results of repeatedly combining a
value with itself never repeat, that value is said to have order zero, serving
as (in effect) a surrogate for infinity. The combiner is then said to
have character
zero if any of its values has order zero; otherwise, the
combiner's character is the largest of the orders of its values (again, zero is
being treated as infinity, in effect; it counts as the largest order).
In a ringlet, every values's (additive) order is a divisor of the order of the ringlet's multiplicative identity; this identity's order is consequently the characteristic of the ringlet's addition. As no combiner on finitely many values can have characteristic zero, every finite ringlet's principal sub-ringlet (an image of {naturals} generated by repeated addition of its multiplicative identity to itself) is exactly the naturals modulo the ringlet's characteristic; and any ringlet with characteristic zero is necessarily infinite, containing a faithful copy of the naturals as its prime sub-ringlet. In particular, every ringlet whose characteristic has any proper divisors has, as a result, proper zero-divisors (namely, the members of its prime sub-ringlet that represent the naturals that are proper factors of the characteristic) and thus has non-cancellable multiplication. Only a ringlet with prime or zero chracteristic can be multiplicatively cancellable.
Given prime p, consider the ringlet of natural arithmetic modulo p; as it has no proper ideals, the ideal generated by any value of it is either {0} or the whole ringlet; as it has no proper zero-divisors, only 0 generates {0} as its ideal; all other i in p generate the whole ringlet as ideal; thus the set of multiples of any non-zero member of the ringlet is all the values of the ringlet, 1 included, so the non-zero multiplication is invertible; every non-zero value has an inverse and our non-zero multiplication forms a group. This makes the arithmetic modulo our prime a field – a commutative division ring. For arithmetic modulo 1, we get the trivial ring {0}, which is technically also a field, albeit less interestingly so; so arithmetic modulo an indivisible gives us a field.
Now, in any group, the powers of any one value (and its inverse) form a sub-group. In a finite group, multiplying each value in a sub-group by a value not in it will give a set, of the same size, of values within the group equivalent to one another modulo factors in the given sub-group; which partitions the group into such sets, each of the same size as the given sub-group; so, the size of a sub-group must be a divisor of the size of the group. Thus the number n of distinct powers, modulo p, of any non-zero i in p is a divisor of p −1; and power(n, i) is necessarily 1; hence so is power(p −1, i), since this is a power of power(n, i) = 1; and power(p, i) = i. The latter also holds true for i = 0, so power(p) = power(1) in the arithmetic modulo any prime p; and, of course, this is also true for the other indivisible, p = 1.
Conversely, suppose power(N −1, i) = 1 modulo N for all non-zero i in some natural N. In the case N = 1, this is fatuous (there are no such i); otherwise, N > 1, power(N −2, i) is a multiplicative inverse for i, making every non-zero i in N invertible, modulo N, which makes the multiplication cancellable and ensures there are no proper zero-divisors; this, in turn, implies that N has no proper divisors, i.e. is indivisible.
This can be used to test whether a value p > 1 is prime: take some smaller positive values and see whether power(p −1) of each is 1; if any isn't, p isn't prime. You only get negative evidence, but some care at chosing which values to check can rapidly reduce the odds of a non-prime passing this test repeatedly. The computational cost of formally checking all lesser primes as possible divisors is so colossally high that the probability of random cosmic rays hitting your computer and causing it to get the wrong result, during that formally correct computation, actually makes it less reliable than the much cheaper method of checking power(p −1) at a good sample of candidates values. (The latter has, of course, its own risk of cosmic ray interference, plus its (if done right) very small probability of being wrong because you didn't try the right values; but it's so much quicker that the sum of these two is still less than the cosmic-ray risk of the slower algorithm.)
Now, when 1+n is a prime, n is −1 modulo it so n and 1 are self-inverse; can any other values be self-inverse ? If m is self-inverse modulo a prime, then m.m −1 = (m −1).(m +1) is a multiple of the prime; consequently, as there are no zero-divisors, at least one of m −1 and m +1 must be a multiple of the prime; hence m is either 1 or −1 modulo the prime; so the only self-inverse values modulo prime 1+n are n (i.e. −1) and 1.
Consequently, in computing the factorial n! modulo prime 1 +n, we can pair off the factors, aside from 1 and n, into mutually inverse pairs; as each such pair's product is 1, n! mod 1+n is just n, i.e. n! +1 is a multiple of n +1. So every prime n +1 is a divisor of n! +1. The other indivisible, n = 0 giving indivisible 1 as n +1, is likewise a divisor of 0! +1 = 2. For the converse, suppose we have a natural n for which n +1 is a divisor of n! +1; then n! = k.(n +1) −1 for some natural k and none of the naturals 2 through n is a divisor of k.(n +1); in particular, none of them is a divisor of n +1. Thus n +1 is indivisible. We have just proved (as Lagrange did) Wilson's theorem: for a natural n, n +1 divides n! +1 precisely if n +1 is indivisible.
This is actually a special case of a stronger result. For any odd prime 2.b +1 and non-zero value a of the arithmetic modulo this prime, consider the relation m(a) = (: y ←x; x.y = a :) on the non-zero values. Any fixed point of this is some x for which x.x = a and, being non-zero (and not its own negation, since our modulus is odd), can be paired with its negation, as ±x have the same square; and their product it then x.(−x) = −a. Since our arithmetic is a field and x.x = a is a quadratic, m(a) has at most one such pair of fixed points. Since our arithmetic forms a commutative group, m(a) is a self-inverse mapping from all the non-zero values of the arithmetic to all those same values, so partitions those values that aren't fixed points into pairs, with each pair's product equa to a. But now the product of 1 through 2.b can be rearranged to put each of our pairs together, delivering a factor of a from each of b pairs, with a possible factor of −1 from the pair of fixed points, if there is one. So this product is ±power(b, a); and it doesn't depend on a. In particular, a = 1 definitely does give us a pair of fixed points, ±1, so the product is in fact −1.
Thus when power(b, a) is +1, modulo a prime 2.b +1, there must be some value modulo 2.b +1 whose square is a; and, if there is not, then power(b, a) is −1. This is known as Euler's criterion. For example, taking a = −1, we get a square root of −1 modulo exactly those odd primes that are one more than a multiple of four. (We also have a square root of −1 modulo 2, because −1 = 1 in this case.)
Written by Eddy.