TITLE: find $0 < l < 35$ such that $l^5 \equiv 3\pmod {35} $
QUESTION [0 upvotes]: I have to find some $0  < l < 35$,  such that $l^5 \equiv 3\pmod {35} $.
I tried to use suggestions from my previous question, 
So I tried: 
$l^5 \equiv 3\pmod {35} $ => $35 | l^5 - 3$,  I find some matching $l$'s
But I didn't find any matching number. I can't use calculator, so I guess there's some trick behind. please help.

REPLY [2 votes]: $(l,35)=(3,35)=1$ by Euclidean Algorithm.
Now we have
$$l^{25}\equiv(l^{5})^{5}\equiv3^{5}\equiv243\equiv33\ (\mathrm{mod}\ 35)$$
from the question and
$$l^{24}\equiv l^{\varphi(35)}\equiv1\ (\mathrm{mod}\ 35)$$
by Euler's Theorem.
Therefore, we get
$$l\equiv33\ (\mathrm{mod}\ 35).$$

REPLY [2 votes]: Here is a trick: Since $2^5 = 32 = 35 - 3$ you have $ 33^5 \equiv (-2)^5 \equiv -2^5 \equiv 3 \mod 35$

REPLY [0 votes]: HINT: $\ell^5\equiv 3\pmod 5$ has solution $\ell\equiv 3\pmod 5$; $\ell^5\equiv 3\pmod 7$ has solution $\ell\equiv 5\pmod 7$. (I found these by brute force, since there are very few numbers to test.) The numbers in the required range that are congruent to $5$ modulo $7$ are $5,12,19,26$, and $33$; those that are congruent gto $3$ modulo $5$ are $3,8,13,18,23,28$, and $33$. Can you draw a conclusion from this?
{"set_name": "stack_exchange", "score": 0, "question_id": 440344}