Why is this verifier for primality wrong? We are provided with the following verifier of primality:

Verifier for prime

Input: integer n ≥ 1
       integer d

if 1 &lt; d &lt; n and d divides exactly n then
    return ’no’
else
    return ’yes’


But the answer is that it is wrong:


  Note that in order to be a verifier it is required that for every n, n
  is a positive instance (that is, n is a prime) if and only if there
  exists one d such that the verifier with input n and d returns ’yes’.
  However, in the algorithm for Primes we have that n is a negative
  instance if and only if there exists one d such that the verifier with
  input n and d returns ’no’.


But I do not understand this answer or why "in order to be a verifier it is required that for every n, n is a positive instance (that is, n is a prime) if and only if there exists one d such that the verifier with input n and d returns ’yes’"
Here are the semantics of a verifier for primality. The verifier gets two inputs, an integer $n$ and a witness $w$. The following two properties must hold"


Soundness: if the verifier accepts $n$ and $w$, then $n$ is prime.
Completeness: if $n$ is prime, then there is a witness $w$ such that the verifier accepts $n$ and $w$.


We also usually ask that the verifier run in polynomial time in $n$.

Your verifier isn't sound (take any odd composite $n$ and $d = 2$) but is complete.

However, if you flip the return value, you do get a verifier for compositeness:


If $d \mid n$ and $1 &lt; d &lt; n$ then $n$ is composite.
If $n$ is composite then there exists $d$ such that $d \mid n$ and $1 &lt; d &lt; n$.


The notion of a verifier is asymmetric. Your verifier works for compositeness, but not for its complement, which is primality.