Number systems violating easy primes Many students are surprised to learn that the definition of prime is not generally “only divisible by 1 and itself” for general number systems. 
What are some examples of numbers systems for which $p|ab$ implies either $p|a$ or $p|b$ is not equivalent to the definition $p$ only is divisible by 1 and itself? And explicit constructions if violating numbers in these systems?
 A: In more general systems, these two notions are different and have different names:


*

*"irreducible" means something that cannot be further decomposed. 

*"prime" means something that divides at least one factor of a product if it divides the product.
Consider the set $2\mathbb N$.
Then $30$ is an irreducible element of $2\mathbb N$. Now, $30$ divides $60=6\cdot10$ but does not divide $6$ or $10$. Therefore, $30$ is not prime in $2\mathbb N$.
Another classical example is the Hilbert monoid $4\mathbb N+1$. Then $21$ is irreducible but not prime because $21$ divides $9 \cdot 49$ but does not divide $9$ or $49$.
In both systems, the numbers can always be decomposed into products of irreducibles but this decomposition is not always unique because not every irreducible is prime.
A: If you want an example which is an integral domain, consider the ring $\mathbf{Z}[i \sqrt3]$ which consists of complex numbers of the form
$$
z = a + b i \sqrt{3}
,\qquad
a,b \in \mathbf{Z}
.
$$
Then
$$
4 = 2 \cdot 2
$$
and
$$
4 = (1+i \sqrt3)(1-i \sqrt3)
$$
are two essentially different factorizations of $4$ into irreducible elements.
That the numbers $z=2$ and $z=1 \pm i \sqrt3$ are irreducible in this ring can be seen by contemplating the $\mathbf{Z}$-valued function $N(z)=|z|^2=a^2+3b^2$ which has the multiplicative property $N(z_1 z_2)=N(z_1)N(z_2)$. Since $N(z)=4$ in both cases, and $N=1$ only for the invertible elements $\pm 1$, a nontrivial factorization $z=w_1 w_2$ would have to have $N(w_1)=N(w_2)=2$, but the ring contains no elements with $N=2$.
On the other hands, those numbers cannot be prime in this ring,
since a factorization of a ring element into primes is always essentially unique (i.e., unique up to reordering and multiplication by invertible elements), and we saw two different factorizations of $4$ above.
