From: trebla@vex.net (Albert Y.C. Lai) Newsgroups: alt.algebra.help Date: Sat, 17 May 1997 15:23:42 -0400 Organization: InterLog Internet Services In article , R Clanchy 1 wrote: >Prime and composite numbers form a convenient dichotomy until the >problem with 1 arises. When I first met prime numbers we were all >allowed to happily believe that 1 was prime. The slight hiccup with the >prime factors of 6 being 2 * 3 and not 1 * 2 * 3 was easily enough >accepted as the 1 was not necessary. These all point to the necessity to introduce a third class, "units", and we will have a trichotomy instead: units, primes, composites. Intuitively, units are what you can throw in or take away from a factorization without feeling uncomfortable, like 2*3 = 1*2*3. Allow me to introduce negative numbers. Then there are several factorizations of 6: 2*3, (-2)*(-3), (-1)*2*(-1)*3, (-1)*2*(-3), ... You do not feel uncomfortable about that; they still look strikingly similar to you. Why, 1 and -1 do not introduce "new values", do they? The formal definition of "unit" is --- think about it --- anything admitting a reciprocal in the number system you use. We are confining ourselves to natural numbers or integers. No one has a reciprocal... except 1 and -1, of course. What a coincidence. The coincidence looks even more stunning when you think about it. Why do you think that 2*3 and (-2)*(-3) look alike? Because you can cancel out the -1's. Why can you cancel them out? Why, because precisely -1 has a reciprocal! It is pretty clear that it is insensible to talk about factorizations of 1 and -1. Well, it is sensible, but you can't ask for uniqueness. If you don't think it is because they are units, consider this. Working in the rational numbers, factorize 3/4. You can't, right? Well, you can, but you feel that your leg is pulled. 3/4 = 3/4 = 3 * 1/4 = 3/2 * 1/2 = 5 * 3/20 = ... They do not look alike. Which one should you prefer, or is it just a skill-testing question? The problem is that 3/4 is a unit (its reciprocal, 4/3, is still a rational number), so its factorizations cannot be unique. 3/4 = 4/3 * 3/4 * 3/4 = 4/3 * 3/4 * 4/3 * 3/4 * 3/4 = ... And there are many more units in the rational numbers, so that you can synthesize a "different" factorization by introducing units. For example, I came up with 5 * 3/20 by considering that 3/4 = 5 * 1/5 * 3/4, knowing that 5 is a unit. Finally, there is no prime --- basic building block --- in the rational numbers, because everyone is a unit. Recently, someone in this newsgroup considered subsets of rational numbers in which unique factorizations make sense. An example is the integers augmented with the rational number 1/2. Let's call it R. Every member of R can be expressed in a compact form. R = { k/(2^n) | k is integer, n is natural } (My natural numbers include 0.) Anyway, it can be shown that R admits unique factorizations. I will not prove that (but I can), instead I will show an example of factorizations in R. Before we begin, let us recognize the units. 1 and -1 are always units. 2, -2, 1/2, and -1/2 are the new kids, obviously. In fact +/- 2^n and +/- (1/2)^n, for each natural n, are. There are no more: Suppose k/2^n is a unit, then it has a reciprocal j/2^m, so that k/2^n * j/2^m = 1 multiply by 2^n and 2^m k * j = 2^(n+m) where k and j are ordinary integers. Unique factorization in the integers implies that k must be a power of 2, times 1 or -1 (units of integers). Thus k/2^n must be also a power of 2, times 1 or -1. So in R we cannot ask for a unique factorization of 4, because it is a unit: 4 = 2*2 = 1*4 = 16 * 1/8 = ... Contrast this to the integer case 4 = 2 * 2 = (-2) * (-2). However, 3 is still a prime in R. That 3 = 3/2 * 2 is not a problem because 3 = -3 * -1 has never been a problem. 2, 1/2, and -1 are units. This also shows that 3/2 is as prime as 3, just like -3 is as prime as 3. If you are still with me, 6 is also a prime, since 6 = 3*2 where 2 is just a unit. We call 3/2 and 6 associates of 3. (Or 6 and 3 are associates of 3/2, etc.) Formally, two numbers are associates iff by multiplying a unit to one you can get another. Let us factor 9. We know that 3*3 is ok. So is 3/2 * 6, so is 3/4 * 12, etc. Even 3 * 6 * 1/2 will do. We still say that the factorization is unique, because the only differences are ordering and units. The primes used in one version are no more than associates of the primes used in another version. The definition of "prime" must be revised to allow for the new changes. The revised version is still convenient to use in the case of naturals and integers. 1. A prime is a non-unit, and the only way to split it into x*y is to have x a unit or y a unit. Another way to say the same thing: a non-unit, and its only divisors are its associates and units. 2. A prime is a non-unit, and whenever it divides into some u*t it must divide into u or it must divide into t. (We must also add that they are non-zero's.) It has been taken for granted that the two are equivalent. In number systems admitting unique factorizations, the two are really equivalent. But there are bizzare number systems in which factorizations are really not unique, and there the two definitions are different. In this case, the first definition is called "irredicible", the second "prime". Educationists, (like, the education authorities), in their infinite wisdom, decree that we will teach only the prime-composite dichotomy, not the unit-prime-composite trichotomy. In their holy vision, the only "useful" number systems are the naturals, the integers, the rationals, the reals, and questionably the complexes. In these systems, either there are almost no units, or almost the whole system is units, so it is not "educational" to introduce an "unnecessary" term. Many of us have played "war games": you know, using tokens to represent armies or ships or airplanes, on a board representing a 2D map of the battlefield. The discretization of the battlefield is unorthodox: regular hexagons are used to tile the map. One day, a friend on the phone posed the problem of computerizing this hexagonal board. Within half a minute, I recalled something I learned from university algebra classes. Augment the integers with the complex number -1/3 + i/2. You recognize that it is one of the most important roots of the polynomial x^3 - 1. Let w = -1/3 + i/2. Pretend that w is the Greek letter omega. :) Consider the number system W = { b + c*w | b, c are integers } Try to plot this lattice on a paper or computer screen. You will see that you get the centres of the hexagons you need. Each cell on the board can be identified with its centre; the centre obviously comes with a Cartesian coordinate (x,y) or a complex number x+iy, but is more conveniently expressed as b + wc, where b and c are humble integers. Thus the data structure emerges: to name a cell, use a tuple representing b+wc; to store the entire board, use a 2D array Board(1..100, 1..100) or something, where Board(i,j) stores the cell at i+wj. We still need to move from a cell to another. Pretend that you are at cell <0,0>. It has six neighbours in the six directions: 1 = <1,0>, 1+w = <1,1>, w = <0,1>, -1 = <-1,0>, -w-1 = <-1,-1>, -w = <0,-1>. I named them in the counterclockwise order. By translation, if you are at any cell, adding one of those six numbers to your present position will move you by one cell in the corresponding direction. For example, suppose you are at b+wc = now, then (b+1)+w(c+1) = will move you in the 60-degrees direction, because you are adding 1+w. A computer programmer can easily take these as basic rules of operations and codify them into a program of war game. More computation is done than manipulating rectangular grids, but it works elegantly. And so much for educationists deciding what we need to know. BTW, unique factorization makes sense in W. >The idea seemed to be to find the >set of numbers which could not be formed by multiplying smaller numbers >together. 1 fits into this category. As I understood it then, the name >prime implies that these numbers are needed to start with, once they are >in place all the composite numbers can be formed from them. (I simply >don't understand it now.) > >There seems to be no simple, reasonable explanation. I would be >grateful if anyone can convince me (within the realm of the natural >numbers only). Oops, ok. Finding numbers not reducible to smaller numbers is not quite the same as finding numbers needed to form larger numbers. I guess the traditional definition of "prime" tries to capture the latter. Sure, 1 cannot be split into smaller numbers, but it never gives you any larger number either. Units are a sore point in any study of factorization. More reason to give them a name --- unit --- because they are a sore point, no matter how rarely they occur. >Also, why is zero not a natural number, (even if it was rather an >afterthought in the big bang theory of mathematics)? The football >scores, amongst many other non-negative concepts are so peculiar without >it. It is just convention. But lately you find that this convention is inconvenient. I support 0 to be included into the naturals, as do a number of computer science books. The ancient Greeks even excluded 1 from "numbers": "number" started with 2. This is still reminiscent in English and probably other European languages. I have a number of wives. What is your first impression? Your basic instinct tells you that I must have at least 2 eh? As if 1 is not "a number" eh? And if I now tell you, I am still single actually, you will royally object: "you can't say you have a number of wives when you have none!" So there. It also depends on the topic. If you just want to talk about prime factorizations, you would kill to get 0 out of the way. It only annoys you. >Another annoying question someone asked me relates to the convention of >labelling the transformation of the point A as A' which I was always >taught to read as "A prime". This is simply an overloading of the word >prime but as my questioner pointed out, it can be a source of confusion >for pupils. Does anyone else read "A prime" for A' and if so, is there >a good reason for it? I read it as A primed, or A prime if I am lazy. If the word "prime" is needed for other purposes in the discussion, I will call it A dashed, or A dash. To be exotic, you could call it A apostrophe too. :)