Most efficient solution to find polynomial congruence for 0 mod p

Question

I was given the polynomial $$f(x) = x^4 + 2x^3 + 3x^2 + x + 1$$ and told to find $$f(x) \mod 17 = 0 $$ I found the solution to be $$x = 8 + 17n$$ However, I arrived at this solution by computing all of the residues of f(x) mod 17 and then finding where the zero occurred. I was told by the person who gave me the problem that there's a more efficient solution that doesn't involve making a list. I'm quite new to number theory, so I don't know where to look to ask the question in a more advanced way, need guidance to be able to. Thank you kindly if you can.

TL;DR: Looking for a more number theoretic way to solve for x than computing f(x) from 1 to 17

Answer 1

If $\,\color{#c00}{x^4\!+\!1} = 0\,$ then $\,f = 2x^3\!+\!3x\!+\!x = (2x\!+\!1)(x\!+\!1)x\,$ with roots $\,0,-1,-1/2,\,$ and $-1/2\equiv 8\,$ is a root of $\,x^4\!+\!1\,$ so also of $\,f.$

Key Idea behind the method. By Fermat, $\!\bmod 17,\,$ all $\,a\not\equiv 0\,$ are roots of $$\,x^{16}\!-\!1 = (x^8\!-\!1)(x^8\!+\!1) = (\color{#c00}{x^4\!+\!1})(x^4\!-\!1)(x^4\!+\!4)(x^4\!-\!4)\qquad$$ So if $f$ has a root $\not\equiv 0$ then we we can find it by taking its gcd with these quartics. We tried $\,x^4\!+\!1\,$ first since that kills the constant term, reducing to checking a quadratic, and that did the trick (we optimized out of the Euclidean algorithm by noting an obvious factor $\,x\!+\!1\,$ of the quadratic).

The idea generalizes to efficient irreducibility tests and factorization algorithms (e.g. see Jyrki's introduction here to Cantor-Zassenhaus factorization), but these are usually not practical for manual computation (except for extremely small or special problems).

Answer 2

The fastest solution is probably by noticing $f(x) = (x^2 + x + 1)^2 - x$, after which you can apply Euler's Criterion to bound the order of $x \pmod {17}$ and then solve in four cases (either the order is 8, 4, 2, or 1). This solution is pretty similar to the solution given by Bill Dubuque. Here's another interesting solution:

Since $f$ is a polynomial, we can apply finite differences to get a recurrence. To make things nicer, let $a_n = f(n)$. The recurrence is: $$a_n = 5a_{n-1} - 10a_{n-2} + 10a_{n-3} - 5a_{n-4} + a_{n-5}$$ This is solely based on the fact that $f$ is a fourth degree polynomial. Now we can quickly calculate $f(0)$, $f(1)$, $f(2)$, $f(3)$, $f(4)$: $$f(0) = 1 \mod 17$$ $$f(1) = 1 + 2 + 3 + 1 + 1 = 8 \mod 17$$ $$f(2) = 16 + 16 + 12 + 2 + 1 = 47 = -4 \mod 17$$ $$f(3) = 81 + 54 + 27 + 3 + 1 = -4 + 3 - 7 + 3 + 1 = -4 \mod 17$$ $$f(4) = 256 + 128 + 48 + 4 + 1 = 1 -8 -3 + 4 + 1= -5 \mod 17$$

Now we can simply calculate the values up to 17 in a table using the recurrence. This isn't actually tedious if you stay organized (make a table with columns of $n$, $a_n$, $5a_n$, and $10a_n$) after which you can skip many multiplications because you've done them before and the only other operation needed is addition.

After this, you will see that 8 is the only value that yields zero mod 17.