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?

After a bit of thinking, I decided that my first thoughts were more useless than I had previously thought.

Oracle 2:  After using my class time in school today to think about this, I think I understand what it's getting at.  I think saying m/n mod p is a better way of describing it.  It basically outputs the only integer solution of k=(m+jp)/n, where j is any integer.  We could also add a multiple of p to n, but I found through a bit of experimenting and equation-manipulating that it doesn't matter.  It would probably be best to use n mod p for n, as that would be simplest.

I was trying to program my calculator with oracle 2, since as someone (I think it was Douglas Adams) once said, the best way to learn something is to teach it to something very stupid.  Unfortunately, I couldn't do it without reiteration or trial and error.  Oracle 2 is probably very useful.
__________________

So, the readers having skipped the last two paragraphs, I think that one excellent use for oracle 2 would be to verify any answer.  If we input (-1,x) for (m,n), we should get x.

Other uses for Oracle 2 include finding m mod p, just by making n=1.  Also, if m and n are below p, and m is divisible by n, then we can find m/n.  Perhaps some sort of multiplication is possible, since with division, we can easily find an "inverse" and divide by it.
__________________

Time for some experimentation.  Let's just say p is 13.  Let's find some "inverses"

1/1 mod p = 1
1/2 mod p = 7
1/3 mod p = 9
1/4 mod p = 10
1/5 mod p = 8
1/6 mod p = 11

Using these inverses, I'll make a multiplication table of sorts.  I divide the number above by the inverse of the number to the left.

  1  2  3  4  5  6
1 1  2  3  4  5  6
2 2  4  6  8 10 12
3 3  6  9 12  2  5

I would continue, but it seems pretty clear to me that this works perfectly.  If oracle 2 is the function f(m,n), then f(m,f(1,n)) is equal to nm mod p.

Edit: one last thing I want to squeeze in here:

To Jer:  It is not hard to prove that if x is a solution that -x is a solution, as x^2 is equal to (-x)^2.  If -x is a solution, p-x is also a solution.

Edited on May 2, 2005, 11:05 pm

Posted by Tristan on 2005-05-02 22:59:24