Notation: $(a,b) = \gcd(a,b)$

If $p,q$ are distinct odd primes, is it true that

$$(pq,(p-1)(q-1)) =1 \iff (pq,\operatorname{lcm}(p-1,q-1))=1\;?$$


2 Answers 2


Yes, that statement is true. In fact, it is true for all $p$ and $q$ integers greater than $1$: they do not need to be distinct or odd primes.

The key point is that for positive integers $a$ and $b$, the prime factors of $\operatorname{lcm}(a,b)$ are the same as the prime factors of $ab$, which are also the prime factors of either $a$ or $b$ or both. Let me know if you need a proof of this (there are several).

Therefore, for any positive integers $a,b,c$,

$$\gcd(c,ab)=1 \iff \gcd(c,\operatorname{lcm}(a,b))=1$$

Now substitute $c=pq,\ a=p-1,\ b=q-1$, and we get your proposition.


Let $(pq,(p-1)(q-1))=1 $, suppose $k=(pq,lcm(p-1,q-1))$ then
$k|pq$ and $k|lcm(p-1,q-1)=\frac{(p-1)(q-1)}{(p-1,q-1)} \Rightarrow$
$k|pq$ and $k|(p-1)(q-1)$ , since $(pq,(p-1)(q-1))=1\Rightarrow$ $k=1$ .

Now let $(pq,lcm(p-1,q-1))=1$ , suppose $(pq,(p-1)(q-1))=k $ then
$k|pq$ and $k|(p-1)(q-1)=pq-p-q+1 \Rightarrow k\nmid (p-1,q-1)$ and $k|(p-1)(q-1)$ then $k|lcm(p-1,q-1)$ since $(pq,lcm(p-1,q-1))=1$ so $k=1$ .


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.