11
$\begingroup$

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?
$\endgroup$
  • 1
    $\begingroup$ The use of complex numbers can be explained the following way: $\mathbb{C}$ is $\mathbb{R}[i]$, i.e $\mathbb{R}$ along with a solution of $X^2 + 1$. The quotient $R[X]/(X^2 + 1)$ is actually the same thing, it is $\mathbb{R}$, in which you adjoin some element $\bar{X}$ (the class of $X$ in the quotient) that satisfy $X^2 + 1 = 0$. So you can freely think of this quotient as $\mathbb{C}$ and substitute $X$ to $i$. $\endgroup$ – Robin Carlier Oct 30 at 14:14
  • $\begingroup$ seems easier to show it's congruent to $(x+1)^{17}$ and work from that honestly. edit realized you did that, polynomial remainder theorem to the rescue. $\endgroup$ – Roddy MacPhee Oct 30 at 19:11
  • 1
    $\begingroup$ I'm gonna include exercises like this to my algebra course this coming Spring. +1 to all posters. $\endgroup$ – Jyrki Lahtonen Oct 30 at 19:27
  • 1
    $\begingroup$ I added some more examples to my answer that may help you better understand the universal algebraic principles at the heart of the matter. Again, questions are always welcome. $\endgroup$ – Bill Dubuque Oct 31 at 0:22
19
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

{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.

$\endgroup$
4
$\begingroup$
  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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.