# Calculating mod polynomials, e.g. $\,a^2 = a+3\,\Rightarrow\, a^3 = \, \ldots\,$ [closed]

This is a Belgian math olympiad question. https://www.vwo.be/vwo/files/2r2017.pdf

Sorry, the picture is in Dutch I will translate it:

If $a^2 -a -3=0$ then $a^3$ is equal to:

(A) $a+1$ (B) $2a+1$ (C) $4a+1$ (D) $4a+3$ (E) $5a+3$

I've tried $a^2 = a + 3$ then multiply by $a$. Doesn't work.

I've tried finding the roots in the standard manners ($x_1 + x_2 = -b/a$ and $x_1x_2 = c/a$ and also the quadratic formula) but of course that doesn't work as they ask it in terms of $a$ and I can't figure it out from the roots directly, so I will be trying your complete algebra approach thanks.

• I've tried $a^2 = a + 3$ then multiply by a. Doesn't work. I've tried finding the roots in the standard manners (x1 + x2 = -b/a and x1*x2 = c/a and also the quadratic formula) but of course that doesn't work as they ask it in terms of a and i can't figure it out from the roots directly, so I will be trying your complete algebra approach thanks. Commented Aug 29, 2017 at 15:55
• No, you don't need the roots. if you multiply by $a$ you get $a^3=a^2+3a$. Now, can you rewrite $a^2$?
– lulu
Commented Aug 29, 2017 at 15:56
• Oh, these things always look easy after you see them. They are often hard to spot though.
– lulu
Commented Aug 29, 2017 at 16:00
• I've downvoted and voted to close this question because it looks very much like a homework question and is a PSQ. In the future, please include more context such as what's holding you back. Commented Aug 29, 2017 at 20:56
• Please follow the guidelines outlined by How to ask a good question? and How to ask a homework question?. Low quality questions run the risk of being closed and deleted, and repeated closures and deletions may trigger a question ban. Thank you! Commented Aug 29, 2017 at 20:56

\begin{align}0&=a^2-a-3\\a^2&=a+3\qquad\qquad~~~(1)\\a^3&=a^2+3a\\a^3&=(a+3)+3a\qquad\text{by (1)}\\a^3&=4a+3\end{align}

Since the general method may not be clear from other answers it may help to describe it explicitly. Given $$\:\!a\:\!$$ is a root of a polynomial $$\,g(x)\ne 0,\,$$ i.e. $$\,\color{#c00}{g(a)=0},\,$$ suppose we wish to compute $$f(a)\,$$ for some polynomial $$\,f(x).\,$$ By the Polynomial Division Algorithm we can divide $$\,f(x)\,$$ by $$\,g(x)$$

\begin{align} f(x) &=\, r(x)\, +\, q(x)\, g(x),\ \ {\rm with}\ \ \deg r < \deg g\\[.2em] \smash{\overset{\large x\ =\ a}\Longrightarrow}\ \ f(a) &=\, r(a)\, +\, q(a)\, \color{#c00}{g(a)}\\[.2em] &=\, r(a)\ \ \ \ \ {\rm by}\,\ \ \ \ \color{#c00}{g(a) = 0} \end{align}

Since we need only the remainder $$\,r(a)\,$$ it is more efficient to use arithmetic modulo $$\,g(x),\,$$ vs. the full-blown division algorithm, e.g. $$\,g(x) = x^{\large 2}-x-3\,$$ in OP  so

\begin{align} \bmod{\,x^{\large 2}\!-\!x\!-\!3}\!:\,\ \color{#c00}{x^{\large 2}}&\equiv \,\color{#0a0}{x\,+\,3}\\[.2em] \overset{\times\ x}\Longrightarrow\ \ x^{\large 3}&\equiv \color{#c00}{x^{\large 2}}+3x\,\ \ {\rm by}\,\ \ x * {\rm prior}\\[.2em] &\equiv \color{#0a0}{x+3}+3x\\[.2em] &\equiv 4x+3\\ \overset{\times\ x}\Longrightarrow\ \ x^{\large 4}&\equiv\ \ldots\ \ \text{as above}\\ \overset{\times\ x}\Longrightarrow\ \ x^{\large 5}&\equiv\ \ldots\ \ \text{as above} \end{align}\qquad\qquad\qquad\qquad\qquad\qquad

Continuing we can rewrite $$\,x^{\large 4},x^{\large 5}\ldots$$ all as linear polynomials in $$x$$, and use this table to quickly rewrite any polynomial $$f(x)$$ as a linear polynomial $$\, f\bmod g\,=\, r\,$$ in the above notation.

Remark  In some cases it may be simpler to use Horner nested form, e.g. as here, to reduce $$\!\bmod \color{#c00}{x^4}-16$$ we rewrite the polynomial in nested form, pulling out factors of $$\,\color{#c00}{x^4}\,$$ as follows

\begin{align} &\ 3 - 2\ x^3\ \ \ +\ \ \ \,5\ x^5\ \ \ -\ \ \ \ \,11\ x^9 \ \ +\, \ \ 7\ x^{13}\\[.3em] =\ &\ 3 - 2\ x^3 + \color{#c00}{x^4}\ (5\ x + \color{#c00}{x^4}\ (-11\ x + \color{#c00}{x^4}\ (7\ x)))\end{align}\qquad\qquad

Substituting $$\, \color{#c00}{x^4} = 16\$$ above yields the sought remainder of degree $$< \color{#c00}4$$.

From the given equation,

$$a^2=a+3.$$

Then multiplying by $a$ and substituting,

$$a^3=a^2+3a=a+3+3a.$$

Zo simple.

The "hard" way:

The roots of the quadratic are $$a=\frac{1\pm\sqrt{13}}2.$$

Then taking the cube (by the binomial theorem), $$a^3=\frac{1\pm3\sqrt{13}+3\cdot13\pm13\sqrt{13}}8=5\pm2\sqrt{13}.$$

To account for the square root of $13$, you take $4a$, giving $2\pm2\sqrt{13}$ and add $3$ to adjust the integer term.

Another way to approach this is to use $(a^2-a+1)(a+1)=a^3+1$. Then you can say

\begin{align}a^2-a-3&=0\\ a^2-a+1&=4\\ (a^2-a+1)(a+1)&=4(a+1)\\ a^3+1&=4a+4\\ a^3&=4a+3\end{align}

• Thanks, I would like to know how you can learn such "tricks". Are the Art of Problem Solving books good for these sort of things? Commented Aug 29, 2017 at 17:13
• @delivosa It's not a "trick". Rather, it is a special case of computing modulo a polynomial - see my answer. This is algebraically reified when one studies quotient rings. Commented Aug 29, 2017 at 17:14
• Okay, thank you for that insight. Thought it was some shortcut you just know, still very new to this. Commented Aug 29, 2017 at 17:15