A question about modulus for polynomials

Question

The other day my friend was asked to find $A$ and $B$ in the equation $$(x^3+2x+1)^{17} \equiv Ax+B \pmod {x^2+1}$$ A method was proposed by our teacher to use complex numbers and especially to let $x=i$ where $i$ is the imaginary unit. We obtain from that substitution $$(i+1)^{17} \equiv Ai+B \pmod {0}$$ which if we have understood it correctly is valid if we define $a \equiv b \pmod n$ to be $a=b+dn$. Running through with this definition we have $$\begin{align*} (i+1)^{17} &=\left(\sqrt{2}\left(\cos\left(\frac{\pi}{4}\right)+\sin\left(\frac{\pi}{4}\right)\right)\right)^{17}\\ &=\sqrt{2}^{17}\left(\cos\left(\frac{17\pi}{4}\right)+\sin\left(\frac{17\pi}{4}\right)\right) \tag{De Moivre}\\ &=256\left(\sqrt{2}\left(\cos\left(\frac{\pi}{4}\right)+\sin\left(\frac{\pi}{4}\right)\right)\right)\\ &=256\left(1+i\right) \\ &=256+256i\end{align*} $$ which gives the correct coefficient values for $A$ and $B$. Our questions are

1. Why is this substitution valid to begin with?
2. It seems here that the special case ($x=i$) implies the general case ($x$), why is that valid?

Answer 1

Here I think it's easier to see what's going on if we forgo the modular arithmetic and look at simple factoring and remainder. We have $$ (x^3+2x+1)^{17}=(x^2+1)Q(x)+Ax+B $$ for some polynomial $Q$. Which polynomial? We don't really care. The main point is that the left-hand side and the right-hand side are the same polynomial.

And since they are the same, they must give the same value when we evaluate them at $x=i$. So we insert $x=i$ and get $$ (i^3+2i+1)^{17}=(i^2+1)Q(i)+Ai+B\\ (i+1)^{17}=0\cdot Q(i)+Ai+B $$ Knowing that $A,B$ are real means we can find them directly from this, as $Q$ disappears.

Answer 2

1. It comes from the exponential form of complex numbers: $1+i$ has modulus $\sqrt 2$ and argument $\frac\pi 4$, so it writes as $$1+i=\sqrt2\,\mathrm e^{\tfrac\pi 4},\quad\text{and similarly}\quad 1-+i=\sqrt2\,\mathrm e^{-\tfrac\pi 4} $$ The substitution is valid because of the meaning of the congruence: \begin{align}&(x^3+2x+1)^{17} \equiv Ax+B\enspace (\!\bmod {x^2+1)}\\ &\qquad\qquad\iff \exists q(x):\;(x^3+2x+1)^{17} =(x^2+1)q(x)+Ax+B , \end{align} so when you set $x=\pm i$, the first term in the r.h.s. cancels.
2. Setting $x=i$ yields an equation for $A$ and $B$, that's all.

Answer 3

{To hot list readers: you can understand a good part of this answer knowing only modular arithmetic. Please feel welcome to ask questions and it will be my pleasure to elaborate.]

First let's do it using only modular arithmetic (congruences).

$\!\!\!\begin{align}\bmod x^{\large 2}\!+\!1\!:\,\ f^{{\large 2}N}\! = (\color{#c00}{x^{\large 3}}\!+\!2x\!+\!1)^{{\large 2}N}\!&\,\equiv (x\!+\!1)^{{\large 2}N}\ \ \ \ \ \ \ \ \, {\rm by}\ \ \ x^{\large 2}\equiv -1\,\Rightarrow\, \color{#c00}{x^{\large 3}\equiv -x}\\[.4em] &\equiv\, (2x)^N\ \ \ \ \ \ \ \ \ \ \ \ \ \,{\rm by}\ \ \ (x\!+\!1)^{\large 2}\equiv (x^{\large 2}\!+1)+2x\equiv 2x\\[.4em] &\equiv\, \bbox[5px,border:1px solid #c00]{2^N x^{N\bmod\large\color{#0a0}4}}\ \ {\rm by}\,\ \ x^{\large 2}\equiv -1\,\Rightarrow\,x^{\large\color{#0a0} 4}\equiv 1 \end{align}$

which yields: $\ f^{\large 17}\!\equiv (x\!+\!1)^{\large 16}(x\!+\!1)\,\equiv\, 2^{\large 8}\, x^{{\large 8}\bmod\large 4}\, (x\!+\!1)\, \equiv\, 256(x\!+\!1)$

Calculating in $\, C := \Bbb R[x] \pmod {\!x^2\!+\!1}\,$ amounts to calculating modulo a generic root of $\,x^2\!+\!1,\,$ i.e. we reason using only the ring axioms in $\,\Bbb R[x]\,$ plus the additional hypothesis that $\,x^2 = -1.\,$ But $C \cong \Bbb R[x]/(x^2+1) \equiv \Bbb R[i]\cong \Bbb C\,$ because $\,x^2\!+\!1\,$ is the minimal polynomial of $\,i\,$ over $\,\Bbb R.\,$ This means that we can replace $\,x\,$ by $\,i\,$ in the above calculations. This will be clarified when one studies polynomial and quotient rings in abstract algebra - esp. their universal properties. These imply that the above calculations hold true in every ring with an element $\,x\,$ such that $\,x^2 \equiv -1.\,$ For example in $\,\Bbb Z/5 = $ integers $\bmod 5\,$ we have $\,2^2 \equiv -1$ therefore by specializing the above for $\,x\equiv 2\,$ we obtain the congruences below $\color{#90f}{\bmod 5},\,$ and similarly for the following congruences when $\,x\equiv 3,4,\ldots\, 10$.

$$\begin{align} &\!\!\!\bbox[6px,border:1px solid #c00]{\bmod x^2\!+\!1\!: f(x)^{17}\!\!\equiv (x\!+\!1)^{17}\!\!\equiv\! 256(x\!+\!1) }\\[.3em] x=2\!:\ &\color{#90f}{\bmod\,\ \ \ 5}\!:\ \ \ \ \ 13^{17}\ \equiv\ 3^{17}\equiv 256(3)\ \equiv\ 3\\ x=3\!:\ &\bmod\,\ 10\!:\ \ \ \ \ 34^{17}\ \equiv\ 4^{17}\equiv 256(4)\ \equiv\ 4\\ x=4\!:\ &\bmod\,\ 17\!:\ \ \ \ \ 73^{17}\ \equiv\ 5^{17}\equiv 256(5)\ \equiv\ 5\\ &\bmod\,\ 26\!:\ \ \ 136^{17}\ \equiv\ 6^{17}\equiv 256(6)\ \equiv\ 2\\ &\bmod\,\ 37\!:\ \ \ 229^{17}\ \equiv\ 7^{17}\equiv 256(7)\ \equiv\ 16\\ &\bmod\,\ 50\!:\ \ \ 358^{17}\ \equiv\ 8^{17}\equiv 256(8)\ \equiv\ 48\\ &\bmod\,\ 65\!:\ \ \ 529^{17}\ \equiv\ 9^{17}\equiv 256(9)\ \equiv\ 29\\ &\bmod\,\ 82\!:\ \ \ 748^{17}\equiv 10^{17}\equiv 256(10)\equiv 18\\ x=10\!:\ &\bmod 101\!:\ 1021^{17}\equiv 11^{17}\equiv 256(11)\equiv 89\\ \end{align}\qquad\qquad\qquad\ \ \ \ \ \ \ $$

Our calculations persist to hold true in all these rings because they used only ring laws and the hypothesis that $\,x^2 \equiv -1.\ $ You may have encountered simpler linear examples in terms of fractions (roots of linear polynomials), e.g. the equality $\ 1/ 6 = 1/2 - 1/3\ $ holds true in any rings where $2$ & $3$ are invertible, e.g. $\bmod 5\,$ it is $\,1 \equiv 3 - 2,\,$ and $\bmod 11\,$ it is $\,2\equiv 6- 4.\,$ This can also be used in exponents to get a sixth root from a square root and cube root: $\,a ^{1/6}\equiv a^{1/2}/a^{1/3}$ and again it also works when the exponents are modular, e.g. see here. This all works because we used only rings laws and the added hypotheses $\,2x\equiv 1,\ 3y\equiv 1,\,$ so our calculations will persist to hold true in any rings where these equations have roots $\,x,y.\,$ This is a special case of the universal properties of rings of fractions (and localizations).

These are a couple simple examples of the power afforded by the algebraic abstractions at the foundation of "abstract algebra".

Such modular arithmetic calculations in quadratic extensions often proves convenient, e.g. see the quadratic extension of Hermite's cover-up method for partial fraction expansion.