Find p and q s.t. $({p-1})^{q-1}+({q-1})^{p-1} \equiv 101 \pmod {pq}$
The question is:
Find two distinct odd primes p and q such that $({p-1})^{q-1}+({q-1})^{p-1} \equiv 101 \pmod {pq}$ Well... I only have the idea to write down
${p-1}^{q-1} \equiv -1^{q-1} \equiv 1 \pmod {p}$
Actually, I solve this question by brute force and get p=11 q=3; however, I wanna know some wise solutions...
Mine is .... a bad one
Please help me to solve this question :(
Taking your equation mod $p$,
$$(-1)^{q-1} + (q-1)^{p-1} \equiv 101 \ (\text{mod }p)$$ But $q$ is an odd prime, so $(-1)^{q-1} = 1$, and thus $(q-1)^{p-1} \equiv 100 \ (\text{mod }p)$. Similarly $(p-1)^{q-1} \equiv 100 \ (\text{mod }q)$. Now use Fermat's "little" theorem (but don't forget the case where $p$ or $q$ is $5$).