8
$\begingroup$

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?

Improve this question
$\endgroup$
3
$\begingroup$

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

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ But this only shows that any prime factor of $k$ divides the gcd, not that $k$ divides the gcd, right? $\endgroup$ – awllower Oct 8 '15 at 3:29
  • 1
    $\begingroup$ @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$) $\endgroup$ – CIJ Oct 8 '15 at 4:22
  • $\begingroup$ It is fixed now. $\endgroup$ – CIJ Oct 12 '15 at 12:57
  • 1
    $\begingroup$ I think you mean $(a+b)x+b(y-x)=1,$ and likewise for the next equation. Also, thanks then for the great answer. $\endgroup$ – awllower Oct 12 '15 at 13:39
  • 1
    $\begingroup$ Yes, I meant that, thanks!. $\endgroup$ – CIJ Oct 12 '15 at 13:55
2
$\begingroup$

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

Improve this answer
$\endgroup$
  • $\begingroup$ If our answers aren't identical, I think you should post your solution $\endgroup$ – Julian Rosen Oct 8 '15 at 2:53
  • 1
    $\begingroup$ 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)? $\endgroup$ – Gero Oct 10 '15 at 21:29

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.