5
$\begingroup$

Assume that $p$ and $q$ are distinct add primes such that $p-1\mid q-1$. If $\gcd(a,pq)=1$ ,show that: $a^{q-1} \equiv 1 \pmod{pq}$

I have tried as follows: $a^{q-1} \equiv 1 \pmod{q} \quad \text{and} \quad a^{p-1} \equiv 1 \pmod{p}$ $\implies a^{(q-1)(p-1)} \equiv 1 \pmod{q} \quad \text{and} \quad a^{(q-1)(p-1)} \equiv 1 \pmod{p}$ $\implies a^{(q-1)(p-1)} \equiv 1 \pmod{pq}$
But then I am stuck - please help.

  • 1
    Damn, I lost the type-off this time. But hint: Chinese Remainder Theorem.2012-06-09

3 Answers 3

6

Remember that you are told that $p-1$ divides $q-1$. Note that you have not yet used this hypothesis. That suggests that you should really try to use it somehow.

Since $p-1$ divides $q-1$, then there exists $k$ such that $q-1 = k(p-1)$. That means that, since $a^{p-1}\equiv 1\pmod{p}$, then $1 \equiv 1^k \equiv (a^{p-1})^k \equiv a^{(p-1)k} = a^{q-1}\pmod{p}.$

So now you have $a^{q-1}\equiv 1\pmod{q}$ and $a^{q-1}\equiv 1\pmod{p}.$

3

Note that $p-1\mid q-1$ means that $q-1=k(p-1)$ for some $k$. Thus, $a^{p-1}\equiv 1\bmod p$ implies that $a^{q-1} = a^{k(p-1)} = (a^{p-1})^k\equiv 1^k= 1\bmod p.$ Now use the Chinese Remainder Theorem.

2

You know that:

$a^{p-1} \equiv 1$ mod $p$

but $(p-1)|(q-1)$ so this means that

$a^{q-1} \equiv 1$ mod $p$.

Now you may use the Chinese remainer theorem with your first congruence to tell you that

$a^{q-1} \equiv 1$ mod $pq$