# Find a polynomial in $\mathbb{Z}_{41}$

Find a $$7^\text{th}$$ degree polynomial $$p(x)$$ in $$\mathbb{Z}_{41}[x]$$, so that $$p(14^i) = i\pmod{41}\ \forall i = 0,1,\ldots,7.$$

Hint: $$3$$ is the $$8^\text{th}$$ primitive root of unity and $$3 \cdot 14 = 8 \cdot 36 = 1$$ in $$\mathbb{Z}_{41}$$.

How does one solve such a task?

I shall write $$w$$ for $$14$$. Note that $$w^8=1$$. For $$k=0,1,2,\ldots,8$$, consider the polynomial $$f_k(x):=\frac{w^k}{8}\left(\frac{x^8-1}{x-w^k}\right)=\frac{1}{8}\left(\frac{\left(w^{-k}x\right)^8-1}{w^{-k}x-1}\right)=\frac{1}{8}\left(\sum_{r=0}^7\,w^{-kr}x^r\right)\,.$$ Furthermore, for $$l=0,1,2,\ldots,8$$ with $$l \neq k$$, $$f_k\left(w^l\right)=0$$, whereas $$f_k\left(w^k\right)=1$$. The unique polynomial $$p(x) \in \mathbb{F}_{41}[x]$$ satisfying the condition is $$p(x)=\sum\limits_{k=0}^7\,k\,f_k(x)$$. That is, $$p(x)=\frac{1}{8}\,\sum_{k=0}^7\,k\,\sum_{r=0}^7\,w^{-kr}x^r=\frac{1}{8}\,\sum_{r=0}^7\,\left(\sum_{k=0}^7\,k\,w^{-kr}\right)\,x^r\,.$$
Now, consider $$g(x)=\frac{x^8-1}{x-1}=\sum_{r=0}^7\,x^r$$. Then, $$\sum_{k=0}^7\,k\,x^k=x\,g'(x)=\frac{8x^8}{x-1}-\frac{x\left(x^8-1\right)}{(x-1)^2}\,.$$ Thus, $$\sum_{k=0}^7\,k\,w^{-kr}=w^{-r}\,g'\left(w^{-r}\right)=\frac{8}{w^{-r}-1}$$ for $$r=1,2,\ldots,7$$. Consequently, $$p(x)=24+\sum_{r=1}^7\,\frac{1}{w^{-r}-1}\,x^r=24+\sum_{r=1}^7\,\frac{1}{3^r-1}\,x^r\,,$$ as $$w^{-1}=14^{-1}=3$$. That is, $$p(x)=24+21x+36x^2+30x^3+20x^4+10x^5+4x^6+19x^7\,.$$
• If that is what you wanted, then let $p(x)=\sum_{k=0}^7\,p_kx^k$ for some $p_0,p_1,p_2,\ldots,p_7\in\mathbb{F}_{41}$. Then, consider the FFT matrix $\mathbf{F}:=\left[w^{ij}\right]_{i,j\in[7]}$, where $[7]:=\{0,1,2,\ldots,7\}$, and vectors $\mathbf{p}:=\left(p_0,p_1,\ldots,p_7\right)$ and $\mathbf{q}:=\left(0,1,2,\ldots,7\right)$. The inverse is $\mathbf{F}^{-1}=\frac{1}{8}\left[w^{-ij}\right]_{i,j\in[7]}$. Hence, the condition on $p(x)$ is the same as saying $\mathbf{Fp}=\mathbf{q}$, which then implies $\mathbf{p}=\mathbf{F}^{-1}\mathbf{q}$, and the rest is only computation. – Batominovski Jun 21 '15 at 10:11