Not sure if there are infinitely many ways to factorise 12 in the integers ;)

I can't remember the general definition of a prime numer, but I think it may be

a is prime => if a divides b*c then a = b or a = c

Otherwise, something to do with units (which are invertible elements with respect to multiplication, so those are +1 and -1 for the integers).

EDIT: Yeah, if a is prime and a = b * c then b or c is a unit (invertible element)?

Also, if a is a prime and a divides b*c, then a divides b or a divides c.

[quote name='Álvaro' timestamp='1354827471' post='5007874']
Whether 1 is prime or not is a matter of convention, and the prevailing convention is that it is not a prime. There are multiple possible definitions of what "prime" means, and they often tell you explicitly that 1 is not a prime. See the beginning of the Wikipedia page for an example.

This isn't really correct. 1 isn't a prime because it doesn't match the true definition of prime numbers. There is no convention about it.
The definition you've probably heard (something along the lines of "positive integer divisible only by 1 and itself, excluding 1") is a laymen's definition that simply happens to coincide with the real definition.
The real definition is that a prime number is an element of the set of numbers into which all positive integers can be factored into products of powers of, uniquely. It's a fundamental theorem in number theory. '1' clearly violates this because to factorize, say 12, you could have 1 * 2^2 * 3^1 or 1^2 * 2^2 * 3^1, or 1^3 * 2^2 * 3^1, etc. There are an infinite number of ways you can factorize something if you accept 1 as a prime number and primes are defined to make factorization unique.
[/quote]
As the Spanish expression goes, you are teaching your father how to make babies. I didn't "hear" a definition of prime: I spent 7 years of my life becoming a mathematician, which is what I do for a living, and that involved learning a whole lot of things about primes.



The definition of prime has changed over the centuries, and so has the primality of 1. The fact that natural numbers can be decomposed into a product of primes in a unique manner is a theorem (Fundamental Theorem of Algebra) and not a definition. The modern definition of prime is an element of a commutative ring that is not 0, not a unit and generates a prime ideal (that's the condition I just described in my previous post). The "not a unit" excludes 1. But this is a convention that people have found convenient, and has no deeper meaning.


If we were to consider 1 a prime, many theorems would have to be reworded to exclude it. But some other theorems would be simplified. For instance, see Wilson's theorem. There are also theorems that need to exclude 2 (example), but that doesn't mean that 2 isn't prime.

I didn't "hear" a definition of prime

I think you're mincing words here. I wasn't implying you were a layman to mathematics. Just that the definition you might have been basing that statement on was a laymen's definition. I know, from years of experience dealing with you that you have an awesome grasp of mathematics and computer science. And probably much more.

(Fundamental Theorem of Algebra)

Actually it's the Fundamental Theorem of Arithmetic, which is what I was referring to. The Fundamental Theorem of Algebra is something very different.

The modern definition of prime is an element of a commutative ring that is not 0, not a unit and generates a prime ideal (that's the condition I just described in my previous post). The "not a unit" excludes 1. But this is a convention that people have found convenient, and has no deeper meaning.

Except that this modern definition, with which I'm familiar, is a consequence of its equivalence to the definition that satisfies the fundamental theorem of arithmetic and a desire to merge abstract algebra with number theory.

If we were to consider 1 a prime, many theorems would have to be reworded to exclude it. But some other theorems would be simplified. For instance, see Wilson's theorem. There are also theorems that need to exclude 2 (example), but that doesn't mean that 2 isn't prime.

Yep. But this isn't really related to what we're talking about, which is the definition and whether 1's exclusion is a convention or a consequence of something deeper. Not the consequences of things being different.

[quote name='Álvaro' timestamp='1354838822' post='5007937']I didn't "hear" a definition of prime

I think you're mincing words here. I wasn't implying you were a layman to mathematics. Just that the definition you might have been basing that statement on was a laymen's definition. I know, from years of experience dealing with you that you have an awesome grasp of mathematics and computer science. And probably much more.[/quote]
Sorry if I misinterpreted what you were saying.

(Fundamental Theorem of Algebra)

Actually it's the Fundamental Theorem of Arithmetic, which is what I was referring to. The Fundamental Theorem of Algebra is something very different.[/quote]
Ooops! That's exactly right.

The modern definition of prime is an element of a commutative ring that is not 0, not a unit and generates a prime ideal (that's the condition I just described in my previous post). The "not a unit" excludes 1. But this is a convention that people have found convenient, and has no deeper meaning.

Except that this modern definition, with which I'm familiar, is a consequence of its equivalence to the definition that satisfies the fundamental theorem of arithmetic and a desire to merge abstract algebra with number theory.[/quote]
Can you point at a reference that defines prime in terms of the fundamental theorem of arithmetic?

If we were to consider 1 a prime, many theorems would have to be reworded to exclude it. But some other theorems would be simplified. For instance, see Wilson's theorem. There are also theorems that need to exclude 2 (example), but that doesn't mean that 2 isn't prime.

Yep. But this isn't really related to what we're talking about, which is the definition and whether 1's exclusion is a convention or a consequence of something deeper. Not the consequences of things being different.
[/quote]

It is very much related to what we are talking about. From Wikipedia:

Most early Greeks did not even consider 1 to be a number,[4] so did not consider it a prime. In the 19th century however, many mathematicians did consider the number 1 a prime. For example, Derrick Norman Lehmer's list of primes up to 10,006,721, reprinted as late as 1956,[5] started with 1 as its first prime.[6] Henri Lebesgue is said to be the last professional mathematician to call 1 prime.[7] Although a large body of mathematical work is also valid when calling 1 a prime, the above fundamental theorem of arithmetic does not hold as stated. For example, the number 15 can be factored as 3 · 5 or 1 · 3 · 5. If 1 were admitted as a prime, these two presentations would be considered different factorizations of 15 into prime numbers, so the statement of that theorem would have to be modified. Furthermore, the prime numbers have several properties that the number 1 lacks, such as the relationship of the number to its corresponding value of Euler's totient function or the sum of divisors function.[8][9][/quote]

As you see, the justification for not considering 1 a prime precisely has to do with the fact that many theorems would have to make exceptions for 1.

This quote alone supports my claim that 1 not being a prime is pure convention:

In the 19th century however, many mathematicians did consider the number 1 a prime.[/quote]
It's not like they made a mistake by considering 1 a prime: They simply used a different convention. I am not saying that all conventions are equally valid: There are valid reasons to prefer the current one. But thinking that the convention is a consequence of the definition and not the other way around is the wrong way to look at it.

On a side note, if an integer can't be divided by 2 then it also can't be divided by any other even number, so you can try 2 and then only try odd numbers from 3 to sqrt(x), where x the integer that you check for primality.

On a side note, if an integer can't be divided by 2 then it also can't be divided by any other even number, so you can try 2 and then only try odd numbers from 3 to sqrt(x), where x the integer that you check for primality.

Yes, you can also check 2 and 3 first, and then you only need to check division by multiplies of 6 plus 1 and multiples of 6 minus 1. That's usually how I implement trial division.

If you want to test larger numbers, you probably want to use the probabilistic Miller-Rabin test.