# If a divisor of $pq-1$ divides the LCM of $p-1$ and $q-1$, then it also divides the GCD of these two numbers

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.$

• But this only shows that any prime factor of $k$ divides the gcd, not that $k$ divides the gcd, right? – awllower Oct 8 '15 at 3:29
• @awllower You are right, let me see if I can fix that (at first I thought that it was a typo, but then I realized that in fact it doesn't prove that $k\mid g$) – CIJ Oct 8 '15 at 4:22
• It is fixed now. – CIJ Oct 12 '15 at 12:57
• I think you mean $(a+b)x+b(y-x)=1,$ and likewise for the next equation. Also, thanks then for the great answer. – awllower Oct 12 '15 at 13:39
• Yes, I meant that, thanks!. – CIJ Oct 12 '15 at 13:55

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$.

• If our answers aren't identical, I think you should post your solution – Julian Rosen Oct 8 '15 at 2:53
• I don't understand why if $\ell^n$ is a prime power dividing $\mathrm{lcm}(p-1,q-1)$ then $\ell^n$ divides $p-1$ and $q-1$ (I would if $\ell^n$ were a prime)? – Gero Oct 10 '15 at 21:29