Use Euler's Theorem to Find a Number $x$ between $0$ and $28$ such that $x^{85} \equiv 6 \pmod{35}$

Question

Problem: Use Euler's Theorem to Find a Number $x$ between $0$ and $28$ such that $x^{85} \equiv6\pmod{35}$

Hi all,

I have narrowed this problem down to $x^{13} \equiv6 \pmod{35}$. I got here by splitting up $x^{85}$ into $x^{24}\cdot x^{24}\cdot x^{24}\cdot x^{13}$, and then cancelling out the $x^{24}$'s to just $1$'s (using Euler's theorem which states that $x^{\phi(n)} \equiv1 \pmod{n}$; $\phi(35) = 24$).

I'm stuck on how to proceed from here. Any tips?

Answer 1

$a^{24} = 1 \mod(35)$ so $a^{12} = \pm 1 \mod(35)$

So $a^{85} = a^{13} = a^{12}a = \pm a = 6 \mod(35)$. So $a = \{6, -6\}\mod 35$. As $6^2 = 1 \mod (35)$, $(-6)^{13} = -6 \mod 35$, so $a = 6\mod 35$, so a = 6.

=== oh, we were give a is between 0 and 28. So 29 = 35 -6 was out by premise.

Answer 2

$x^{85}\equiv6\pmod{35}\ \ \ \ (1)$

As $35=5\cdot7$ with $(5,7)=1$

$(1)\implies x^{85}\equiv6\pmod5\equiv1$

As $\phi(5)=4,85\equiv1\pmod4; x\equiv1\pmod5\ \ \ \ (2)$

$(2)\implies x^{85}\equiv6\pmod7$

As $\phi(7)=6,85\equiv1\pmod6; x\equiv6\pmod7\ \ \ \ (3)$

Apply CRT on $(2),(3)$ or by observation $x\equiv6\pmod{35}$