## A community for students. Sign up today

Here's the question you clicked on:

## praxer one year ago Explain the proof :

• This Question is Closed
1. praxer

Help me understand the corollary

2. praxer

@satellite73

3. anonymous

consider if we have $$n+1$$ values $$a_0,\dots,a_n$$. if the functions match at all points, we have: $$P(a_0)=Q(a_0)\\P(a_1)=Q(a_1)\\\dots\\P(a_n)=Q(a_n)$$ for a particular $$P(a_i)=Q(a_i)$$, we can equivalently write $$P(a_i)-Q(a_i)=0$$ define the polynomial function $$R(x)=P(x)-Q(x)$$, so the earlier list of equations tells us:$$R(a_0)=0\\R(a_1)=0\\\dots\\R(a_n)=0$$ so it follows that $$R$$ has $$n+1$$ zeros. but since $$R(x)=P(x)-Q(x)$$, it follows that $$R$$ is at most dimension $$n$$

4. anonymous

at most degree* n

5. anonymous

so it follows that we must have that $$R(x)=0$$ everywhere (in other words, in the representation $$R(x)=c(x-x_1)\dots(x-x_n)$$, we must have $$c=0$$)

6. anonymous

and if $$R(x)=0$$, well $$R(x)=P(x)-Q(x)$$ so that means $$P(x)-Q(x)=0\implies P(x)=Q(x)$$

7. praxer

Okay for the $$P(a_0)=Q(a_0)$$ what does it basically explain the value of the function being equal or the term $$a_0$$

8. anonymous

it means the two different polynomials $$P,Q$$ match at $$x=a_0$$

9. praxer

in the first part why is it taken that 6|K please explain :)

10. praxer

I want to understand the approach in the question. Please help

11. anonymous

$$\epsilon_{1,2}$$ are roots of unity -- recall that: $$\cos(\pm\pi/3)=\pm\frac12\\\sin(\pm\pi/3)=\frac{\sqrt3}2\\$$

12. anonymous

so we have: $$\epsilon_1=\cos(\pi/3)+i\sin(\pi/3)$$now by de Moivre's theorem we see $$\epsilon_1^3=\cos(3\cdot\pi/3)+i\sin(3\cdot \pi/3)=\cos(\pi)+i\sin(\pi)=-1$$ and so $$\epsilon_1^6=(\epsilon_1^3)^2=(-1)^2=1$$

13. anonymous

similarly, $$\epsilon_2=\cos(-\pi/3)+i\sin(-\pi/3)\\\epsilon_2^3=\cos(-\pi)+i\sin(-\pi)=-1\\\epsilon_2^6=(\epsilon_2^3)^2=(-1)^2=1$$

14. anonymous

equivalently, you could've just done de Moivre's theorem directly for the sixth power, so: $$\epsilon_1^6=\cos(6\cdot \pi/3)+i\sin(6\cdot \pi/3)=\cos(2\pi)+i\sin(2\pi)=1\\\epsilon_2^6=\cos(6\cdot-\pi/3)+i\sin(6\cdot-\pi/3)=\cos(-2\pi)+i\sin(-2\pi)=1$$

15. anonymous

and yes @ParthKohli I meant to say: $$\cos\left(\pm\frac{\pi}3\right)=\frac12\\\sin\left(\pm\frac\pi3\right)=\pm\frac{\sqrt3}2$$

16. anonymous

anyways, they factor $$x^2-x+1=(x-\epsilon_1)(x-\epsilon_2)$$ because that way we can check if $$x^2-x+1$$ divides $$x^n-x+1$$ by merely checking if the individual factors $$x-\epsilon_1,x-\epsilon_2$$ divide $$x^n-x+1$$. by the factor theorem, we know that $$x-\epsilon$$ is a factor of $$f(x)=x^n-x+1$$ if and only if $$f(\epsilon)=0$$; in other words, $$\epsilon^n-\epsilon+1=0$$ so in this case we're checking both factors $$x-\epsilon_1,x-\epsilon_2$$ so we have: $$\epsilon_1^n-\epsilon_1+1=0\\\epsilon_2^n-\epsilon_2+1=0$$

17. anonymous

anyways, since $$\epsilon_1,\epsilon_2$$ are roots of $$x^2-x+1=0$$, consider: $$x^2-x+1=0\\x(x-1)=-1\\x(1-x)=1$$so it follows that $$x(1-x)=1$$ or $$1-x=\frac1x=x^{-1}$$ for $$x\in\{\epsilon_1,\epsilon_2\}$$ -- in other words, $$1-\epsilon_1=1/\epsilon_1\\1-\epsilon_2=1/\epsilon_2$$

18. anonymous

also i had the $$n$$-th degree polynomial wrong, I meant to write $$f(x)=x^n+x-1$$ so $$\epsilon_1^n+\epsilon_1-1=0\\\epsilon_2^n+\epsilon_2-1=0$$

19. anonymous

in which case we can rewrite the equations like: $$\epsilon_1^n=1-\epsilon_1\\\implies \epsilon_1^n=1/\epsilon_1\\\epsilon_2^n=1-\epsilon_2\\\implies \epsilon_2^n=1/\epsilon_2$$

20. anonymous

in other words, $$\epsilon_1^{n+1}=1$$ and $$\epsilon_2^{n+1}=1$$ by multiplying both sides by $$\epsilon_1,\epsilon_2$$ respectively

21. anonymous

and yet we saw that: $$\epsilon_1^6=\epsilon_2^6=1$$so taking both sides to any integer power $$i$$ we have $$\epsilon_1^{6i}=\epsilon_2^{6i}=1$$ so it follows that we must have $$n+1=6i\implies n=6i-1$$

22. praxer

thank u :)

23. anonymous

the reason I showed earlier that $$\epsilon_1^3=\epsilon_2^3=-1$$ earlier is to show that $$k=6$$ is the *smallest* positive integer such that $$\epsilon_1^k=\epsilon_2^k=1$$, otherwise we could've had other solutions we missed

24. anonymous

oops, I said show and earlier too many times

25. ganeshie8

so that $$i$$ in $$6i-1$$ has nothing to do with the imaginary unit $$i$$ haha!

#### Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy