a tad more on OR-numbrals

Jens Voss jens.voss at poet.de
Wed Jan 2 10:08:17 CET 2002

Jens Voss wrote:
> [...]
> On the other hand,
> the OR-numbral system appears to be the only one in which there
> is no unique factorization, so as one consequence of that we have
> to have to distinguish between "irreducible" and "prime" elements:
> [5] for example is irreducible (since it is not a product of two
> factors different from [1]), but not prime since it neither divides
> [3] nor [11] but their product [3] * [11] = [31] = [5] * [7].

In fact, it is not hard to see that [2] is the only OR-numbral
prime number. The proof consists of six steps the first four of
which should be proved as exercises.
We define a number to be _odd_ if its rightmost bit is set;
otherwise we call it _even_.
Recall that a number is defined to be _prime_ if whenever it divides
a product, it must also divide (at least) one of the factors.

(1) A product of two numbers is even if and only if at least one
    factor is even.

(2) A number is divisible by [2] if and only if it is even.

(3) [2] is a prime.

(4) For any odd number [x] there exists a number [y] such that
    [x] * [y] = [2^k - 1] for some k.

(5) [3] is not a prime.

Proof: [3] * [165] = [5] * [107] and neither [5] nor [107] are
divisible by [3].

(6) No odd number is prime.

Proof: Let [x] be an odd number. By (5) we may assume that
x is greater or equal to 5. By (4), there exists a number k
such that [x] divides [2^k - 1], so we can choose k minimal
with that property. Note that k > 1 by the choice of [x].
On the other hand, [2^k - 1] = [2^(k-1) - 1] * [3], so by
the minimal choice of k and the choice of [x], neither
factor is divisible by [x] and thus [x] is not a prime.  q.e.d.

More information about the SeqFan mailing list