Question
How do I perform a long division between $p(x)$ and $q(x)$ when they are not written in canonical base?
Description
Let $p(x)$ and $q(x)$ be polynomials of degree $n$ and $m$. I want to find two polynomials $a(x)$ and $r(x)$ such
$$p(x) = q(x) \cdot a(x) + r(x)$$
$a(x)$ is a polynomial of degree $(n-m)$ and $r(x)$'s degree is at maximum $(m-1)$.
In canonical base, we can write these polynomials as
$$\begin{align}p(x)& =p_0+p_1x+\cdots+p_nx^n \\ q(x)& =q_0+q_1x+\cdots+q_mx^m \\ a(x)& =a_0+a_1x+\cdots+a_{n-m}x^{n-m} \\ r(x)& =r_0+r_1x+\cdots+r_{m-1}x^{m-1} \\ \end{align}$$
But if these polynomials are written in another basis (like bezier shown bellow), how can I find the coefficients?
$$B_{i,n}(x)=\binom{n}{i}\left(1-x\right)^{n-i}\cdot x^i$$
$$\begin{align}p(x)& =P_0\cdot B_{0,n}(x)+P_1\cdot B_{1,n}(x)+\cdots+P_n\cdot B_{n,n}(x) \\ q(x)&=Q_0\cdot B_{0,m}(x)+Q_1\cdot B_{1,m}(x)+\cdots+Q_m\cdot B_{m}(x) \\ a(x)&=A_0\cdot B_{0,n-m}(x)+A_1\cdot B_{1,n-m}(x)+\cdots+A_{n-m}\cdot B_{n-m,n-m}(x) \\ r(x)&=R_0\cdot B_{0,m-1}(x)+R_1\cdot B_{1,m-1}(x)+\cdots+R_{m-1}\cdot B_{m-1,m-1}(x) \\ \end{align}$$
My main interest is in bezier, but maybe There are other polynomial families like Laguerre or Legendre which may be useful the property of orthogonality
Here we consider the $(n+1)$-dimensional vector space of polynomials $F_{n}$ of degree less or equal $n$ with coefficients in $\mathbb{R}$. The polynomials \begin{align*} e_k(x):=x^k\qquad\qquad\qquad\qquad\qquad 0\leq k\leq n \end{align*} are a basis of $F_{n}$. The Bezier polynomials \begin{align*} B_{k,n}(x):=\binom{n}{k}x^k(1-x)^{n-k}\qquad\qquad 0\leq k\leq n \end{align*} are also a basis of $F_n$ since each $B_{k,n}$ has order $k, 0\leq k\leq n$. Here we use the term order as the degree of its non-zero term of lowest degree.
In order to find the coefficients we start with a small number, let's say $n=4$ and check if we can see a relationship. It is easy to represent $B_{k,n}(x)$ in terms of the standard basis $(e_k)_{0\leq k\leq n}=(x^k)_{0\leq k\leq n}$. We have in case $n=4$ \begin{align*} \begin{pmatrix} 1&-4&6&-4&1\\ &4&-12&12&-4\\ &&6&-12&6\\ &&&4&-4\\ &&&&1 \end{pmatrix} \begin{pmatrix} 1\\x\\x^2\\x^3\\x^4 \end{pmatrix} &= \begin{pmatrix} 1-4x+6x^2-4x^3+x^4\\ 4x-12x^2+12x^3-4x^4\ \ \\ 6x^2-12x^3+6x^4\ \ \ \ \ \ \ \ \ \ \\ 4x^3-4x^4\qquad\qquad\qquad\ \ \\ x^4\qquad\qquad\qquad\qquad\qquad \end{pmatrix}\\ \begin{pmatrix} 1&-4&6&-4&1\\ &4&-12&12&-4\\ &&6&-12&6\\ &&&4&-4\\ &&&&1 \end{pmatrix} \begin{pmatrix} 1\\x\\x^2\\x^3\\x^4 \end{pmatrix} &= \begin{pmatrix} B_{0,4}(x)\\ B_{1,4}(x)\\ B_{2,4}(x)\\ B_{3,4}(x)\\ B_{4,4}(x)\\ \end{pmatrix} \end{align*} such that empty entries in the matrix are filled with zeros. It's not too hard to find the inverse of the change-of-basis matrix above. We obtain \begin{align*} \begin{pmatrix} 1&1&1&1&1\\ &\frac{1}{4}&\frac{2}{4}&\frac{3}{4}&\frac{4}{4}\\ &&\frac{1}{6}&\frac{3}{6}&\frac{6}{6}\\ &&&\frac{1}{4}&\frac{4}{4}\\ &&&&\frac{1}{1} \end{pmatrix} \begin{pmatrix} B_{0,4}(x)\\ B_{1,4}(x)\\ B_{2,4}(x)\\ B_{3,4}(x)\\ B_{4,4}(x)\\ \end{pmatrix} = \begin{pmatrix} 1\\x\\x^2\\x^3\\x^4 \end{pmatrix}\tag{2} \end{align*} Here we have again an upper triangle matrix where empty entries are filled with zeros. We can write the entries in the change-of-basis matrix (2) in a form which can be easily generalized: \begin{align*} \begin{pmatrix} \binom{0}{0}&\binom{1}{0}&\binom{2}{0} &\binom{3}{0}&\binom{4}{0}\\ &\frac{1}{4}\binom{1}{1}&\frac{1}{4}\binom{2}{1} &\frac{1}{4}\binom{3}{1}&\frac{1}{4}\binom{4}{1}\\ &&\frac{1}{6}\binom{2}{2} &\frac{1}{6}\binom{3}{2}&\frac{1}{6}\binom{4}{2}\\ &&&\frac{1}{4}\binom{3}{3}&\frac{1}{4}\binom{4}{3}\\ &&&&\binom{4}{4}\\ \end{pmatrix} \begin{pmatrix} B_{0,4}(x)\\ B_{1,4}(x)\\ B_{2,4}(x)\\ B_{3,4}(x)\\ B_{4,4}(x)\\ \end{pmatrix} = \begin{pmatrix} 1\\x\\x^2\\x^3\\x^4 \end{pmatrix}\tag{3} \end{align*}
With the transformation (4) we can then represent polynomials $p(x)=\sum_{k=0}^n a_kx^k$ in terms of $B_{j,n}, 0\leq j\leq n$.