2
$\begingroup$

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.

$\endgroup$

2 Answers 2

1
$\begingroup$

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

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

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

$\endgroup$
7
  • $\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, 2013 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, 2013 at 2:05
  • $\begingroup$ @bof I'm really sorry I missed that part from OP. $\endgroup$ Oct 30, 2013 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, 2013 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, 2013 at 2:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .