At this year's state mental math competition, contestants will be given a prime number p<10,000 of the form 4k+1 and will be asked to find an integer x such that x²+1 is divisible by p, in less than 10 minutes. Each contestant will also be given access to two oracles:

Oracle 1: When given any integer n, outputs n².

Oracle 2: When given any integers m,n not divisible by p, outputs a number k such that kn-m is divisible by p. (In math-speak, this outputs m/n (mod p).)

Each oracle takes 1 second to respond.

You are going to enter this competition, but unfortunately, you are not great at mental math. In fact, all you know how to do in your head is add and subtract numbers. Furthermore, it takes you one second to perform such an operation.

Of course, you can also perform the most basic comparison operations in your head (m<n?, m>n?, m=n?). These also take you one second to perform.

Fortunately, you have a good short term memory, so you can keep track of and instantly access as many numbers in your head as you would like. Trying to fill your memory before the competition will be problematic, however, as your long term memory is bad.

How can you ensure success at this competition?

OK, I'm new at this, so bear with me.

This is the "loop".  I will put it as if it were a program, but not specifically like any programs.  The numbers are just for listing purposes, but they also act as time indicators, since everything takes one second.

1 Let n=1

2 To "Oracle 1", input "n"= n

3 To "Oracle 2", input "n"= Output "Oracle 1", "m" = -1

4 If Output "Oracle 2" = 1, then let x = n; If Output "Oracle 2" > 1, then let n = n + 5; If Output "Oracle 2" < 1, let n = n - 1

Since the largest prime they can give you is 9973 (largest prime under 10,000), and the smallest multiple that oracle 2 can calculate is 2 times that, which is 19,946.  If so, the maximum x value you could have is technically 141.22676800097069416754994263139 (square root of 19,945).  So if the "program" skips five by five, the maximum n value you can get to is n = 145, then take four steps back to n=141.

Therefore, 145 + 4 = 149 loops.  Four steps each, all involving one second.  Therefore 149 loops * 4 secs/loop = 596 seconds.

The limit is 10 minutes, or 600 seconds, so even for the largest prime, you'll have four full seconds to bask in the glory :p

Posted by Alexis on 2005-10-30 10:06:31