IBM Ponder This #325 · May 2025

Imagine the following scenario: You are entering an empty classroom. The board only says "Arithmetic in F_{?????}" from which you understand the class involved computations over the prime field $F_p$ for some prime $p$, but you don't know which $p$.

It seems the students received their graded work, which lies on some of the tables. Each worksheet consists of the same multiple choice questions, and the grading marks the number of correct answers, without specifying which answers were correct.

(This illustration might not be accurate!)

It seems the questions, along with their possible answers, are:

5x_2 + 7x_3 + 5x_5 + 3x_6 = ?
A: 2416 B: 2415 C: 2413 D: 2412

8x_1 + 5x_2 + 2x_5 + 5x_8 = ?
A: 7624 B: 7622 C: 7621 D: 7625

7x_1 + 4x_2 + 5x_4 + 2x_5 = ?
A: 638 B: 642 C: 633 D: 637

7x_1 + 9x_3 + x_6 + x_7 = ?
A: 765 B: 761 C: 759 D: 760

8x_3 + 7x_4 + 4x_5 + 3x_6 = ?
A: 2211 B: 2212 C: 2217 D: 2216

2x_3 + 5x_4 + 5x_6 + 5x_7 = ?
A: 3497 B: 3501 C: 3496 D: 3499

5x_2 + 4x_4 + 6x_5 + 7x_6 = ?
A: 4007 B: 4010 C: 4008 D: 4013

7x_3 + x_4 + 8x_6 + 8x_7 = ?
A: 5531 B: 5535 C: 5538 D: 5534

x_1*x_2*x_3*x_4*x_5*x_6*x_7*x_8 = ?
A: -4 B: 1 C: 5 D: 4

x_1*x_3*x_5*x_7 = ?
A: 6544 B: 6546 C: 6545 D: 6550

It seems all these questions deal with computations over $F_p$ with eight unknown quantities, $x_1,\dots ,x_8$. Try as you might, you can't find any indications to the values of $x_1,\dots ,x_8$ anywhere; they must have been on the board and erased. Collecting the answers of the students along with their grade, you obtain

BABBDDCDCA 6/10
DADBDDAACD 6/10
CADBDBCDCC 7/10
DACBDDCBCB 6/10
DCBBDDCDAB 6/10
DDDBDDCDBD 8/10
DADBDDCCCC 8/10
CADBDDDDAC 7/10

Your goal: Find $p$.

A bonus "*" will be given for solving this followup question: After determining $p$, you encounter a second set of tests. This time, the board says "q(x) = x^{20}+???...?" so you understand you are dealing with a monic polynomial of the 20th degree, but most of it is erased.

The questions you find are now

q(5698) = ?
A: 5146 B: 5142 C: 5149 D: 5147

q(1616) = ?
A: 3715 B: 3725 C: 3720 D: 3716

q(1338) = ?
A: 2547 B: 2548 C: 2549 D: 2550

q(7821) = ?
A: 6624 B: 6628 C: 6619 D: 6627

q(4461) = ?
A: 4661 B: 4660 C: 4659 D: 4662

q(2156) = ?
A: 5112 B: 5107 C: 5106 D: 5102

q(7559) = ?
A: 3916 B: 3921 C: 3913 D: 3917

q(5812) = ?
A: 2340 B: 2342 C: 2345 D: 2344

q(794) = ?
A: 6210 B: 6212 C: 6217 D: 6215

q(2595) = ?
A: 3642 B: 3644 C: 3646 D: 3641

q(1640) = ?
A: 1581 B: 1584 C: 1586 D: 1583

q(6779) = ?
A: 6543 B: 6536 C: 6541 D: 6544

q(8362) = ?
A: 3823 B: 3828 C: 3824 D: 3832

q(4605) = ?
A: 5601 B: 5598 C: 5602 D: 5595

q(420) = ?
A: 1272 B: 1274 C: 1278 D: 1275

q(8724) = ?
A: 4410 B: 4420 C: 4415 D: 4412

q(3669) = ?
A: 8974 B: 8973 C: 8976 D: 8971

q(1869) = ?
A: 6723 B: 6720 C: 6728 D: 6721

q(7516) = ?
A: 8244 B: 8247 C: 8246 D: 8243

q(1386) = ?
A: 1571 B: 1570 C: 1569 D: 1568

q(4529) = ?
A: 5504 B: 5501 C: 5503 D: 5506

With answers

CCCDDCAADCCCBBDABDBAD 9/21
ADDACCADDDDBACDDBADCD 11/21
DCBABBAADDACBBAAAABDC 12/21
ACAAABABDDDBACAABADDC 11/21
CABAAAABDBDCCBDCBDBCC 12/21
DDDADCADDBDABBDBCADCC 12/21
ACDBBDAADDDABDCBCBCAC 9/21
AABCBDACDBADBDDCDACCB 10/21
BABBBBABAABCBDBCDACCA 9/21
ACCBABADDDDDBBCDDBACC 12/21
ACDBCBBDBDDCBCCADBCAA 9/21

Your goal is to determine $q(1)$.

Solution

Best opened after a real attempt

To be added.