The Least Nonresidue

All submissions due by 2pm on Friday, April 17.

We have seen that, if p is an odd prime number, then exactly half of the numbers 1,2,3,...,p-1 are quadratic residues modulo p. Many questions in number theory, including issues related to the running time of primality testing algorithms, relate to how exactly the quadratic residues distribute themselves among these p-1 numbers.

Of particular interest in many contexts is the value of the least nonresidue, which is the smallest positive number that is not a quadratic residues modulo p. The conventional wisdom is that the first nonresidue tends to be very small (with order of magnitude close to the number of digits of p). This should be plausible: if half of the numbers from 1 to p-1 are nonresidues, then it shouldn't take long to encounter one. However, the question of exactly how long you might have to wait to find a nonresidue remains elusive, and is related to several topics of modern research.

The goal of this task is to write a program to gather experimental data about this question. Your program will receive an interval (a range of numbers), and find the largest possible value for the least nonresidue for all primes in this interval.


The first line gives the number of test cases, T. T test cases follow. Each case consists of a single line with two integers p_min p_max, which gives the upper and lower bounds for the interval of numbers in question.


For each test case, output one line of the form "Case #X: L P". X is the case number (starting from 1). L is the largest possible value of the least nonresidue modulo a prime chosen between p_min and p_max, inclusive. P is the prime number from the interval that achieves this maximum. If there is a tie, i.e. multiple prime numbers in the interval have least nonresidue L, then P should be the smallest one.


T = 100
3 ≤ p_minp_max
There is guaranteed to be at least one prime number between p_min and p_max, inclusive.

Small dataset:
p_max ≤ 106

Large dataset:
p_max ≤ 1018


Input Output
3 7
97 97
3 100
10000 20000
Case #1: 3 7
Case #2: 5 97
Case #3: 7 71
Case #4: 29 18191

Note in particular that the ends of the interval are inclusive. For example, in case 2, 97 is the only number in the interval (and it is prime).

Hints and remarks

For the small input, you can write a program which first identifies primes (for example, by checking for divisors up to the square root of each number), and then explicitly lists the quadratic residues of each prime in the specified interval.

To complete the large input, you'll need two ingredients: an efficient way to detect primes (such as the Miller-Rabin test), and an efficient way to compute the Legendre symbol (I suggest making using of quadratic reciprocity).

Input and output files

Small inputs: 0 1 2 3 4 5 6 7 8 9
Large input: