# Modular arithmetic polynomial question

Is it possible to find all polynomials of the form $an^2 + bn +c$ where a,b, and c are integers and such that

$$a+b+c \equiv 31 \pmod{54}$$ $$4a+2b+c \equiv 3 \pmod{54}$$ $$9a+3b+c \equiv 11 \pmod{54}$$

-

That you're making them coefficients of a polynomial is irrelevant: the problem is "solve this linear system of three equations in three variables".

That you're solving systems of equations modulo 54 rather than systems of equations of real numbers doesn't change things much: the only real difference is how to compute the inverse of a number, and that some non-zero numbers can fail to be invertible.

Solving the first equation gives

$$c \equiv 31 - a - b$$

plugging into the other equations gives

$$3a + b \equiv -28 \equiv 26$$ $$8a + 2b \equiv -20 \equiv 34$$

Solving the first of these gives

$$b \equiv 26 - 3a$$

plugging into the other equation gives

$$2a \equiv -18 \equiv 36$$

Solving this is a little trickier: the solution space to

$$gux \equiv gv \pmod{gw}$$

is the same as the solution space to

$$ux \equiv v \pmod w$$

(Note if the equation was $gux \equiv v \pmod{gw}$ where $v$ is not divisible by $g$, then there would be no solutions for $x$)

So to solve

$$2a \equiv 36 \pmod{54}$$

you factor out the 2

$$a \equiv 18 \pmod{27}$$ $$a \equiv 18, 45 \pmod{54}$$

Now backsolving gives

$$a \equiv 18 \pmod{54} \qquad b \equiv 26 \pmod{54} \qquad c \equiv 41 \pmod{54}$$ $$a \equiv 45 \pmod{54} \qquad b \equiv 53 \pmod{54} \qquad c \equiv 41 \pmod{54}$$

Of course, I could have used Gaussian elimination and its variants instead. Or I could have solved for $a$ first, or any other variation.

The big thing I didn't demonstrate is the Chinese remainder theorem approach. $54 = 2 \cdot 3^3$; Often, it's easier to solve a problem modulo $2$ then solve the problem modulo $3^3$, then use the Chinese remainder theorem to combine the solutions to modulo $54$ than it is to solve it directly.

-
Thanks for the well detailed answer. – A. Napster Feb 11 '13 at 17:52

So you want to solve the system of linear equations $$\left(\begin{matrix}1 & 1 & 1\\ 4 & 2 & 1\\ 9 & 3 & 1\end{matrix}\right) \left(\begin{matrix} a\\ b\\ c \end{matrix}\right) = \left(\begin{matrix}31\\ 3\\ 11 \end{matrix}\right)$$ over the ring $\mathbb Z/54\mathbb Z$. By the chinese remainder theorem, it is enough to solve this over $\mathbb Z/ 2\mathbb Z$ and $\mathbb Z/27 \mathbb Z$ separately. Using the Gaussian algorithm over $\mathbb Z/2\mathbb Z$, we get $$\left(\begin{array}{ccc|c} 1 & 1 & 1 & 1\\ 0 & 0 & 1 & 1\\ 1 & 1 & 1 & 1\end{array}\right) \leadsto \left(\begin{array}{ccc|c} 1 & 1 & 0 & 0\\ 0 & 0 & 1 & 1 \end{array}\right),$$ whose solutions are $(0,0,1)$ and $(1,1,1)$.

Over $\mathbb Z/27 \mathbb Z$ the matrix is invertible (its determinant is $-2$ which is a unit modulo $27$), so we get a unique solution, namely $(18,26,14)$ by the Gaussian algorithm or by computing the inverse of the matrix.

Putting the solutions together with the Chinese Remainder Theorem gives $$(a,b,c) \equiv (18,26,41) \mod 54$$ (corresponding to $(0,0,1) \bmod 2$) and $$(a,b,c) \equiv (45,53,41) \mod 54$$ (corresponding to $(1,1,1) \bmod 2$).

-

The fact we're searching for a polynomial allows us to use polynomial interpolation methods. We seek a polynomial such that

$$f(1) \equiv 31 \qquad f(2) \equiv 3 \qquad f(3) \equiv 11$$

One trick is to split things apart: first, we find a polynomial

$$g_1(x) = (x-2)(x-3)$$

which satisfies

$$g_1(1) = 2 \qquad g_1(2) = 0 \qquad g_1(3) = 0$$

similarly, $g_2(x) = (x-1)(x-3)$ and $g_3(x) = (x-1)(x-2)$ satisfy

$$g_2(1) = 0 \qquad g_2(2) = -1 \qquad g_2(3) = 0$$ $$g_3(1) = 0 \qquad g_3(2) = 0 \qquad g_3(3) = 2$$

Now, it's easy to see how to combine the values!

\begin{align} f(x) &= \frac{31}{2} g_1(x) - 3 g_2(x) + \frac{11}{2} g_3(x) \\&= 18 x^2 - 82x + 95 \end{align}

We lucked out, we got the coefficients to actually be integers, so this polynomial definitely works.

There is a "problem" here in that I'm dividing by $2$, but that's not really allowed modulo $54$. As you can see, we missed the other set of solutions where the leading coefficient is $45$ modulo $54$.

I'm pretty sure there's a way to account for this problem, but I don't know how to do it systematically. It probably involves the Chinese remainder theorem, and treating the modulo $2$ case with a different method (which is easy because $2$ is small). I believe there are other ways this approach can go badly as well.

-

We seek a quadratic $\rm\,f(x)\,$ with $\rm\,f(1) \equiv 31,\ f(2) \equiv 3,\ f(3)\equiv 11\:\ (mod\ 54).$ Interpolating gives one solution $\rm\: f_1(x) = 3 + (x\!-\!2)(8 + 18(x\!-\!3)) \equiv \color{#C00}{18 x^2 + 26 x - 13}.\:$ If $\rm\,f_2(x)\,$ is another solution then $\rm\,h = f_1-f_2\,$ has degree $\le 2$ but has three distinct roots $1,2,3$ mod $54$. These remain distinct roots mod $3,\,$ thus $\rm\,h \equiv 0\:\ (mod\ 3),\:$ being a polynomial over a field with more roots than its degree.

So $\rm\,h = 3h_1.\,$ Similarly we deduce $\rm\, h_1\! = 3h_2,\,$ then $\rm\,h_2\! = 3g,\:$ so $\rm\:f = 27g.\,$ So $\rm\, mod\ 2\!:\,$ $\rm\,f,\,$ so $\rm\,g,\,$ has roots $\rm\,0,1,\,$ hence $\rm\ g\equiv x(x\!-\!1).\,$ Hence $\rm\ f = 27g = 27(x(x\!-\!1)+2g')\equiv 27(x^2\!-x)\:\ (mod\ 54).\,$ Therefore the only other solution is $\rm\: f_2 = f_1\!+h = f_1\! + 27x^2\!-27x \equiv \color{#C00}{-9x^2\!-x-13}\:\ (mod\ 54).$

-