I'm not sure how it works with the example of the primes, I lost the link to the later pages of the game so I can't read over it again, but I think it's guaranteed because there's just one number encoding all the assignments and you just get to unlock a single pair with the key given in response to your choice. There's an assumption that there isn't enough information in the key to fake any response, it has to reveal something that was already in there.