Find all primes $p,q,r$ such that $qr-1$ is divisible by $p$, $pr-1$ is divisible by $q$, $pq-1$ is divisible by $r$.
Problem
Source: 2015 Taiwan TST Round 1 Quiz 1 Problem 1
Tags: number theory, Taiwan, Taiwan TST 2015, BritishMathematicalOlympiad
12.07.2015 15:09
From condition we deduce $pqr|(pq-1)(pr-1)(qr-1)\rightarrow pqr|pq+qr+pr-1\Rightarrow pqr\leq pq+pr+qr$. The rest is easy by limit....
13.07.2015 05:13
First note: kaito got the first statement from mulitplying all the congruences together and once you get to the statement where the product of all is less than or equal to the sum of pairwise products, you finish it off by dividing by the product of all of them. This gives you 1 is less than or equal to 1/p + 1/q + 1/r so if p,q,r are all greater than 2 then they are all 3, this doesn't work. So at least one is 2. If two are 2 then we get a contradiction because (say the remaining prime is r, and r is not equal to 2) 2 divides 2r-1 but 2r-1 is odd, a contradiction. Thus exactly one (say p) is 2. Using SFFT we get that (p,q,r)=(2,3,5) and permutations.
25.02.2018 17:23
I have this task in a book from 1994. It's author collected problems from USA, Canada, Belarus, Lithuania, Russia and Crux Mathematicorum, Mathematics Magazine, and Quantum (Russian) so it must had been already known by some wider audience (not necessarily from Taiwan) before TST.
25.02.2018 17:28
The same problem was in a British Mathematics Olympiad paper (I don't remember the year, but was surely before 2015)
25.02.2018 23:46
Wizard_32 wrote: The same problem was in a British Mathematics Olympiad paper (I don't remember the year, but was surely before 2015) BMO1 2003/04 question five. Also in the first solution inequality is strict.
27.02.2018 19:30
"Wider" problem: find all positive integers $x,y,z\ge 2$ such that $z|xy-1\wedge x|yz-1\wedge y|zx-1$
27.02.2018 19:46
09.01.2025 23:38
2 am solves are fun We claim that, letting $p \le q \le r$ WLOG, the only solution is $(p, q, r) = (2, 3, 5)$. Note that multiplying all the divisibilities, we have $pqr \mid pq+qr+rp - 1 \implies \frac 1p + \frac 1q + \frac 1r > 1$. But now $\frac 1p > \frac 13 \implies p = 2$, so $\frac 1q + \frac 1r > \frac 12$. Similar logic gives us $q \le 3 \implies q = 3$, and $r \le 5 \implies r = 5$ as $p, q, r$ are all mutually distinct. And $(2, 3, 5)$ and permutations do work, so we're done.
10.01.2025 00:46
this means that $pqr$ divides $pq+qr+rq-1$ so $\frac1p+\frac1q+\frac1r-\frac1{pqr}$ is an integer. since $pq+qr+rq-1\ge 2\cdot2+2\cdot2+2\cdot2-1=11$, the quantity must be positive. since $\frac1p+\frac1q+\frac1r-\frac1{pqr}\le \frac12+\frac12+\frac12=\frac32$, it must be $1$. WLOG let $p\le q\le r$. When $p\ge 5$, $\frac1p+\frac1q+\frac1r\le \frac35$, so this is bad. When $p=3$, $\frac1p+\frac1q+\frac1r-\frac1{pqr}<\frac1p+\frac1q+\frac1r\le \frac33=1$, so this is bad. Therefore, $p=2$ so we want to solve $\frac{1}{q}+\frac{1}{r}=\frac{1}{2}+\frac{1}{2qr}$. multiply both sides by $2qr$ to get $2q+2r=qr+1$ so $(q-2)(r-2)=3$. therefore, the only solution is $(2,3,5)$ and perms