Question: A cartographer uses a polynomial $ p(x) $ of degree 3 such that $ p(0) = 2 $, $ p(1) = 5 $, $ p(2) = 12 $, and $ p(3) = 31 $. Find the remainder when $ p(x) $ is divided by $ x^4 - 1 $.

["Title: Finding the Remainder of a Degree-3 Polynomial Modulo $ x^4 - 1 $", "When working with a cubic polynomial $ p(x) $ that satisfies specific values—$ p(0) = 2 $, $ p(1) = 5 $, $ p(2) = 12 $, and $ p(3) = 31 $—we are asked to find the remainder when $ p(x) $ is divided by $ x^4 - 1 $. This problem blends polynomial interpolation, modular arithmetic, and algebraic structure.", "---", "### Step 1: Understanding the Division Process", "When dividing a polynomial $ p(x) $ by $ x^4 - 1 $, the degree of the remainder is less than 4. So, we can express:", "$$\np(x) = (x^4 - 1)q(x) + r(x)\n$$", "where $ r(x) $ is a polynomial of degree at most 3, and can be written in the form:", "$$\nr(x) = ax^3 + bx^2 + cx + d\n$$", "Our goal is to find constants $ a, b, c, d $ such that $ r(x) $ matches $ p(x) $ at cross terms or infinitely many points—specifically, where $ x^4 - 1 = 0 $, i.e., at the 4th roots of unity: $ x = 1, -1, i, -i $. However, since $ p(x) $ is degree 3 and uniquely determined by four points, $ p(x) $ is exactly the unique cubic interpolating polynomial through $ (0,2), (1,5), (2,12), (3,31) $. Hence, the remainder $ r(x) $ must equal $ p(x) $ everywhere, provided $ p(x) $ is of degree less than 4—which it is.", "Key Insight: Since $ \deg(p) = 3 < 4 = \deg(x^4 - 1) $, the division yields no quotient and the remainder is $ p(x) $ itself—but only if $ p(x) $ is degree less than 4, which it is. So, in principle, the remainder is $ p(x) $. However, the question asks for the remainder when $ p(x) $ is divided by $ x^4 - 1 $, and since $ x^4 \equiv 1 \mod{(x^4 - 1)} $, we can reduce powers of $ x $ modulo $ x^4 - 1 $ using $ x^4 = 1 $, $ x^5 = x $, etc.—but this only helps if we know $ p(x) $.", "But here’s the catch: we don’t know the full expression of $ p(x) $, only four values. However, because $ p(x) $ is a degree-3 polynomial, it is uniquely determined, and so is its remainder modulo $ x^4 - 1 $. Since the remainder must also be a cubic polynomial, and $ x^4 - 1 $ introduces periodicity, the remainder $ r(x) $ is just the interpolating cubic through the four given points.", "Thus, we can compute $ p(x) $ explicitly, then confirm it is degree 3 (which it is), and since its degree is less than 4, it is the remainder modulo $ x^4 - 1 $. So we proceed to find the cubic polynomial $ p(x) $ satisfying the conditions.", "---", "### Step 2: Constructing the Interpolating Polynomial", "We use Lagrange interpolation:", "$$\np(x) = 2 \cdot \frac{(x-1)(x-2)(x-3)}{(0-1)(0-2)(0-3)} + 5 \cdot \frac{(x-0)(x-2)(x-3)}{(1-0)(1-2)(1-3)} + 12 \cdot \frac{(x-0)(x-1)(x-3)}{(2-0)(2-1)(2-3)} + 31 \cdot \frac{(x-0)(x-1)(x-2)}{(3-0)(3-1)(3-2)}\n$$", "We compute each term separately at $ x = 0,1,2,3 $ to ensure correctness, but since Lagrange interpolation guarantees correctness at those points and the polynomial is degree ≤ 3, this defines the unique cubic.", "But to compute the remainder modulo $ x^4 - 1 $, we evaluate $ p(x) $ at the 4th roots of unity to extract coefficients via discrete Fourier methods—or better, evaluate $ p(x) $ at $ x = 1, -1, i, -i $, since $ x^4 - 1 = (x-1)(x+1)(x-i)(x+i) $, and use the fact that the remainder is determined by values at these points (Lagrange interpolation over complex roots).", "We already know:\n- $ p(1) = 5 $\n- $ p(2) = 12 $\n- $ p(3) = 31 $", "But we lack $ p(-1) $ and $ p(i) $. However, since $ p(x) $ is a cubic polynomial, and we have four data points, we can construct $ p(x) $ explicitly.", "---", "### Step 3: Solving the System of Equations", "Let $ p(x) = ax^3 + bx^2 + cx + d $", "Using:\n- $ p(0) = d = 2 $\n- $ p(1) = a + b + c + d = 5 $\n- $ p(2) = 8a + 4b + 2c + d = 12 $\n- $ p(3) = 27a + 9b + 3c + d = 31 $", "Substitute $ d = 2 $:", "1. $ a + b + c = 3 $\n2. $ 8a + 4b + 2c = 10 $\n3. $ 27a + 9b + 3c = 29 $", "Simplify equations:", "From (1): $ a + b + c = 3 $ → multiply by 2:\n$ 2a + 2b + 2c = 6 $\nSubtract from (2):\n$ (8a + 4b + 2c) - (2a + 2b + 2c) = 10 - 6 $ → $ 6a + 2b = 4 $ → $ 3a + b = 2 $ → (A)", "From (3): $ 27a + 9b + 3c = 29 $\nMultiply (1) by 3: $ 3a + 3b + 3c = 9 $\nSubtract:\n$ (27a + 9b + 3c) - (3a + 3b + 3c) = 29 - 9 $ → $ 24a + 6b = 20 $ → $ 12a + 3b = 10 $ → (B)", "Now solve (A) and (B):", "From (A): $ b = 2 - 3a $\nPlug into (B):\n$ 12a + 3(2 - 3a) = 10 $ → $ 12a + 6 - 9a = 10 $ → $ 3a = 4 $ → $ a = \frac{4}{3} $", "Then $ b = 2 - 3 \cdot \frac{4}{3} = 2 - 4 = -2 $\nFrom (1): $ \frac{4}{3} - 2 + c = 3 $ → $ c = 3 - \frac{4}{3} + 2 = 5 - \frac{4}{3} = \frac{11}{3} $", "So:\n$$\np(x) = \frac{4}{3}x^3 - 2x^2 + \frac{11}{3}x + 2\n$$", "Check degree: cubic → degree < 4 → remainder modulo $ x^4 - 1 $ is $ p(x) $", "But the problem says: “Find the remainder when $ p(x) $ is divided by $ x^4 - 1 $.” Since $ p(x) $ is degree 3 < 4, the remainder is simply $ p(x) $.", "But perhaps the question intends to test modular reduction using symmetry or the structure of $ x^4 - 1 $? However, no—since $ \deg(p) < 4 $, the remainder is $ p(x) $.", "But let’s double-check: could $ x^4 \equiv 1 $, so $ x^k \equiv x^{k \mod 4} $? That applies when dividing by $ x^4 - 1 $, but only if we are reducing expressions. However, here $ p(x) $ is already expressed in terms of powers ≤ 3, so no reduction is needed.", "Therefore, the remainder is $ p(x) $. But the problem likely expects us to compute it explicitly, or verify via roots.", "Alternatively, interpret the remainder not as a polynomial, but the essentially unique representative of $ p(x) \mod (x^4 - 1) $, which, since $ \deg(p) < 4 $, is $ p(x) $.", "Hence, the remainder is:", "$$\np(x) = \frac{4}{3}x^3 - 2x^2 + \frac{11}{3}x + 2\n$$", "But let’s confirm $ p(3) $:", "$$\np(3) = \frac{4}{3}(27) - 2(9) + \frac{11}{3}(3) + 2 = 36 - 18 + 11 + 2 = 31 \quad \ ext{✓}\n$$", "$ p(2) = \frac{4}{3}(8) - 2(4) + \frac{11}{3}(2) + 2 = \frac{32}{3} - 8 + \frac{22}{3} + 2 = \frac{54}{3} - 6 = 18 - 6 = 12 $ ✓\n$ p(1) = \frac{4}{3} - 2 + \frac{11}{3} + 2 = \frac{15}{3} + 0 = 5 $ ✓\n$ p(0) = 2 $ ✓", "All match.", "---", "### Step 4: Final Answer — The Remainder", "As $ \deg(p) = 3 < 4 = \deg(x^4 - 1) $, the remainder upon division is $ p(x) $ itself. So the remainder is:", "$$\n\boxed{\frac{4}{3}x^3 - 2x^2 + \frac{11}{3}x + 2}\n$$", "However, in many olympiad contexts, such answers are expressed as polynomials. But to match the format and clarity, we present it neatly.", "But wait—could there be a further algebraic interpretation? For example, if we were to evaluate $ p(x) $ at $ x = 1, -1, i"]