# Homework Help: Langrange interpolation polynomial and Euclidian division

1. May 15, 2015

### geoffrey159

1. The problem statement, all variables and given/known data
Let $x_1,...,x_n$ be distinct real numbers, and $P = \prod_{i=1}^n(X-x_i)$.
If for $i=1...n$, $L_i = \frac{\prod_{j \neq i}^n(X-x_j)}{\prod_{j\neq i}(x_i-x_j)}$, show that for any polynomial A (single variable and real coefs), the rest of the euclidian division of A by P is $\sum_{i=1}^n A(x_i)L_i$

2. Relevant equations

$Q = \sum_{i=1}^n A(x_i)L_i$

3. The attempt at a solution

Hello, could you tell me if my proof is correct please? It seems correct to me but I have a doubt.

Let $(B,R)$ the quotient and the rest of the euclidian division of A by P. We have that $\text{deg}(R)<\text{deg}(P) = n$, and $A = BP+R$.

Since $Q(x_i) = A(x_i) = R(x_i)$, then for all $i = 1...n$, $(R-Q)(x_i) = 0$, so $X-x_i$ divides $R-Q$
But for $i\neq j$, $X-x_i$ and $X-x_j$ are relatively prime and divide $R-Q$, so $P | R-Q$.
However, $\text{deg}(R-Q) \le \max(\text{deg}(R),\text{deg(Q)}) \le n-1 < n =\text{deg}(P)$, so $R-Q = 0$

Last edited: May 15, 2015
2. May 16, 2015

### wabbit

Seems perfectly fine to me.
You could formulate it in a marginally more direct way perhaps, e.g. saying A-Q is zero at each x_i, hence it divides P, etc. - but this is equivalent to what you say.