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