4
$\begingroup$

Given $p,q$ odd primes, prove that if $\gcd(a,pq)=1$ then $a^{\operatorname{lcm} (p-1,q-1)} \equiv 1 \pmod {pq}$

What I am thinking:

I know by Fermat's that $a^{p-1} \equiv 1 \pmod p$ and also $a^{q-1} \equiv 1 \pmod q$. I need to combine them somehow. Should I use the chinese remainder theorem?

In which case what is the inverse of $p \bmod q$ and vise versa?

$\endgroup$
2
$\begingroup$

Use the Chinese Remainder Theorem as you have suggested. But the easiest way is to use it to check your answer, not to find the answer. Let's write $l={\rm lcm}(p-1,q-1)$.

We have $$a^{p-1}\equiv1\pmod p\ ,$$ and since $l$ is a multiple of $p-1$, $$a^l\equiv1\pmod p\ .$$ Similarly $$a^l\equiv1\pmod q\ .$$ Therefore $x=a^l$ is a solution of the simultaneous congruences $$x\equiv1\pmod p\ ,\quad x\equiv1\pmod q\ ;$$ but by CRT this system has a unique solution modulo $pq$, and $x=1$ is clearly a solution, so we have $a^l\equiv1\pmod{pq}$.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

We need to assume that $p$ and $q$ are distinct.

Let $L$ be our lcm. Since $p-1$ divides $L$, we have $a^L\equiv 1\pmod{p}$. Similarly, $a^L\equiv 1\pmod{q}$. Thus $p$ divides $a^L-1$ and $q$ divides $a^L-1$. Since $p$ and $q$ are relatively prime, it follows that $pq$ divides $a^L-1$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ You are welcome. We are not really using the CRT, just simple facts about divisibility. $\endgroup$ – André Nicolas Dec 17 '15 at 1:09

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.