Prove if $ x^{11}\equiv 21$ (mod $59$) then $x^{9}\equiv 35$ (mod $59$)

Question

Prove if $ x^{11}\equiv 21$ (mod $59$) then $x^{9}\equiv 35$ (mod $59$).

I know by Fermatt's Little Theorem, $x^{58} \equiv1$ (mod 59), and I know that $x^{58} = (x^{11})^5(x^3)$, but I dont know where to go from here. What do I do next?

Answer 1

In the field $\mathbb F_{59}$ we have $$x^{11}=21\Rightarrow x^{55}=x^{58}\cdot(x^{-1})^3=1\cdot x^{-3}=21^5\Rightarrow x^3=(21^{-1})^5$$

Therefore $$x^9=(21^{-1})^{15}$$ we have $21\cdot45=16\cdot59+1$ so $$x^9=(45)^{15}=(29)^5=(15)^2\cdot29=48\cdot29=\color{red}{35}$$

Answer 2

As you figured out $$(x^{11})^5 \equiv (21)^5 \equiv 3 \pmod{59} \Rightarrow (x^{11})^5x^3 \equiv 3x^3 \pmod{59} \Rightarrow \\ 1 \equiv 3x^3 \pmod{59} \Rightarrow 1 \equiv 3^3x^9 \pmod{59}\Rightarrow \\ 35 \equiv (35\cdot 27) \cdot x^9 \equiv x^9 \pmod{59}$$ since $$35\cdot 27 \equiv 1 \pmod{59}$$

Answer 3

Continuing rtybase's answer, A LDE can be formed : 27t + 59y =1, where t = x^9 You can now deuce that t=35 is the only solution when 0<= t < 59, hence t is equivalent to 35 (mod 59)