Congruence Equation involving Modulo and Indices

Question

I have a question I want to answer but am having trouble understanding the method as this is the first one of these problems i have encountered with indices. I must solve for $x\leq34$ $$x^5 \equiv 11(mod 35)$$

What is the method to solve this, usually I would use the GCD algorithm between the factor in front of the $x$ and the number 35 but that will not work here.

Answer 1

Modular arithmetic is cyclical.

That is if $gcd(n,m) = 1$

Then there exists an $a$ such that $n^a \equiv 1 \pmod m$

And $a$ divides $\phi (m)$ where $\phi$ is the Euler phi function.

So what is that $a$ when $n = 11$ and $m = 35?$

$11^2 \equiv 16 \pmod {35}\\ 11^3 \equiv 1 \pmod {35}$

Which means that $11^{10} \equiv 11^9\cdot 11 \equiv 11 \pmod {35}$ and $(11^2)^5 \equiv 16^5 \equiv 11\pmod {35}$