2

For how many distinct primes pqr can we have $$pq \equiv 1 \bmod r$$ $$pr \equiv 1 \bmod q$$ $$rq \equiv 1 \bmod p$$???

I've never arrived at something like this before ( i got here wile doing an olympiad problem)

Asinomás
  • 105,651

1 Answers1

2

The given congruences imply $$ pqr\mid pq+qr+rp-1 $$ This is because $p,q,r$ primes means that it suffices to verify that each of $p,q,$ and $r$ divide $pq+qr+rp-1$, but this is clear. Now clearly $pq+qr+rp-1>0$, so then we have $pqr\le pq+qr+rp-1$. WLOG assume that $p\ge q\ge r\ge 2$. Then $$ q(qr-q-r)\le p(qr-q-r)\le qr-1\Rightarrow q^2(r-1)-2qr\le-1 $$ But then $$ qr(\frac{q}{2}-2)\le\frac{q^2r}{2}-2qr\le q^2(r-1)-2qr<0 $$ So $q\le 3$.

If $q=2$, then $p=2$, so $4r\mid 4r+3$, which is impossible for $r\ge 2$.

If $q=3$ and $p=2$, then $6r\mid 5(r+1)$, so $r\mid 5$ give $r=5$ as the only possibility.

If $q=3$ and $p=3$, then $9r\mid 6r+8$, so $r\mid 2$, a contradiction.

pi37
  • 1,521
  • 7
  • 7
  • How did you think of that? – Asinomás Nov 07 '13 at 03:24
  • In general, for these types of olympiad problems a common strategy is to use bounding to limit the number of possible cases, and then do casework to finish. – pi37 Nov 10 '13 at 04:30
  • yes, what I couldn't think of was using the reflexive property of the equations to add them and get the strong result that pqr devided the sum – Asinomás Nov 10 '13 at 17:07