We are provided with the following verifier of primality:
Verifier for prime
Input: integer n ≥ 1
integer d
if 1 < d < 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’"