I came across this exercise in solving a modular congruence:
Find an integer $0\le x<527$ such that $$x^{37}\equiv3\mod527$$
but being fairly new to this branch of number theory (and the topic in general), I'm not sure how to proceed. My current knowledge doesn't exceed what I've gleaned from the Wikipedia article on modular arithmetic and a few examples I've worked out involving the Euclidean algorithm.
Attempt: I thought to simplify the above slightly by considering the congruence
$$3y\equiv1\mod527$$
then via the Euclidean algorithm found the modular inverse to be $y=176$; easy enough.
Then multiplying by $3$ gives
$$9y\equiv3\mod527$$
suggesting that the solution to my problem satisfies $x^{37}=1584$. But I'm hitting a wall, and I don't even know whether this is correct to begin with.
Wolfram|Alpha tells me I should arrive at $x=148$, which makes me think my reasoning above isn't valid or that what I'm doing simply isn't productive. Is there a "right" method I should be using?
Best Answer
Use the Chinese Remainder Theorem, noting that $527=17\times31$. Thus $$x^{37}\equiv3\pmod{527}$$ is equivalent to $$x^{37}\equiv3\pmod{17}\quad\hbox{and}\quad x^{37}\equiv3\pmod{31}\ .$$ By Fermat's Little Theorem (terms and conditions apply) $a^{p-1}\equiv1\pmod p$, so these are equivalent to $$x^5\equiv3\pmod{17}\quad\hbox{and}\quad x^7\equiv3\pmod{31}\ .$$ Now these are small enough to solve by trial and error (alternative: see below), giving $$x\equiv-5\pmod{17}\quad\hbox{and}\quad x\equiv-7\pmod{31}\ ,$$ and then the standard CRT procedure gives $$x\equiv148\pmod{527}\ .$$
Alternative way to solve $x^5\equiv3\pmod{17}$: raise to the power $s$ such that $x^{5s}\equiv x\pmod{17}$. This requires $5s\equiv1\pmod{16}$ and we may take $s=13$. So $$x^5\equiv3\quad \Rightarrow\quad x\equiv x^{65}\equiv(x^5)^{13}\equiv3^{13}\pmod{17}$$ and we calculate $$3^2\equiv9\ ,\quad 3^4\equiv9^2\equiv81\equiv-4\ ,\quad 3^8\equiv(-4)^2\equiv16\equiv-1$$ and finally $$3^{13}\equiv3^8\times3^4\times3^1\equiv12\equiv-5\pmod{17}\ .$$