3
$\begingroup$

Let $p,q$ and $r$ be prime numbers. It is given that $p$ divides $qr − 1$, $q$ divides $rp − 1$, and $r$ divides $pq − 1$. Determine all possible values of $pqr$.

I think I'm missing something in this problem. There's no solutions online so I was wondering if you guys could show me what I'm doing wrong.

We must have one of $p,q,r = 2$ as $pq - 1$, $pr - 1$, $qr - 1$ are congruent to $0 mod 2$ if $p,q,r > 2$, so wlog let $p = 2$ (more than one of $p,q,r$ being 2 gives contradiction). Then $q$ divides $2r - 1$ (so $2r - 1 = xq$) and $r$ divides $2q - 1$ (so $2q - 1 = yr$). Solving for r we have that $(xq + 1)/2 = (2q - 1)/y$ hence $ q = (2 + y)/(4 - xy)$. This gives the only pair as $(3,5)$, so $pqr$ can only be $30$?

The way the question is phrased leads me to believe there's more to it, and also it's the last question on an olympiad so it should take longer than 5 minutes.

Re-did it, is this okay?

If we write $ rq - 1 = px $ and $ rp - 1 = qy$ we obtain $ p = \frac{r + y}{r^2 - xy} $ and $ q = \frac{r + x}{r^2 - xy} $ (and clearly we can't have $ r^2 = xy $) so $q(r + y) = p(r + x)$. Then subbing $ x = \frac{3q - 1}{p} $ and $y = \frac{3p - 1}{q}$ we obtain $r=3$ if $p$ doesn't equal $q$ (if $p=q$ then no solutions). Then it's just a matter of checking cases and we just get $(p,q,r) = (5,7,3), (2,5,3)$. But $(5,7,3)$ doesn't satisfy the fact that $r$ divides $pq - 1$ hence the only solution is $pqr = 30$. I hope that's ok

$\endgroup$
9
  • $\begingroup$ Here's a MathJax tutorial :) $\endgroup$
    – Shaun
    Jul 20, 2014 at 18:21
  • $\begingroup$ Are negative primes allowed? $\endgroup$
    – Mathmo123
    Jul 20, 2014 at 18:23
  • $\begingroup$ Isn't a prime number positive by definition? Thanks Shaun I tried to make it better $\endgroup$
    – user121591
    Jul 20, 2014 at 18:25
  • 1
    $\begingroup$ I don't think your first line is correct. Suppose they are all greater than two. Then indeed all of the products of the form $pq-1$ are even. But that isn't a problem (even numbers can have odd prime divisors), and it doesn't immediately imply anything interesting. $\endgroup$
    – Potato
    Jul 20, 2014 at 18:35
  • $\begingroup$ By the way, I think you can piece a solution together from the comments here: nrich.maths.org/discus/messages/153904/149403.html?1281107322 $\endgroup$
    – Potato
    Jul 20, 2014 at 18:40

1 Answer 1

2
$\begingroup$

The divisibility criteria ensure that $pqr$ divides $$(pq-1)(pr-1)(qr-1)=p^2q^2r^2-p^2qr-pq^2r-pqr^2+pq+pr+qr-1,$$ and hence that $pqr\mid pq+pr+qr-1$. Without loss of generality $p\leq q\leq r$ and so $$3qr-1\geq pq+pr+qr-1\geq pqr,$$ which shows that $p<3$ and so $p=2$. Then $2qr\mid2q+2r+qr-1$ and so $q$ and $r$ are odd, and moreover $$2qr\leq 2q+2r+qr-1,$$ or equivalently $(q-2)(r-2)\leq3$. This shows that $q=3$ and $r\in\{3,5\}$, and a quick check shows that $r=3$ does not work and that $r=5$ does, so $\{p,q,r\}=\{2,3,5\}$ and so $pqr=30$.

$\endgroup$

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.