Argthtjtr

Take $mathbb Z$ and $12$.

$12$ is divided by $4$.

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

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

$4 mid 4 implies 4 mid 2cdot2$, 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,bin R$ and $p|abrightarrow 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$:

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

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$.

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|c$. 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_{sin 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$.

Here's how I would reword it:

An element $p$ of a ring $R$ is called prime if for any 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.