Exercises - Finding Roots

  1. Find a solution to $x^5 \equiv 11\pmod{29}$.  

    Suppose $x \equiv 11^u\pmod{29}$. Then $$\begin{array}{rcl} (11^u)^5 &\equiv& 11\pmod{29}\\ 11^{5u} &\equiv& 11\pmod{29} \quad \textrm{ but noting that $gcd(11,29) = 1$}\\ 11^{5u-1} &\equiv& 1\pmod{29}\\ \end{array}$$ Recall as a direct result of Euler's theorem, $11^{\phi(29)c} \equiv 1\pmod{29}$ for any positive integer $c$, and $\phi(29) = 28$. So we seek a $u$ so that $$5u - 1 = 28c$$ Applying the Euclidean Algorithm and back-substituting to generate a linear combination of $5$ and $28$ that yields $1$, we find $u=17$ will work.

    Finally, using successive squaring, we discover $$x \equiv 11^{17} \equiv 3 \pmod{29}$$

  2. Find solutions to $x^2 \equiv 5\pmod{11}$.  

    Noting that $11 \equiv 3\pmod{4}$ and $(11+1)/4 = 3$, we find $x \equiv 5^3 \equiv 4\pmod{11}$. Since $4^2 \equiv 5\pmod{11}$, the square roots we seek are $\pm4$.

  3. Find solutions to $x^2 \equiv 71\pmod{77}$.  

    Noting that $77 = 7 \cdot 11$, we decompose this congruence into two with prime moduli, $$x^2 \equiv 71 \equiv 1\pmod{7} \quad \textrm{ and } \quad x^2 \equiv 71 \equiv 5\pmod{11}$$ For the first congruence, noting that $7 \equiv 3\pmod{4}$ and $(7+1)/4 = 2$, we find $x \equiv 1^2 \equiv 1\pmod{7}$. Since $1^2 \equiv 1 \pmod{7}$, we have $x \equiv \pm 1\pmod{7}$

    For the second congruence, noting that $11 \equiv 3\pmod{4}$ and $(11+1)/4 = 3$, we find $x \equiv 5^3 \equiv 4\pmod{11}$. Since $4^2 \equiv 5\pmod{11}$, we have $x \equiv \pm4\pmod{11}$.

    So we have $$x \equiv \pm 1\pmod{7} \quad \textrm{ and } \quad x \equiv \pm 4\pmod{11}$$ Suppose it was the case that $x \equiv 1\pmod{7}$ and $x \equiv 4\pmod{11}$. These could be combined via the Chinese Remainder Theorem to deduce $x \equiv 15\pmod{77}$.

    Accounting for the other possibilities and again using the Chinese Remainder Theorem in each case, we discover $$x \equiv \pm 15 \textrm{ or } \pm 29 \pmod{77}$$