Find the $\gcd(pq, (p-1)(q-1))$ if $p$ and $q$ are prime.

Question

Given prime numbers p,q , how do I prove that gcd(pq, (p-1)(q-1)) = p, q or 1?

Answer 1

What can the greatest common divisor be? It is $1$, $p$ or $q$. Can you exclude the cases $p$ and $q$?

Alternatively, use $$ \gcd(pq,(p-1)(q-1))=\gcd(pq,pq-(p-1)(q-1)= \gcd(pq,p+q-1) $$

Answer 2

Let $d$ divides $pq,(p-1)(q-1)=pq-p-q+1;$

$d$ must divide $pq-(p-1)(q-1)=p+q-1$

As $p,q$ are primes, $d$ can be $1,p,q$

$d\ne pq$ as $pq>(p-1)(q-1)$

If $d=p,d=p$ must divide $q-1$

Example $p=11, q=11k+1=23,67$ etc.

Answer 3

Only possible values are $1$, $p$, $q$ and $pq$. So one way is to show that $pq$ does not divide $(p-1)(q-1)$.

Since $p$ and $p-1$ are coprime, and same applies for $q$ and $q-1$, then $pq$ would divide $(p-1)(q-1)$ only if $p$ divides $q-1$ and $q$ divides $p-1$. But then you have $$p\leq q-1 \leq p-2$$ which cannot be, so original $\gcd$ can only be one of $1$, $p$ and $q$.

Note: You still need to show that actually all of these three cases can happen, but that is not hard by simply checking few examples.