Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is it correct to represent a prime number like this?

$$\exists k \in \mathbb N,\, \exists n\in \mathbb N\, \Big((n\mid k) \land (n=k \lor n=1)\Big)$$

share|cite|improve this question
Are you going to accept the other answers? – ILoveMath Nov 5 '13 at 0:56
@DonAnselmo, I definitely didn't know I had to do that... I kept clicking an arrow whenever I got an answer. – JOX Nov 5 '13 at 0:59
You seem to want a formula $\varphi(n)$ if and only if $n$ is prime. Your formula does not work. Depending on details of language, and what the variables range over, something like $\forall x\forall y((xy=n)\implies ((x=1)\lor (y=1)))$ will work. – André Nicolas Nov 5 '13 at 2:16
You are looking for a predicate $\phi(n)$, a formula that is true when $k$ is prime and false when $k$ is not prime. You can think of it as a function from $\Bbb N$ to $\{$True, False $\}$. You don't want to quantify over $k$, because the value depends on $n$. Joe Johnson 126 has given a good answer to that, but I wanted to show this part of the thought. – Ross Millikan Nov 5 '13 at 17:38
up vote 1 down vote accepted

What you have claimed is that there are two natural numbers, $n$ and $k$, such that $n$ divides $k$ and $n=k$ or $n=1$. This is true. For instance, let $k=5$ and $n=1$. What you want is that $k$ is prime if whenever $n$ divides $k$, $n$ must be $1$ or $k$. That is, if $k$ is prime then $$ \forall n\in \mathbb{N}, \left((n\mid k)\Rightarrow (n=1)\vee (n=k)\right). $$

share|cite|improve this answer
But in a more general way that would be false... If k were 6 and n = 3, then if 3|6 => n=1 or n=6 would be false! I am looking for an expression that helps me determine if a number is a prime... – JOX Nov 5 '13 at 1:22
@Daniel If you let n=3 and k=6, then the statement would be false and thus 6 is not prime. – GAM Nov 5 '13 at 1:25
A nit: this returns true for $k=1$, so you need to exclude that. – Ross Millikan Nov 5 '13 at 17:38

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.