For any positive integer $n>1$, let $p(n)$ be the greatest prime factor of $n$. Find all the triplets of distinct positive integers $(x,y,z)$ which satisfy the following properties: $x,y$ and $z$ form an arithmetic progression, and $p(xyz)\leq 3.$
Problem
Source:
Tags: number theory, Romanian TST, TST, BritishMathematicalOlympiad
15.05.2021 20:20
Factoring the GCD, we get some cases(excluding cases when we have a contradiction by $mod 2$ or $mod 3$), where $a,b,c>0$ 1)$x=2^a,y=3^b,z=2^c$. In this case we must have $2\cdot 3^b=2^a(1+2^{c-a})$ which implies $a=1$. Furthermore, by mihailescu, we either have $c-a=1$ or $c-a=3$ and respectively $b=1$ or $b=2$ This leads to either $(x,y,z)=(2,3,4)$ or $(x,y,z)=(2,9,16)$ 2)$(x,y,z)=(3^a,2^b,3^c)$. This implies $3^a(1+3^{c-a})=2^{b+1}$. This implies $a=0$, so we can exclude this case 3)$(x,y,z)=(1,2^a,3^c)$. This means $2^{a+1}=1+3^c$, and so by mihailescu either $c=1$ and $a=1$, which leads to $(1,2,3)$ 4)$(x,y,z)=(1,1,1)$. This trivially works. Therefore all solutions are those cited before scaled by $3^m2^n$, where $m,n\geq 0$ and with any permutation (since it wasn't said arithmetic progression in which order)
15.05.2021 20:32
Verbatim from 2003 British Olympiad.
15.05.2021 20:34
So is it $p(xyz)$? The notion $p(x,y,z)$ does not seem to make sense... Please clarify the problem statement!
15.05.2021 20:42
Tintarn wrote: So is it $p(xyz)$? The notion $p(x,y,z)$ does not seem to make sense... Please clarify the problem statement! I think it means $p(xyz)\leq 3$ or equivalently $p(x)\leq 3,p(y)\leq 3,p(z)\leq 3$, which is maybe what is implied by the commas.
15.05.2021 20:50
Tintarn wrote: So is it $p(xyz)$? The notion $p(x,y,z)$ does not seem to make sense... Please clarify the problem statement! Yes, I am sorry, I made a little typing mistake.
15.05.2021 21:22
16.05.2021 18:30
Basically case bashing, $(\text{mod} \ 2),(\text{mod} \ 3)$ and a bit of Mihăilescu's.
17.05.2021 12:20
I want to point out that the original text of the problem mentioned finding the triplets of distinct numbers x,y,z satisfying those conditions. I know it's not a big deal but that gives only 3 correct forms for the solution triplets.
17.05.2021 15:05
oVlad wrote: Basically case bashing, $(\text{mod} \ 2),(\text{mod} \ 3)$ and a bit of Mihăilescu's. Or Zsigmondy (instead of Mihăilescu).
30.07.2021 18:51
I found that the only solutions are (x,y,z) = (2^k.3^b , 2^(k+1).3^b , 2^k,3^(b+1) ) or (2^(c+1).3^m , 2^(c).3^(m+1) , 2^(c+2).3^m ) or (2^(d+1).3^f , 2^d.3^(f+2) , 2^(d+4.3^f)
13.04.2022 16:06
CahitArf wrote: I found that the only solutions are (x,y,z) = (2^k.3^b , 2^(k+1).3^b , 2^k,3^(b+1) ) or (2^(c+1).3^m , 2^(c).3^(m+1) , 2^(c+2).3^m ) or (2^(d+1).3^f , 2^d.3^(f+2) , 2^(d+4.3^f) same
07.11.2022 21:45
IMO a bit easy for P2, the special cases for zsigmondy was annoying but cool problem overall, and uhh I think I overcomplicated things again The condition $p(xyz) \le 3$ gives that $x,y,z$ only has prime divisors $2,3$ only.WLOG $x<y<z$ and let $\gcd(x,y,z)= l$. Define $x',y',z'$ such that $x'l=x,y'l=y,z'l=z$. Since they form a sequence, we have $x'l+d=y'l$ and $y'l+d=z'l$. Then $d= l(y'-x')=l(z'-y')$ which gives $y'-x=z'-y'$, hence if there are solutions triplets $(x',y',z')$, so does the triplets $(lx',ly',z')$ where $l=2^p3^q$, hence assume $l=1$. Now divide into cases. Case 1. two of the variables $x,y,z$ are divisible by $3$. Then either the third one is divisible by $3$ or $ d \equiv 1 \mod 3$, contradiction. $\square$ Case 2. one of the variables $x,y,z$ is divisible by $3$. ( Note that powers of $2$ can be $0$) Subcase 2.1 $3|x$. Then let $x=3^a2^b,y=2^p,z=2^q$. Since they form a arithmetic sequence, we have $$z-y=y-x \Leftrightarrow 2^{p+1}=2^q+3^a2^b=2^b(2^{q-b}+3^a)$$Then $b=p+1$, but notice that $x=3^a2^{p+1}>y=2^p$, contradiction to our WLOG. $\square$ Subcase 2.2 $3|y$ Let $x=2^b,y=2^p3^q,z=2^n$. Similiarly, since they form a sequence: $$2^{p+1}3^q=2^n+2^b=2^b(2^{n-b}+1)$$Which gives $p+1=b$, which is a contradiction to $\gcd(x,y,z)=1$ since $b<n$ if $p>0$, hence $p=0$, which gives $b=1$. Hence we have $$3^q=2^{n-1}+1$$ By fermat's little theorem, $2^x \equiv -1 \mod 3$ if $x=2k+1$, meaning $n+1$ is odd. Then we can factor RHS, which is $2^{n-1}+1=(2+1)(stuff)$ By Zsigmondy's theorem, there is some $p$ such that $p|2^{2k+1}+1$ but $p \nmid (2+1) $, which gives that there is another prime factor for RHS. But this theorem does not hold for $2^3+1$ ( special case and well known) or exponend is $1$ ( also well known). Hence $n=4$, Which gives a triplets $\boxed{(2,9,16) \ (2,3,4)}$. $\square$ Remark: $b=0$ gives $2^{p+1}3^q=2^n+1$ which is obviously wrong, hence $b=0$ is excluded. Subcase 2.3 $3|z$ Let $x=2^b,y=2^p,z=2^n3^m$, similiar as above cases, we have $$2^{p+1}=2^b(2^{n-b}3^m+1)$$ Which gives $p+1=b$ if $b \neq 0$, contradiction to our WLOG. Hence $b=0$, which gives $$2^{p+1}=2^n3^m+1$$Since $m>0$, we must have $n=0$, hence $2^{p+1}-1=3^m$ Again by Fermat's little theorem, $p+1$ is even, hence we can use Zsigmondy again to have contradiction, but again we have special cases when power is $6$ or power is $2$ and sum of bases equals to power of $2$, $p+1=6$ gives no solutions, $p+1=2$ gives solution $\boxed{(1,2,3)}$. $\square$ If none of the variables are divisible by $3$. Then we must have $x=1,y=2^a,z=2^b$, $x=1,y=1,z=2^a$ which gives trivial contradictions. Hence, the solutions are $\boxed{(x,y,z)=(l,2l,3l),(2l,3l,4l),(2l,9l,16l)}$ where $l=2^a3^b$ $\blacksquare$