# Fermat's Little Theorem and Prime Moduli

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$.

• Did you notice that there is a mistake in the first line of your Hint 1? 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)$

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