# How many ways can we define prime number?

So the other day I was in an interview for a PhD program, one of the professors asked me to give the definition of a prime number. So I gave him the following usual definition-

Any positive number $$p>1$$ is called a prime number if the only divisors of $$p$$ are $$1$$ and $$p$$ itself.

Then he asked me what are the other definitions of a prime number? To which I had no answer as I don't know any other definition. Then he said the following-

A natural number $$n > 1$$ is a prime number if and only if $$(n-1)!=-1 (\text{mod} ~n).$$

Which is basically the statement of Wilson's theorem.

My question is, can we use these kind of results//theorems as definitions of prime numbers?

If I say, "for any natural number $$n>1$$, if $$\phi(n)=n-1,$$ then $$n$$ is a prime, where $$\phi$$ is Euler's Totient function." would also qualifies to be a definition of prime number?

If so what are the other definitions of prime numbers?

Thanks for any valuable input.

Edit: So from the comments I got several examples, thanks for that, I got the idea. So now I want an answer to the question, can we use these kind of results//theorems as definitions of prime numbers?

• If we allow Wilson's theorem to be considered a definition of a prime number - instead of viewing it as a corollary of primality by what one could call "the" definition (which you gave) - then it feels like any of the foolproof primality tests would warrant a valid definition of prime. – Eevee Trainer Mar 12 at 2:13
• A prime number could be defined as the generators of the prime ideals of $\mathbb_{Z}$. – Chip Hurst Mar 12 at 2:15
• Or the positive integers for which $\Bbb{Z}/p\Bbb{Z}$ is a field. – Servaes Mar 12 at 2:16
• One of the most important ways you can define a prime integer $p$ is as an integer for which the implication $p\mid ab$ implies $p\mid a$ or $p\mid b$ holds for all integers $a,b$. – JMoravitz Mar 12 at 2:21
• The points of discontinuity of $\pi(x) = R(x) - \sum_\rho R(x^\rho) -1/\ln(x) - \tan^{-1}(\pi/\ln x)/\pi$, where $R$ is the Riemann R function and $\rho$ is a nontrivial zero of the zeta function. – eyeballfrog Mar 12 at 2:26

Just like Wilson's theorem (a positive integer is a prime if and only if ....) any equivalent statement is handy when we want to show a number is prime. If we encountered a number in a situation where congruence condition of its factorial is available then it is good to use that for testing primality.

Logically any of the "if-and-only-if theorems" can be taken as a definition.

But human beings who discover theorems are not logical machines. While learning a subject, a formulation that uses less preliminary concepts is helpful; So the theorem "$$n$$ is a prime iff $$Z/nZ$$ is a field", is not suitable as a definition.

Accepted textbooks use that formulation of definition which makes it easy to digest and understand the subject, even if the subject did not evolve that way historically!

Take the statements of any of the deterministic pirmality tests. Each of their converse gives a new definition of primes.

I'm going to elaborate on the comment that a number $$p$$ is prime if $$p \mid ab$$ means either $$p \mid a$$ or $$p \mid b$$.

Consider for example $$p = 14$$. That's not actually prime, but indulge me for a minute. Check that $$14 \mid 112$$ and $$112 = 7 \times 16$$. However, $$14 \nmid 7$$ and $$14 \nmid 16$$ either. Therefore $$14$$ is not prime. However, $$2$$ and $$7$$ are prime, since for any choice of $$a$$ and $$b$$ such that $$ab = 112$$, you will see that either $$a$$ or $$b$$, maybe both, are divisible by $$2$$ and/or by $$7$$.

The definition you gave is equivalent to saying if $$ab = p$$, then either $$a$$ or $$b$$ is a unit (like $$-1$$). And that definition is fine until you venture out to domains of numbers other than $$\mathbb{Z}$$. For example, are the numbers $$3 \pm 2 \sqrt{10}$$ prime? Yes, they are. How about $$\sqrt{10}$$? It satisfies the $$ab = p$$ definition but not the $$p \mid ab$$ definition.