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?

$\endgroup$
0

2 Answers 2

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

$\endgroup$
5
  • 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, 2015 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, 2015 at 4:22
  • $\begingroup$ It is fixed now. $\endgroup$
    – CIJ
    Oct 12, 2015 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, 2015 at 13:39
  • 1
    $\begingroup$ Yes, I meant that, thanks!. $\endgroup$
    – CIJ
    Oct 12, 2015 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$.

$\endgroup$
2
  • $\begingroup$ If our answers aren't identical, I think you should post your solution $\endgroup$ Oct 8, 2015 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, 2015 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.