All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Algorithms
Mental Math Competition (Posted on 2005-04-29) Difficulty: 5 of 5
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?

See The Solution Submitted by David Shin    
Rating: 2.2000 (5 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Some Thoughts some things I noticed | Comment 3 of 7 |

I started by choosing p=1009 (=4*252+1) and I managed to find x=469 where 469^1 + 1 = 219962 = 1009*218.
This didn't help much (and I used the unallowed operations multiplication and square root)

So I chose smaller p's

p=5
5*1  = 2^2 +1
5*2  = 3^2 +1
5*10 = 7^2 +1
5*13 = 8^2 +1
5*29 = 12^1 +1

notice that x is either 2 or 3 mod 5
The same thing happened when I tried 13, 17, and 29:  there were only two values for x mod p and these values summed to p.

I haven't proven this always holds but if it does then the smallest x will be less than 5000.

It is easy to see that if
p divides x^2 +1 then
p divides (x+p)^2 +1


  Posted by Jer on 2005-05-02 17:44:43
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (7)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information