Modulo Equations

Question

I am trying to solve a problem involving modulo arithmetic but I am not sure what method to use as I have never done this style of question before nor do I have any examples to work from.

The question is:

Solve for $x$ where $x^5 = 11 \mod (35)$

So I though Eculid's GCD algorithm would help but I just get circular equations and get nowhere.

Thanks

Answer 1

Taking mod 10 on $x^5\equiv 11$ (mod 35)

the only possibilities of $x$ are:

$x\equiv 1$ or $6$

All $x$ in the range should be evaluated.

Using calculator $x\equiv 16$ (mod 35)

Answer 2

$x^5 \equiv 11 \mod 35$ means

$x^5 \equiv 11 \equiv 1 \mod 5$ and $x^5 \equiv 11 \equiv 4 \mod 7$

$0^5, 1^5, 2^5, 3^5, 4^5 \equiv 0^5, 1^5, 2^5, -2^5, -1^5 \mod 5 \equiv 0, 1, 32, -32, -1 \equiv 0, 1, 2, 3, 4 \mod 5$.

So $x \equiv 1 \mod 5$.

$0^5, 1^5, 2^5, 3^5, 4^5, 6^5, 6^7 \mod 7 \equiv 0^5, 1^5, 2^5, 3^5, -3^5, -2^5, -1^7 \mod 7 \equiv 0,1,4, 9*9*3, -9*9*3, -4, -1 \equiv 0, 1, 4, 2*2*3, -2*2*3, -4,-1 \equiv 0,1,4, 12, -12, -4, -1 \mod 7 \equiv 0,1,4,5,2,3,6 \mod 7$.

So $x \equiv 1 \mod 5$ and $x \equiv 2 \mod 7$. So $x \in \{1,6,11,16,21,26,31\} \cap \{2, 9, 16, 23, 30\} = \{16\}$. So $x \equiv 16 \mod 35$.

And indeed $16^5 = 2^{20} = 32^4 = (35 - 3)^4 = 35^4 -4*3*35^3 + 6*3^2*35^2 - 4*3^3*35 + 3^4 = 35*[35^3 - 4*3*35^2 + 6*3^2*35 - 4*3^3] + 81 = 35\{[35^3 - 4*3*35^2 + 6*3^2*35 - 4*3^3] + 2\} + 11 \equiv 11 \mod 35$.

Answer 3

Let $x\in\mathbb{Z}$ be such that $x^5\equiv 11\pmod{35}$. Then, $x^{15}=\left(x^5\right)^3\equiv 11^3\equiv 1\pmod{35}$. Since $\gcd(x,35)=1$, $x^{12}=x^{\text{lcm}(5-1,7-1)}=x^{\lambda(35)}\equiv 1\pmod{35}$, where $\lambda$ is the Carmichael function. Thus, $x^3=x^{\gcd(15,12)}=1\pmod{35}$, whence $1\equiv x^6\equiv x^5\cdot x\equiv 11\pmod{35}$, so that $x\equiv 11^{-1}\equiv 16\pmod{35}$, which is obviously a solution to this congruence.

Alternatively, $x^5\equiv 11\pmod{35}$ iff $x^5\equiv 1\pmod{5}$ and $x^5\equiv 4\equiv 3^4\pmod{7}$, which is equivalent to $x\equiv 1\pmod{5}$ and $x\equiv 3^2\equiv 2\pmod{7}$. Consequently, $x^5\equiv 11\pmod{35}$ if and only if $x\equiv 16\pmod{35}$.