# Alternate definition of prime number

I know the definition of prime number when dealing with integers, but I can't understand why the following definition also works:

A prime is a quantity $p$ such that whenever $p$ is a factor of some product $a\cdot b$, then either $p$ is a factor of $a$ or $p$ is a factor of $b$.

For example, take $4$ (which clearly is not a prime): it is a factor of $16=8\cdot 2$, so I should check that either $4\mid 8$ or $4\mid 2$. But $4\mid 8$ is true. So $4$ is a prime, which is absurd.

Please note that English is not my first language, so I may have easily misunderstood the above definition.

Edit: Let me try formalize the definition as I understood it: $p$ is prime if and only if $\exists a\exists b(p\mid a\cdot b)\rightarrow p\mid a\lor p\mid b$.

-
The «whenever» means «for all», and you only considered one particular choice of $a$ and $b$ such that $p\mid a\cdot b$. –  Mariano Suárez-Alvarez Sep 8 '10 at 11:32
You could replace "whenever" by "every time" in your definition to help make it clearer. Some students with English as a mother tongue are often tripped up by the use of the word "whenever" when they encounter it for the first time in mathematics. –  Derek Jennings Sep 8 '10 at 12:41
By the way, if you accept your definition (in your Edit), then every number $p$ becomes a prime. Take $a=1$ and $b=p$. Even better, take $a=b=1$. (Note that nothing in that sentence told us that $p$ should in fact divide $ab$ or $a$ or $b$. So the implication is true.) –  Srivatsan Sep 1 '11 at 10:40

Note that this is whenever.

$4|4 = 2\cdot 2$ however $4\not{|}2$.

To the edited question:

No! The word "whenever" comes to say that $p$ is prime if $\forall a \forall b (p | a\cdot b \Rightarrow (p | a \vee p | b))$

-

If you're willing to accept the fundamental theorem of arithmetic (which can be proved by elementary -i.e., "ideal free"- methods, see the link) that states that any integer different from $\pm 1$ can be written as a unique product (up to ordering of the factors) of prime numbers, then the equivalence of both definitions of prime numbers

$$(\ m \vert p \ \Longrightarrow \ m = \pm 1 \ \text{or} \ \pm p \ ) \qquad \Longleftrightarrow \qquad (\ p \vert ab \ \Longrightarrow \ p \vert a \ \text{or} \ p \vert b \ )$$

is clear:

[Warning. If you feel more comfortable working only with positive integer numbers, then just drop those $\pm$ all over this answer.]

$(\Longrightarrow)$ If $p\vert ab$, then $ab = pq$ for some integer $q$. Since both $ab$ and $pq$ can be uniquely written as a product of prime numbers, $p$ must be a prime factor of $ab$. But prime factors of $ab$ are necessarily prime factors of $a$ or $b$, again by the uniqueness of the fundamental theorem of arithmetic. So, $p$ is necessarily a prime factor of $a$ or $b$; that is, $p\vert a$ or $p\vert b$.

$(\Longleftarrow)$ Again, if $m\vert p$, all prime factors of $m$ must be prime factors of $p$. But the only prime factors of $p$ are $\pm p$. So, either $m = \pm p$, or $m=\pm 1$.

Of course, there is little (big?) circular argument here, because one already uses implication $(\Longrightarrow)$ in the proof of the fundamental theorem of arithmetic. This implication is called Euclid's lemma. But it can be proved by elementary methods too, that rely on Bézout's identity (whith elementary proof too: see the last link).

So, as you can see, everything is elementary, but, perhaps, too long for a single answer and to remember in one go. While reasoning using the fundamental theorem of arithmetic may be seen as little short cut easier to remember the next time you have any doubt about the equivalence of both definitions of prime number.

(In fact, a number satisfying the left hand side condition is called "irreducible", while $p$ on the right hand side is called "prime". So "prime = irreducible", at least for integer numbers.)

-
Exactly, I think that the difference between irreducible and prime should be kept in mind even in UFDs –  Andy Sep 9 '10 at 14:17
For a very simple proof that irreducible integers are prime see Gauss's proof in my post math.stackexchange.com/questions/3230 –  Bill Dubuque Sep 11 '10 at 3:19

As far as I know, your definition

A prime is an element p such that whenever p divides ab, then either p divides a or p divides b,

is the true definition of "prime". The usual one,

... an element p which cannot be expressed as a product of non-unit elements,

is the definition of an irreducible element. Now, in every ring all primes are also irreducible, but the converse is in general not true. In other words, there are rings where the two definitions are not equivalent. One case in which they are indeed equivalent is when the ring is a unique factorization domain (the statement of the so-called "fundamental theorem of arithmetic" is that the integers form one such ring).

-
I believe Agusti already said this in his answer. +1 for spelling it out, anyway. –  Aryabhata Sep 11 '10 at 1:35
@Moron: Whenever I read your comments the first impression is they're intended as an insult, because of the "-- Moron" at the end. –  Ryan Budney Sep 20 '10 at 0:45
@Ryan: :-) I used this name on other sites and it has stuck. Probably too late to change it. –  Aryabhata Sep 20 '10 at 2:42

You have encountered the general ring-theoretic definition of a prime (versus irreducible) element. For general rings one distinguishes between the inequivalent properties of being irreducible, i.e. having no nontrivial factors, and being prime, i.e a nonunit such that if it divides a product then it divides some factor of the product. The latter property is key to unique factorization since one easily proves by induction that products of primes factor uniquely in any domain, i.e. a ring such that $\rm\; ab = 0 \;\Rightarrow\; a=0\ \ or\ \ b=0$.

Here are the precise definitions. Let $\rm\; a,b,p \;$ be elements of a domain $\rm\:Z\:$.

DEFINITION $\rm\quad\; a\;$ is a unit $\ \$ if $\rm\ \ a\: |\: 1\quad\quad\quad\ \ \:\; (\:a\ |\ b\ :=\ a\ \ divides\ \ b\:)$

DEFINITION $\quad$ nonunit $\rm\; p\;$ is $\quad\;$ prime $\quad\;$ if $\;\;\;\rm p \;\;\:|\:\;\; ab \;\;\Rightarrow\;\; p|a \;\;\; or \;\;\; p|b$

DEFINITION $\quad$ nonunit $\rm\; p\;$ is $\:$ irreducible$\;$ if $\;\;\:\rm p = ab \;\;\Rightarrow\;\; p|a \;\;\; or \;\;\; p|b\quad\;\;$ (a.k.a.$\:$ atom)

COROLLARY $\quad\;$ prime $\;\;\Rightarrow\;\;$ irreducible, since $\;\;\;\rm p = ab \;\;\Rightarrow\;\; p|ab$

Conversely $\:\;$ irreducible $\;\Rightarrow\;\;$ prime $\;\;$ iff $\;$ factorizations into irreducibles are unique (upto order and units). Indeed, it is very easy to prove that a factorization into primes is unique, i.e. any other factorization into irreducibles is the same (upto order and units).

-