Puzzle
6 minute read

Ponder This Challenge - May 2025 - The prime arithmetic quiz

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 FpF_{p} for some prime pp, but you don't know which pp.

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 FpF_{p} with eight unknown quantities, x1,…,x8x_1,\ldots,x_8. Try as you might, you can't find any indications to the values of x1,…,x8x_1,\ldots,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 pp.

A bonus "*" will be given for solving this followup question: After determining pp, 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)q(1).

Solution

  • May 2025 Solution:

    The numerical solutions are

    p = 8999
q(1) = 3898

    Finding the correct test results is a standard task for constraint solvers, which can also be performed manually. The data was choses such that there is only one valid solution. Given this solution, the first 8 questions give us a linear equations system which has a solution in integers over the rational numbers, meaning the same solution is also valid over any prime pp. So we first solve this system.
    The next equation tells us that multiplying all the results give us a number NN such that the prime pp we are looking for divides N−1N-1. So we factor N−1N-1 (easy for numbers of this size), and for every prime factor we check whether the last equation holds. Only p=8999p=8999 passes this test.
    In order to find q(1)q(1) one simply find the correct test results and then uses some interpolation method (e.g. Lagrange interpolation) over F8999F_{8999}.

Solvers

  • *Lazar Ilic (30/4/2025 8:07 PM IDT)
  • *Bert Dobbelaere (30/4/2025 8:11 PM IDT)
  • Ruben Menendez (30/4/2025 9:08 PM IDT)
  • *Bertram Felgenhauer (30/4/2025 9:19 PM IDT)
  • *Ankit Aggarwal (30/4/2025 9:35 PM IDT)
  • *Lorenz Reichel (30/4/2025 11:47 PM IDT)
  • Shirish Chinchalkar (1/5/2025 12:46 AM IDT)
  • *Sanandan Swaminathan (1/5/2025 1:42 AM IDT)
  • Reiner Martin (1/5/2025 2:45 AM IDT)
  • *Joydeep Pal (1/5/2025 7:29 AM IDT)
  • *Yi Jiang (1/5/2025 8:18 AM IDT)
  • Rohan Kansal (1/5/2025 8:39 AM IDT)
  • *Nadir S. (1/5/2025 9:05 AM IDT)
  • *Stephen Ebert (1/5/2025 10:48 AM IDT)
  • Giorgos Kalogeropoulos (1/5/2025 12:48 PM IDT)
  • *Juergen Koehl (1/5/2025 1:54 PM IDT)
  • *Alper Halbutogullari (1/5/2025 1:56 PM IDT)
  • *Noam Zaks (1/5/2025 3:28 PM IDT)
  • *Dieter Beckerle (1/5/2025 5:03 PM IDT)
  • *Klaus Nagel (1/5/2025 7:06 PM IDT)
  • Sam Fischer (1/5/2025 7:12 PM IDT)
  • Loukas Sidiropoulos (1/5/2025 9:10 PM IDT)
  • *Peter Moser (1/5/2025 11:08 PM IDT)
  • *Kang Jin Cho (2/5/2025 4:59 AM IDT)
  • Alex Fleischer (2/5/2025 9:04 AM IDT)
  • *Dan Dima (2/5/2025 10:38 AM IDT)
  • *Daniel Bitin (2/5/2025 12:27 PM IDT)
  • *Piyush Agrawal (2/5/2025 12:44 PM IDT)
  • *Vladimir Volevich (2/5/2025 2:35 PM IDT)
  • Fabio Michele Negroni (2/5/2025 4:31 PM IDT)
  • Kennedy (2/5/2025 5:59 PM IDT)
  • *Gary M. Gerken (3/5/2025 3:22 AM IDT)
  • *King Pig (3/5/2025 3:54 AM IDT)
  • *Mithil Ramteke (3/5/2025 3:51 PM IDT)
  • Terry Lee (3/5/2025 6:48 PM IDT)
  • *Minseung Kim (3/5/2025 8:44 PM IDT)
  • *Balakrishnan V (3/5/2025 9:04 PM IDT)
  • John Tromp (3/5/2025 11:24 PM IDT)
  • *Alexander Daryin (4/5/2025 3:48 AM IDT)
  • *Li Li (4/5/2025 9:01 AM IDT)
  • *Daniel Chong Jyh Tar (4/5/2025 11:24 AM IDT)
  • Amos Guler (4/5/2025 11:35 AM IDT)
  • *Sherman Yuen (4/5/2025 12:41 PM IDT)
  • *Paul Lupascu (4/5/2025 2:26 PM IDT)
  • *Arun Srinivaas (4/5/2025 3:30 PM IDT)
  • *Asaf Zimmerman (4/5/2025 4:40 PM IDT)
  • *Arthur Vause (4/5/2025 6:12 PM IDT)
  • *Hugo Pfoertner (4/5/2025 8:29 PM IDT)
  • *Martin Thorne (4/5/2025 9:18 PM IDT)
  • *Prashant Wankhede (5/5/2025 12:26 AM IDT)
  • *Mark Mammel (5/5/2025 12:39 AM IDT)
  • *Camden Chappelle (5/5/2025 4:46 AM IDT)
  • *Karl-Heinz Hofmann (5/5/2025 1:58 PM IDT)
  • *Sujal Singh (5/5/2025 3:00 PM IDT)
  • *Daniel Rolfe (6/5/2025 12:16 AM IDT)
  • *Stéphane Higueret (6/5/2025 7:06 AM IDT)
  • Mathias Schenker (6/5/2025 12:53 PM IDT)
  • *Franciraldo Cavalcante (6/5/2025 4:26 PM IDT)
  • *Sri Mallikarjun J (6/5/2025 7:38 PM IDT)
  • *Evan Schor (7/5/2025 12:02 AM IDT)
  • *Tim Walters (7/5/2025 1:43 AM IDT)
  • Kipp Johnson (7/5/2025 5:14 PM IDT)
  • *Ankit Chakraborty (8/5/2025 9:14 PM IDT)
  • *Serge Batalov (9/5/2025 8:23 AM IDT)
  • *Matt McNenly (10/5/2025 7:57 AM IDT)
  • *Davide Colì (10/5/2025 5:30 PM IDT)
  • Eran Vered (10/5/2025 9:22 PM IDT)
  • *Nyles Heise (10/5/2025 10:13 PM IDT)
  • Sachal Mahajan (11/5/2025 8:35 AM IDT)
  • *David Greer (11/5/2025 11:33 AM IDT)
  • Michael Liepelt (11/5/2025 12:39 PM IDT)
  • *Guangxi Liu (12/5/2025 9:02 AM IDT)
  • *Tamir Ganor & Shouky Dan (12/5/2025 9:05 AM IDT)
  • John Bortins & Phil Benamy (12/5/2025 9:04 PM IDT)
  • Paul Revenant (12/5/2025 10:39 PM IDT)
  • *Jordan Payette (12/5/2025 10:44 PM IDT)
  • *Nikhil Mishra (13/5/2025 9:54 PM IDT)
  • *Andrew Gauld (14/5/2025 11:32 PM IDT)
  • *Chris Shannon (16/5/2025 8:39 AM IDT)
  • *Harald Bögeholz (16/5/2025 6:51 PM IDT)
  • *Dominik Reichl (17/5/2025 8:46 PM IDT)
  • Hakan Summakoğlu (17/5/2025 10:28 PM IDT)
  • *Sean Kuwamoto (18/5/2025 9:54 PM IDT)
  • *Sho Kuwamoto (19/5/2025 12:23 AM IDT)
  • *Marco Bellocchi (19/5/2025 12:25 AM IDT)
  • Resnina (Kulshaeva) Tathyana (19/5/2025 1:16 AM IDT)
  • *Latchezar Christov (19/5/2025 8:11 PM IDT)
  • *Christoph Baumgarten (19/5/2025 10:26 PM IDT)
  • Thomas Egense (19/5/2025 11:48 PM IDT)
  • Rajnish Kumar (20/5/2025 4:23 PM IDT)
  • *Kevin Bauer (21/5/2025 2:42 AM IDT)
  • *Zach Liu (21/5/2025 6:48 AM IDT)
  • Marshall Munsch-Hayhurst (22/5/2025 2:59 AM IDT)
  • Todd Will (22/5/2025 7:54 PM IDT)
  • Alexey Zyl (23/5/2025 9:50 AM IDT)
  • *Motty Porat (23/5/2025 7:52 PM IDT)
  • qq (24/5/2025 9:34 AM IDT)
  • *Aayaam Panigrahi (25/5/2025 7:40 AM IDT)
  • *Albert Stadler (26/5/2025 3:00 PM IDT)
  • *Jim Clare (27/5/2025 2:57 AM IDT)
  • Michael Vahle (28/5/2025 5:17 PM IDT)
  • *Maths ForFun2 (29/5/2025 3:02 AM IDT)
  • Stefan Wirth (29/5/2025 2:59 PM IDT)
  • *Nischal Agrawal (31/5/2025 5:34 PM IDT)
  • Zoltan Haindrich (1/6/2025 8:11 AM IDT)
  • *Dwij Mehta (1/6/2025 11:34 AM IDT)
  • Ranjit Eswaran (1/6/2025 9:03 PM IDT)
  • David F.H. Dunkley (2/6/2025 12:27 AM IDT)
  • Radu-Alexandru Todor (3/6/2025 2:05 AM IDT)
  • *Evan Semet (3/6/2025 9:35 AM IDT)
  • *Jérome Langlois (3/6/2025 9:09 PM IDT)
  • Robin Guilliou (4/6/2025 5:37 PM IDT)

Related posts