I am given two distinct primes $p$ and $q$, where $$m = p*q$$ Also,

$$ \begin{cases} r\equiv 1\mod p-1\\ r\equiv 1\mod q-1 \end{cases} $$

I have to show that given an integer a, show that $$a^r \equiv a \mod (m)$$

I'm not sure how to get started. I know I can tie this in to Fermat's Little Theorem and I've found something here CRT + Fermat's Little Theorem that was somewhat related to my question but I had a hard time seeing where to go. Just need a little hint to get me in the right direction! Thanks.


Hint #1. It's enough to show that $a^r\equiv a\pmod p$ and $a^r\equiv a\pmod q$; since $p$ and $q$ are relatively prime, it will follow from that that $a^r\equiv a\pmod{pq}$. By symmetry, it's enough to show that $a^r\equiv a\pmod p$.

Hint #2. What does $\ r\equiv1\pmod{p-1}\ \ $ mean? It means that $r-1$ is divisible by $p-1$; in other words, that $\ r=1+(p-1)m\ \ $ for some integer $m$.

  • $\begingroup$ Did you notice that there is a mistake in the first line of your Hint 1? $\endgroup$ Oct 30 '13 at 2:10

Since $\begin{cases} r\equiv 1\mod p-1\\ r\equiv 1\mod q-1 \end{cases}$ you can write $r=(p-1)k+1$ and $r=(q-1)l+1$ for some $k,l\in\mathbb{Z}$. Then $a^r=a^{(p-1)k+1}=a\cdot (a^{p-1})^k\equiv a (mod \;p)$ where the last conclusion follows from Fermat's Little Theorem. Similarly you have $a^r\equiv a(mod\; q)$. If you write $a^r=cp+a=dq+a$ you get that $cp=dq$ and since the primes are distinct it must be that $p \; |\;d$ which gives you $a^r=dq+a=pqd_1+a$ which means $a^r\equiv a (mod\; pq)$

  • $\begingroup$ Did you notice the part of the question where user1874239 said "Just need a little hint to get me in the right direction!"? $\endgroup$
    – bof
    Oct 30 '13 at 2:04
  • $\begingroup$ But Fermat's Little Theorem says a^(p-1) = a mod(p) not a^(p-1)^k = a mod (p). Are those two equivalent? $\endgroup$ Oct 30 '13 at 2:05
  • $\begingroup$ @bof I'm really sorry I missed that part from OP. $\endgroup$ Oct 30 '13 at 2:08
  • $\begingroup$ @user1874239 Please try and do this on your own, please ignore my post. I'm sorry I gave it away for you. $\endgroup$ Oct 30 '13 at 2:09
  • $\begingroup$ Fermat's Little Theorem says $a^{p-1}\equiv 1 (mod\;p)$. That means $a^p\equiv a (mod\;p)$. $\endgroup$ Oct 30 '13 at 2:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.