Why doesn't the definition "$p$ is called 'prime' if $p\mid ab\implies p\mid a\,\text{ or }\,p\mid b$" hold up when we square numbers?

Question

So, I've been given the actual definition of a prime for the first time, as opposed to the definition of an irreducible which I was previously taught (as is customary), it goes as follows:

An element $p$ of a ring $R$ is called "prime" if $a,b\in R$ and $p|ab\rightarrow p|a$ or $p|b$

$4^2 = 16$. So inversely $4|16$. Now let's look at all the combinations of two integers $a,b\in R$ where $ab = 16$ and whether $p|a$ or $p|b$:

$1 * 16$ ($4|16$)

$2 * 8$ ($4|8$)

$4 * 4$ ($4|4$)

By my logic, $4$ is prime.

However, as we all know $4 = 2^2$. But $2$ is not a unit so $4$ is an irreducible. Since the ring of integers is an integral domain $4$ must, therefore, be prime as well. Why does this happen?

Edit

Thanks for your help everyone. I understand your answers logically and experimentally but not really conceptually. The reason this definition works (from my perspective) because your saying that

A number is prime if it necessary to represent its multiples in factorisations.

Whereby factorisations, I mean $8 = 2^3, 6 = 2*3$ and relevantly $16 = 2^4$.

The answer I had kind-of expected from this question (and was going to include in my original query until I forgot) was that more generally if there exists the product of any amount of numbers that is equivalent to $ab$ and for each of those numbers $n$, $n$ suffices $p|n$ then $p$ is composite.

This makes much more sense to me logically. In the case of $16$ you saying that you don't need $4$ to express $16$ since you can instead use $2*2*2*2$ or $2^4$ to represent the same thing. For this reason, $4$ is composite.

By this logic, you don't need to prove it for every multiple of 4, only 1. Have I completely confused myself? Can someone provide a counter-example? Also, could you provide an explanation of why my logic doesn't work?

Edit 2

Yes everyone, the correct definition of includes checking the factors of every $ab$ such $p|ab$. However, as @Vincent and I showed in our respective answers (the former much better) the definition I used is equivalent to the definition everyone else is using in integral domains. I highly suggest you read @Vincent answer as he makes this very clear.

Regardless, I'm not accepting any answer that simply says that my definition is wrong when it is actually equivalent.

Answer 1

Take $\mathbb Z$ and $12$.

$12$ is divided by $4$.

$12=6\cdot2$, but $6$ is not divided by $4$ and $2$ is not divided by $4$, which says that $4$ is not prime.

Answer 2

Let's take a step further from your last line:

$4 \mid 4 \implies 4 \mid 2\cdot2$, but $4 \mid 2 $ does not hold, so $4$ is not a prime. (We have $a = b = 2$, $p=4$)

---

Going back to your definition:

An element $p$ of a ring $R$ is called "prime" if $a,b\in R$ and $p|ab\rightarrow p|a$ or $p|b$

As was mentioned in the comments, the implied requirement is that this applies for all $a$ and $b$.

You're trying the case of $4$ being prime, so $p=4$. Letting $a=2$ and $b=2$ is a counterexample, which shows that $4$ is not a prime.

The definition really just says that a multiplication can't make new prime factors appear, but instead all prime factors must be present in the composition of (at least one of) the multiplied items.

---

If it were enough to find just any one pair $a,b$ satisfying $p|a$ and $p|b$ to make $p$ a prime, then we could easily prove that any number is prime. It would be simplest to let $a = b = p$, but that's the squaring you already did. So let's try with e.g. $a = 12$, $b=18$, $p=6$:

$6\mid 216$ and $216 = 12\cdot 18$, so since $6\mid 12$ and $6\mid 18$, then $6$ is prime. This is of course nonsensical.

Answer 3

Going back to your example, with $p=16$.

If I choose $a=12$ and $b=4$, then I have $p | ab$, but neither $p|a$ nor $p|b$. Hence, $p$ is not prime.

The definition requires that you consider any $a, b$ such that $p|ab$, not only those such that $p=ab$.

Answer 4

This is an answer to the accepted answer more than to the question, but I believe that that is ok, since both are posed by the same poster.

NOTE: I CHANGED SOME THINGS AFTER READING DARIJ'S COMMENT

The question seems to be which of four definitions of prime element is the 'correct' one. I restate the definitions here, but let them define four different types of elements (prime1, prime1', prime2, prime3). The reason for this somewhat awkward notation is that it enables us to say things like 'The element $4 \in \mathbb{Z}$ is prime2 but not prime1' and know exactly what we are talking about.

So here are the definitions.

An element $p$ in a ring $R$ is called prime1 if it is not a unit and $\forall a, b \in R$ such that $p|ab$, we have that $p|a$ or $p|b$. This is the definition used in most of the other answers.

An element $p$ in a ring $R$ is called prime1' if it is not a unit and $\forall c \in R$ such that $p|c$, and for all $a, b \in R$ such that $ab = c$, we have that $p|a$ or $p|b$. This definition appears in the accepted answer, although at that point the OP seems to have stopped believing that it is the correct one.

I use the names prime1 and prime1' to emphasis that these definitions are really identical. Just try to think for 2 seconds what you would need to do to show that an element $p$ is not prime1 or not prime1'. In both cases it amounts to the same thing: find two elements ($a, b$) that are not divisible by $p$ while their product ($c$) is.

Things get more interesting when we invoke the other two definitions.

An element $p$ in a ring $R$ is called prime2 if it is not a unit and $\exists c \in R$ such that $p|c$ and $\forall a, b \in R$ such that $ab = c$ we have that $p|a$ or $p|b$. This definition is nowhere written out explicitly but it is very strongly implicitly present in the original question.

An element $p$ in a ring $R$ is called prime3 if it is not a unit and $\forall c \in R$ such that $p|c$, and for all finite $S \subset R$ such that $\prod_{s \in S} = c$, there is an $s \in S$ such that $p|s$. This definition is proposed by the OP in the accepted answer as the "correct" one.

Now the content of the original question is that the number $4 \in \mathbb{Z}$ is prime2, showing that 'prime2-ness' is not a good way of generalizing 'primeness' (primality) of integers to arbitrary rings. Very nice, I never thought of that before. However, for now that means that prime2 is out as a candidate definition of "prime" and the race is between prime1 and prime3. (I ignore prime1' for the moment as it is identical to prime1).

The counterexample the OP is asking for seems to be a natural number that is prime3 but not prime in the ordinary sense. In fact it would already be interesting to see any element of any integral domain that is either prime3 but not prime1 or prime1 but not prime3. The point of my answer is: these elements do not exist. Concretely we have:

Theorem 1: let $R$ be an integral domain. Then every element that is prime3 is also prime1

Theorem 2: let $R$ be an integral domain. Then every element that is prime1 is also prime3.

Together the theorems say that the two definitions are equivalent and hence that choosing the one over the other is a matter of taste (or pedagogy) and doesn't change anything mathematically.

I will prove the theorems below.

Proving Theorem 1 is really easy, there is hardly anything to do. We have an element $p$ that is prime3 and elements $a, b$ such that $p|ab$. Taking $c = ab$ and $S = \{a, b\}$ we see that from prime3-ness of $p$ that $p|a$ or $p|b$ which in turn implies that $p$ is prime1. End of proof.

Proving Theorem 2 is a bit more involved.

Let $p$ be a prime1 element of $R$. Let $c$ be any element of $R$ such that $p|c$ and let $S \subset R$ be any finite set such that $\prod_{s\in S} s = c$. We need to show that there is an element $s \in S$ such that $p|s$ in order to show that $p$ is prime3. We do this by induction on the number $n$ of elements of $S$.

The first hurdle we have to tackle is the fact that if $n = 0$ then our goal is unreachable: clearly in an empty set there is no element $s$ such that $p|s$. Luckily this case does not occur! The point is: the product of all elements of an empty set is 1 by definition. But if $c = 1$ and $p|c$ then $p$ is a unit, which contradicts its prime1-ness. So this case cannot happen.

We move on to the case $n = 1$. If $S$ contains only a single element then clearly this single element must be the element $c$, which was the product of all elements. But we already know that $p|c$ and so, indeed, $p$ divides a (or rather: the) element of $S$.

Now let $n \geq 2$ and we suppose that ('Induction Hypothesis') that for all $a \in R$ with $p|a$ and all $S' \subset R$ with $n-1$ elements such that $\prod_{s \in S'} s = a$ we have that $p$ divides some element of $S'$.

We are still working with the $n$-element set $S$ and we label the the elements $s_1, s_2, \ldots, s_{n-1}, s_n$. Let $a = s_1 \cdot s_2 \cdots s_{n-1}$ and $b = s_n$. Then $ab = c$ and hence $p|ab$ and hence, since $p$ is prime1 we have that $p|a$ or $p|b$. In the second case we see that $p|s_n$ and hence we see that $p$ divides an element of $S$ as we wanted to show. In the first case we set $S' = \{s_1, \ldots, s_{n-1}\}$. Since $p|a$ we know from the Induction Hypothesis that $p$ divides some element of $S'$. But every element of $S'$ is also an element of $S$, so in this case we have that $p$ divides an element of $S$ as well, as we wanted to show.

End of proof.

In summary: the new definition from your answer and the old definition from the other answers are equivalent and single out the same elements of $R$.

Answer 5

Here's how I would reword it:

An element $p$ of a ring $R$ is called prime if for every combination of $a, b \in R$ such that $p \mid ab$, at least one of $p \mid a$ or $p \mid b$ also holds true.

So if $p = a = b = 4$ we see that $p \mid ab$ and then $p \mid a$ and $p \mid b$ are trivially true. But that's not the only possible combination of $a$ and $b$ that we can choose so that $p \mid ab$. You have already discovered two more. But there are in fact infinitely many more.

It suffices to choose one in which $a = 2$ and $b \neq \pm 2$ though it is singly even (that is, not divisible by $4$). So, for example, $b = 14$, then we have that $4 \mid 28$ and $28 = 2 \times 14$, but $2$ is not divisible by $4$ and neither is $14$. Hence $4$ is not prime.

I'm sure you can generalize this to the squares of odd primes. Just my two cents.

Answer 6

I think looking at a ring that is not a unique factorization domain would give you some sorely needed perspective.

I suggest $R = \mathbb Z[\sqrt{10}]$, which consists of all numbers $x \in \mathbb Q(\sqrt{10})$ such that $x$ is a root of a polynomial of the form $x^2 + tx + n = 0$, where $t$ and $n$ are just integers good old integers from $\mathbb Z$. Then $x = r + s \sqrt{10}$, $t = -2r$ and $n = r^2 - 10s^2$, and $r$ and $s$ also drawn from from $\mathbb Z$.

Is $\sqrt{10}$ prime? Maybe. We see that $(\sqrt{10})^2 = \sqrt{10} \times \sqrt{10} = 10$. Obviously $\sqrt{10} \mid \sqrt{10}$. However, $10 = 2 \times 5$ and 2 and 5 are also both integers in $R$, they are of the form $r^2 + 0 \sqrt{10}$, and then there is the polynomial with $x = r$, $t = -2r^2$ and $n = r^2$.

If $\sqrt{10}$ is indeed prime, then either $\sqrt{10} \mid 2$ or $\sqrt{10} \mid 5$. But $$\frac{2}{\sqrt{10}} = \frac{\sqrt{10}}{5},$$ which is a root of $5x^2 - 2$, and $$\frac{5}{\sqrt{10}} = \frac{\sqrt{10}}{2},$$ which is a root of $2x^2 - 5$ (in both cases we needed the coefficients attached to $x^2$ to be 1, not 2 nor 5 nor any other number). So $\sqrt{10}$ is in fact not prime.

Looking at ideals, we see that $\langle \sqrt{10} \rangle$ is not a prime ideal either, since it is properly contained in the ideal $\langle 2, \sqrt{10} \rangle$, which is prime. Likewise, if $p$ is a prime number in the domain, we see that $\langle p^2 \rangle$ is properly contained in $\langle p \rangle$.

This sort of thing doesn't happen in good old $\mathbb Z$ because $\mathbb Z$ is a unique factorization domain and all ideals are principal, so all nonzero non-unit irreducibles are prime numbers. But what good does a definition for prime numbers do us if that definition also gives us squares of primes in addition to the primes?

So the choice of $a$ and $b$ is not limited to $p^2$, but to any $a$ and $b$ such that their product is any nonzero multiple of $p$.

Of course "any" $a$ and $b$ suggests that we have to look at every possible combination and there are infinitely many of them. But in fact there is almost always a shortcut, so that then, for example, to prove that 7 is prime in $\mathbb Z[\sqrt{10}]$ we don't need to look at $(-1)(21 - 7 \sqrt{10})(21 + 7 \sqrt{10})$, $(133 - 42 \sqrt{10})(133 + 42 \sqrt{10})$, $(-1)(819 - 259 \sqrt{10})(819 + 259 \sqrt{10})$, etc., which should all have $n = \pm 49$ in the polynomial, wink, wink. Except for the units, of course.

Instead we can just use the Legendre symbol to verify that $x^2 \equiv 10 \pmod 7$ has no solution in integers and therefore $(x - \sqrt{10})(x + \sqrt{10}) = 7m$, where $x$ is any number in $\mathbb Z$ and $m$ is any number in $\mathbb Z[\sqrt{10}]$, is insoluble.

Answer 7

Further to the other comments and answers, and considering just the ring of integers, here's a reformulation of Euclid’s lemma as a definition of prime numbers. Note that the restriction $n\neq1$ needs to be introduced for the reformulation to hold.

$$\forall n\in\{2,3,\ldots\}\bigg(n \text{ is prime}\iff \forall a,b\in \mathbb Z\big(\;p|ab\implies\left(\,p|a\:\lor \:p|b\,\right)\big)\bigg)$$