2015 Taiwan TST Round 1 Quiz 1 Problem 1

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

w

14 users

TOPICS

No tags match your search

M

No tags match your search

M

2015 Taiwan TST Round 1 Quiz 1 Problem 1

G H J

Reveal topic tags

Taiwan TST 2015

BritishMathematicalOlympiad

L

G H BBookmark kLocked kLocked NReply

Source: 2015 Taiwan TST Round 1 Quiz 1 Problem 1

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

102 posts

#1 h Jul 12, 2015, 9:57 AM • 2 Y

Y by Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

116 posts

#2 h Jul 12, 2015, 12:09 PM • 3 Y

Y by andywu, Pluto1708, Adventure10

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

718 posts

Gibby

#3 h Jul 13, 2015, 2:13 AM • 1 Y

Y by Adventure10

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1900 posts

#4 h Feb 25, 2018, 2:23 PM • 1 Y

Y by Adventure10

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1566 posts

#5 h Feb 25, 2018, 2:28 PM • 2 Y

Y by Adventure10, Mango247

The same problem was in a British Mathematics Olympiad paper (I don't remember the year, but was surely before 2015)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

133 posts

#6 h Feb 25, 2018, 8:46 PM • 2 Y

Y by Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1900 posts

#7 h Feb 27, 2018, 4:30 PM • 2 Y

Y by Adventure10, Mango247

"Wider" problem: find all positive integers $x,y,z\ge 2$ such that $z|xy-1\wedge x|yz-1\wedge y|zx-1$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1900 posts

#8 h Feb 27, 2018, 4:46 PM • 2 Y

Y by Adventure10, Mango247

full solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

933 posts

#9 h Jan 9, 2025, 8:38 PM

Y by

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. :cool:

:cool:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4220 posts

#10 h Jan 9, 2025, 9:46 PM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1 post

#11 h Mar 19, 2025, 9:07 AM

Y by

From the condition we can get $\frac{1}{p}+\frac{1}{q}+\frac{1}{r}-\frac{1}{pqr} \in \mathbb{N}$ ,
but $\frac{1}{p}+\frac{1}{q}+\frac{1}{r}-\frac{1}{pqr} \leqslant \frac{1}{2} +\frac{1}{2}+\frac{1}{2}-\frac{1}{8}=\frac{11}{8}$ ,
therefore it must be $1$ .
Without loss of generality, let $p\geqslant q \geqslant r$ ,which means $\frac{1}{p}\leqslant \frac{1}{q}\leqslant\frac{1}{r}$
Then $\frac{1}{p}+\frac{1}{q}+\frac{1}{r}>1\Rightarrow \frac{1}{r}>\frac{1}{3}\Rightarrow r<3$ . However, r is a prime, hence, $r=2$ .
Then, we can deduce that $\frac{1}{p}+\frac{1}{q}-\frac{1}{2pq}=\frac{1}{2}\Rightarrow (p-2)(q-2)=3\Rightarrow p=5, q=3$
Therefore, the answers are $(5,3,2)$ and its permutations.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6 posts

#12 h Mar 19, 2025, 11:05 AM

Y by

let $p\geq q\geq r$ .
$p \mid qr-1 \Rightarrow p \mid pq+pr+rq-1$ ,
$q \mid pr-1 \Rightarrow q \mid pq+pr+rq-1$ ,
$r \mid pq-1 \Rightarrow r \mid pq+pr+rq-1$ ,

so Because $p,q,r$ are prime we have:
$pqr \mid pq+pr+rq -1 \rightarrow pqr+1 \leq pq+pr+rq$ . contradiction for $r\geq 3$ .
so $r=2$ .
$p \mid 2q-1 \Rightarrow p \mid 2q+2p-1$
$q \mid 2p-1 \Rightarrow q \mid 2q+2p-1$
similary, $pq \leq 2p+2q-1 \Leftrightarrow (q-2)(p-2)\leq 3$
only $(2,3,5)$ works.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a