(1st question)

We need to guess a Prime number between 2 to 10^9(inclusive) in M questions.

Here's how it works:

- We can give the computer a number x(1 to 10^9).the computer replies with x^2%P.

- We need to tell the value of P.

(2nd question)

The modified question is:

- The computer could change the value of P, whenever it wants. But, the changed value also satisfies the Above asked queries and their results.

The number of queries of M, should be less than equal to 5. for first part, and 2 for 2nd question.

I know We need to apply fermat's little theorem on it. but due to the large range am getting lost most of the times. I can't really think how to really approach this. Please guide me a little.

Thank you.