Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
As someone else noted already, $p$ and $q$ need just be integers:
Let $l:=\text{lcm}(p-1,q-1)$ and $g:=\gcd(p-1,q-1).$
Since $lg=(p-1)(q-1)=(pq-1)+(p+q-2)$ and since $k\mid l\mid lg$ and $k\mid pq-1$ then $k\mid p+q-2=(p-1)+(q-1).$
Now write $p-1=ag$ and $q-1=bg,$ where $a,b\in\mathbb Z.$ Then $k\mid l=abg$ and $k\mid(p-1)+(q-1)=(a+b)g.$
Since $a$ and $b$ are coprime, there are $x,y\in\mathbb Z$ such that $ax+by=1$ and hence $(a+b)x+b(y-x)=1$ and $(a+b)y+a(x-y)=1$ and multiplying both expressions we have $$(a+b)\cdot((a+b)xy+(x-y)(bx-ay))-ab\cdot(x-y)^2=1$$ which means that $\gcd(a+b,ab)=1$ and thus $k\mid g.$
This is true for arbitrary integers $p$ and $q$, not just distinct odd primes.
It suffices to show that every prime power dividing both $\mathrm{lcm}(p-1,q-1)$ and $pq-1$ must also divide $p-1$ and $q-1$.
Suppose $\ell^n$ is a prime power dividing $\mathrm{lcm}(p-1,q-1)$ and $pq-1$. The first divisibility implies $p\equiv 1$ or $q\equiv 1\mod\ell^n$. The second divisibility means $p\equiv q^{-1}\mod\ell^n$, so whichever of $p$ or $q$ is congruent to $1$, the other is also. This shows $\ell^n|p-1$ and $\ell^n|q-1$.
