Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
    
Did you notice that there is a mistake in the first line of your Hint 1? –  mathemagician Oct 30 '13 at 2:10
    
Thanks for pointing that out. –  bof Oct 30 '13 at 2:50

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

share|improve this answer
    
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? –  user1874239 Oct 30 '13 at 2:05
    
@bof I'm really sorry I missed that part from OP. –  mathemagician 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. –  mathemagician 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)$. –  mathemagician Oct 30 '13 at 2:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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