How to calculate $x$ in $x^{17} = 20 \pmod {1001}$

Question

I'm doing a cryptology problem and stuck here. I don't know how to find $x$ in the equation:

$$x^{17} \equiv 20 \mod 1001$$

Answer 1

Hint: $1001 = 7 \cdot 11 \cdot 13$. Do you know the Chinese Remainder Theorem?

Of course if you have a computer available it's trivial to try $1001$ cases...

Answer 2

By hand:

$1001=7\cdot 11\cdot 13$ so find the answer for these separate modulus values and combine with the Chinese Remainder theorem.

$\bmod 7: x^{17}\equiv 20 \underset{\text {red by }7/^{\large \phi(7)}}{\implies} x^5\equiv 6 \underset{x^6\equiv 1}{\implies} x\equiv 6$

$\bmod 11: x^{17}\equiv 20\underset{\text {red by }11/^{\large \phi(11)}}{\implies} x^7\equiv 9\underset{5^2\equiv 3}{\implies} x\equiv 3$

$\bmod 13: x^{17}\equiv 20\underset{\text {red by }13/^{\large \phi(13)}}{\implies} x^5\equiv 7$

No obvious shortcuts on that one so I evaluated the odd powers of $2: \{2,8,6,11,5,7\}$ (in the well-founded hope that $2$ is a primitive root) to infer that $7\equiv 2^{11} \equiv 2^{35} \equiv (2^7)^5 \equiv 11^5$ giving $x\equiv 11 \bmod 13$

So
$\left .\begin{array}{r} \left .\begin{array}{r} x\equiv 6 \bmod 7 \\ x\equiv 3 \bmod 11 \end{array}\right\rbrace x\equiv 69 \bmod 77 \\ x\equiv 11 \bmod 13 \end{array}\right\rbrace x\equiv 69+6\cdot 77 \equiv 531 \bmod 1001 $

(the last calculation there arising from $69\equiv 4$ and $77\equiv -1$ needing to get to $11\equiv-2 \bmod 13$ )