following problem I am supposed to solve on paper.
Use Newton-Iteration to find a primitive 16th root of unity over $\mathbb{Z}/17^{16}\mathbb{Z}$ with $\omega = 6 \pmod{17}$
I have some kind of idea how to start here:
The problem is actually to find $ X^{16}-1 = 0 \pmod{17^{16}} $ under the restriction $ X = 6 \pmod{17}$
So newton gives us $X_{k+1}=X_k-\frac{X_k^{16}-1}{16X_k^{15}}$. My problem is how to keep the restriction in mind + $\pmod{17^{16}}$ ?
Thank you.
Hensel's lemma gives you precisely what you want; this is the $p$-adic analog of Newton iteration.
Let $f:=X^{16}-1\in\Bbb{Z}[X]$, and note that if $x\in\Bbb{Z}$ is a root of $f$ modulo $17^k$ for some $k>0$, i.e. it satisfies $f(x)\equiv0\pmod{17^k}$, then $f'(x)\not\equiv0\pmod{17^k}$. This means we can apply Hensel's lemma to can lift such a root modulo $17^k$ to a solution modulo $17^{k+1}$.
Modulo $17$ you have the solution $6\in\Bbb{Z}$, because by Fermat's/Euler's theorem $$6^{16}\equiv1\pmod{17}.$$ Then the unique solution $x\in\Bbb{Z}/17^2\Bbb{Z}$ satisfying $x\equiv6\pmod{17}$ is given by $$x_2:=6-\frac{f(6)}{f'(6)}\equiv40\pmod{17^2},$$ where all operations are done in $\Bbb{Z}/17^2\Bbb{Z}$. Repeating this process we find the unique solution $$x_3:=x_2-\frac{f(x_2)}{f'(x_2)}\equiv4086\pmod{17^3},$$ to $f$ with $x_3\equiv6\pmod{17}$, where all operations are done in $\Bbb{Z}/17^3\Bbb{Z}$. This can be repeated to get a solution in $\Bbb{Z}/17^{16}\Bbb{Z}$, though I don't recommend doing this by hand.