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}$.
Edit. I think a good start is to define $$F=\begin{pmatrix}1&1&1&1&1&1&1&1 \\ 1&14&14^2&14^3&14^4&14^5&14^6&14^7 \\ 1&14^2&14^4&14^6&14^8&14^{10}&14^{12}&14^{14}\\ 1&14^3&14^6&14^9&14^{12}&14^{15}&14^{18}&14^{21}\\ 1&14^4&14^8&14^{12}&14^{16}&14^{20}&14^{24}&14^{28}\\ 1&14^5&14^{10}&14^{15}&14^{20}&14^{25}&14^{30}&14^{35}\\ 1&14^6&14^{12}&14^{18}&14^{24}&14^{30}&14^{36}&14^{42}\\ 1&14^7&14^{14}&14^{21}&14^{28}&14^{35}&14^{42}&14^{49} \end{pmatrix}.$$ and then solve $$FP=B,$$ where $$P=\begin{pmatrix}p_0&p_1&p_2&p_3&p_4&p_5&p_6&p_7\end{pmatrix}^t$$ and $$B=\begin{pmatrix}0&1&2&3&4&5&6&7&8\end{pmatrix}^t.$$ How to solve $FP=B$?
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)=\dfrac{x^8-1}{x-1}=\sum\limits_{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\,.$$