Prime Numbers

[Quailman]

A unique way to learn your prime numbers cna be found here.

[Marvin]

LOL!

[dave10000]

1...is...not...a...prime!!!

[CrystyB]

k it's fixed. With an ongoing grudge...

[Antrax]

Whoa, Quailman, that site has a reference to the goatse.cx guy!
~tries to explain why that's funny, utterly fails~
Antrax

------------------
I was handcuffed by an evil goth limey chick in a really cheesy motel room, and all I got was this lousy sig line.

[pikachamp]

a prime number is defined as having exactly 2 factors, 1 has only 1
so :b

------------------
665: The neighbor of the beast.
666A: The tenant of the beast.
766: The upstairs neighbor of the beast.
DCLXVI: The roman numeral of the beast.

[CrystyB]

Pika, you shut up. I was talking to Dave. But since you interfered... Have you ever really seen those words as a DEFINITION of primenes??? I mean, what is the most advanced entity in maths you remember you last studied? Fractions and common denominators?

[CzarJ]

I much prefer this site

------------------
x=(-b±(sqrt(b^2-4ac)))/2a

I seem to remember... a song...

[Bicho the Inhaler]

Hmmm...preceding comments by pika and CrystyB made me realize that we should really define "primality" before we argue about it. CrystyB, pika's definition of primes as having only 2 factors works quite well, but you obviously don't like it. So I propose the following (partial) definition of prime numbers:

I. A positive integer P (yes, 1 counts) is prime if and only if P has only one prime factor.
II. Every integer greater than 1 has a prime factor (we'll say nothing about the number 1 right now. Fair enough?).

Now suppose 1 is prime. It satisfies I because 1 is the only factor of 1. Now let's look at condition II: Suppose we have a number P such that P =/= 1 and P is prime. P = 1*P, making 1 a prime factor of P, and thus the only prime factor. So P is not prime. This is a contradiction, so we must conclude that P is actually not prime. However, since P is not prime and 1 is a prime factor of P, P must have another prime factor Q with Q =/= 1 (or P would be prime). But Q = 1*Q, so 1 and Q cannot both be prime, since Q =/= 1. Because 1 is prime, Q is not prime, and this is a contradiction. So now we must conclude that our intial supposition, "1 is prime," is false or conditions I and II are not consistent. We can add a third condition:

III. The number 1 is itself not prime.

I won't demonstrate it here (an exercise for the reader, oh boy), but the conditions

I. A positive integer P is prime if and only if P has only one prime factor.
II. Every integer greater than 1 has a prime factor.
III. 1 is not prime.
IV. Only positive integers may be prime.

characterize primality completely (along with the other axioms, of course). If we were to replace III with "1 is prime," our definition would be inconsistent. I guess we could also replace I with "A positive integer P greater than 1 is prime if and only if it has only two distinct prime factors" and we could replace II with "Every integer greater than 1 has two distinct prime factors," and then it's probably consistent. But the only thing that accomplishes is allowing 1 into the definition of primality while making it more complicated, which doesn't attract me. Do you have a good definition of primality that includes 1 as prime?

Also, the fact is that where in a lot of theorems we just say things like "for some prime P" or "for all primes P" or "if P is prime," if 1 was prime, then we would end up saying "for some prime P with P =/= 1" or "if P is prime and P =/= 1," etc. A good example is the prime factorization theorem: we would have to change it because if 1 were prime, then prime factorizations would no longer be unique. Why bother with all this hassle?

[edit: Okay, I see on the page you have a definition that accomodates 1 (and the 1*1*1 thing never crossed my mind). But I still think that things are lot simpler if 1 is not prime. It's very similar to why 0! = 1; it doesn't immediately make intuitive sense, but if we define it that way, then a lot of other things make a lot more sense than if it were defined differently or not defined at all.]

[This message has been edited by Bicho the Inhaler (edited 12-08-2001).]

[CrystyB]

"I. A positive integer P (yes, 1 counts) is prime if and only if P has only one prime factor."
I think this is useless since it is recursive without a stopping condition. UNLESS YOU KNOW ABOUT 1, everything else falls.

Adding "III" was naive, because it is only a theorem (you've just proven it, and went to a lot of trouble in doing so), and not an axiom.

Just out of curiosity, why forcibly decide that only natural numbers can be prime? Since that's what you're doing - a new axiomatization of ''primeness'', ruling "this is in, and this is out".

- - -

I really didn't want to make this an advanced algebra topic, but i see i have to.

Given a ring R, there is a special subset of elements that are better than the rest - those that have an inverse. These will be called 'units'. For instance, in the integers' ring Z, only 1 and -1 are units.

Two elements, x&y, are equivalent (which is shown by writing x~y) iff there is an unit u for which x=uy. Of course, there is another unit v (precisely the inverse of u) for which y=vx. E.g. 18 and -18 are a pair of numbers like that.

To be able to have a decomposition the resembles the intuitive one as much as possible, there are defined two DIFFERENT special elements: irreductible and prime elements. By definition, x is irred. iff p is not an unit and for any y|x, y~x. Mainly, it has no proper divisors. Again by definition, p is prime iff p is not an unit (and in particular p=/=1) and for any a&b, p|ab => (p|a or p|b). The thing is that it just happens that in Z these two concepts are identical. In general, they aren't.

And before anyone asks why specifically remove units from the above definitions, it is due to the desire for the decomposition 'as we know it'. Given any non-zero element of the ring, there is a unique (aside from replacing some factors with their equivalents) decomposition of it in a) prime factors / b) irreductible factors. (i'm too tired @ 3am to actually write this math-style.) If the units are to be considered prime / irred., the uniqueness would be lost, and lots of arithmetics relies on just that uniqueness.

Edit: i forgot to say this, and it was one of the reasons i wrote all that stuff: -7 is prime, and so are an infinite number of negative numbers.

And zero is absolutely out of the question, since it is too egocentric when multiplying.

[This message has been edited by CrystyB (edited 03-10-2002 08:37 PM).]

[Bicho the Inhaler]

OK, I guess I wasn't completely clear. I was talking about N, not Z. The decision was pretty arbitrary; I just didn't want to complicate my definition. I should have stated that.

At least we agree that units aren't prime. Also, isn't it sometimes impossible to find unique prime factorizations? I must admit I know next to nothing about this, but one of my professors hinted it.

[extropalopakettle]

Every natural number (>1) has a unique prime factorization - this is easily proved. Finding it, in practice, may be virtually impossible.

The RSA public key encryption algorithm depends on this fact. If someone were to find a practical way to factor large numbers (like 2000 bits or so), the results would be incredibly devastating, as the RSA algorithm, currently used to protect all manner of confidential information, would be broken.

In general, most public key encryption algorithms depend on a "one way" function - a function that is easy to compute, but has an inverse that is practically impossible (computationally very expensive) to compute. It's trivial to multiply two very large prime numbers. It's incredibly difficult to take the result, and determine what those prime numbers were.

[Bicho the Inhaler]

I know that natural numbers can be factored uniquely but CrystyB was talking about primes/irreducibles/units over more general algebras. Consider single-variable polynomial algebra over a field. Like the integers, unique factorization (not including units) can be achieved for any such polynomial in terms of irreducibles (the nature of "irreducibles" depending on the field). Aren't there domains where this isn't the case?

[CrystyB]

As far as i remember the algebra i took last year, it is a proven fact that there's unique both in primes and irreductibles.