Suppose that $p,q$ are distinct odd primes. Suppose an integer $k$ divides $pq-1$ and also $k|\operatorname{lcm}(p-1,q-1)$. Show that $k|\operatorname{gcd}(p-1,q-1)$.
I've spent ages looking at this problem and very little to show. Surely I would want to use the hypothesis that p and q are not equal. This would mean their gcd is 1. How to use this assumption?