Prove that$$\left(m^{(p-1)(q-1)}\right)^km\equiv m\text{ }(\text{mod }pq),$$where $m

Question

Prove that$$\left(m^{(p-1)(q-1)}\right)^km\equiv m\text{ }(\text{mod }pq),$$where $m<pq$, $\gcd(m,pq)\neq1$, $p$ and $q$ are primes, and $k\in\mathbb{Z}$.

across · Answer

Assuming that $m$ is a positive integer, if $\gcd(m,pq)\neq1$, then $m$ is a multiple of either $p$ or $q$. Without loss of generality, let $m=p$. Then we have$$\left(p^{(p-1)(q-1)}\right)^kp\equiv p\text{ }(\text{mod }pq)$$and$$\left(p^{(p-1)(q-1)}\right)^k\equiv 1\text{ }(\text{mod }q).$$However,$$\left(p^{k(p-1)}\right)^{q-1}\equiv 1\text{ }(\text{mod }q),$$which is true by Fermat's little theorem. Can you wrap it up from here?

anonymous · Answer

yes. thank you very much