Maths Olympiad Prep

Library / /109 of 128

Number theory Difficulty 6.5 National Olympiad Prove it Philippines

Problem:
Determine all ordered pairs (x,y)(x, y) of nonnegative integers that satisfy the equation
3x2+29y=x(4y+11) 3 x^{2}+2 \cdot 9^{y}=x\left(4^{y+1}-1\right)

Solution

Solution:
The equation is equivalent to
(3x)2+232y+1=3x[2(2y+1)+11] (3 x)^{2}+2 \cdot 3^{2 y+1}=3 x\left[2^{(2 y+1)+1}-1\right]
Letting a=3xa=3 x and b=2y+1b=2 y+1, we have
a2+23b=a(2b+11) a^{2}+2 \cdot 3^{b}=a\left(2^{b+1}-1\right)
Case 1: b=1b=1
We have a23a+6=0a^{2}-3 a+6=0 which has no integer solution for aa. Thus, there is no solution in this case.

Case 2: b=3b=3
We have a215a+54=0a^{2}-15 a+54=0, whose roots are 6 and 9, both divisible by 3. This case then has the solutions (2,1)(2,1) and (3,1)(3,1) for the original equation.

Case 3: b=5b=5
We have a263a+486=0a^{2}-63 a+486=0, whose roots are 9 and 54, both divisible by 3. We get as additional solutions (3,2)(3,2) and (18,2)(18,2).

Case 4: b7b \geq 7, bb odd
It follows from (1) that a23ba \mid 2 \cdot 3^{b}. Since aa is divisible by 3, either a=3pa=3^{p} for some 1pb1 \leq p \leq b or a=23qa=2 \cdot 3^{q} for some 1qb1 \leq q \leq b.

For the first case a=3pa=3^{p}, let q=bpq=b-p. Then we have
2b+11=a+23ba=3p+23q 2^{b+1}-1=a+\frac{2 \cdot 3^{b}}{a}=3^{p}+2 \cdot 3^{q}
For the second case a=23qa=2 \cdot 3^{q}, let p=bqp=b-q. Then we have
2b+11=a+23ba=23q+3p 2^{b+1}-1=a+\frac{2 \cdot 3^{b}}{a}=2 \cdot 3^{q}+3^{p}
In either case,
2b+11=3p+23q 2^{b+1}-1=3^{p}+2 \cdot 3^{q}
where p+q=bp+q=b. Consequently, 2b+1>3p2^{b+1}>3^{p} and 2b+1>23q2^{b+1}>2 \cdot 3^{q}. Thus,
3p<2b+1=8b+13<9b+13=32(b+1)323q<2b+1=28b3<29b3=232b3<232(b+1)3 \begin{aligned} 3^{p}<2^{b+1} & =8^{\frac{b+1}{3}}<9^{\frac{b+1}{3}}=3^{\frac{2(b+1)}{3}} \\ 2 \cdot 3^{q}<2^{b+1} & =2 \cdot 8^{\frac{b}{3}}<2 \cdot 9^{\frac{b}{3}}=2 \cdot 3^{\frac{2 b}{3}}<2 \cdot 3^{\frac{2(b+1)}{3}} \end{aligned}
Thus, p,q<2(b+1)3p, q<\frac{2(b+1)}{3}. Since p=bqp=b-q and q=bpq=b-p, we get p,q>b2(b+1)3=b23p, q>b-\frac{2(b+1)}{3}=\frac{b-2}{3}. Therefore,
b23<p,q<2(b+1)3 \frac{b-2}{3}<p, q<\frac{2(b+1)}{3}
Let r=min{p,q}r=\min \{p, q\}. Since r>b2353r>\frac{b-2}{3} \geq \frac{5}{3}, then r2r \geq 2. Consequently, the right hand side of (2) is divisible by 9. Thus, 9 divides 2b+112^{b+1}-1. This is true only if 6b+16 \mid b+1. Since b7b \geq 7, then b11b \geq 11. Thus, we can let b+1=6sb+1=6 s for some positive integer ss, and we can write
2b+11=26s1=43s1=(2s1)(2s+1)(42s+4s+1) 2^{b+1}-1=2^{6 s}-1=4^{3 s}-1=\left(2^{s}-1\right)\left(2^{s}+1\right)\left(4^{2 s}+4^{s}+1\right)
Since 4s1mod34^{s} \equiv 1 \bmod 3, then 42s+4s+1=(4s1)2+34s4^{2 s}+4^{s}+1=\left(4^{s}-1\right)^{2}+3 \cdot 4^{s} is always divisible by 3 but never by 9. Furthermore, at most one of 2s12^{s}-1 and 2s+12^{s}+1 is divisible by 3, being consecutive odd numbers. Since 3r2b+113^{r} \mid 2^{b+1}-1, then either 3r12s13^{r-1} \mid 2^{s}-1 or 3r12s+13^{r-1} \mid 2^{s}+1. From both cases, we have 3r12s+13^{r-1} \leq 2^{s}+1. Thus,
3r12s+13s=3b+16 3^{r-1} \leq 2^{s}+1 \leq 3^{s}=3^{\frac{b+1}{6}}
Therefore,
b231<r1b+16 \frac{b-2}{3}-1<r-1 \leq \frac{b+1}{6}
which implies b<11b<11. However, there is no odd integer bb between 7 (included) and 11 (excluded) such that 6b+16 \mid b+1. There are then no solutions for this last case.

Therefore, the solutions (x,y)(x, y) of the given equation are (2,1),(3,1),(3,2)(2,1),(3,1),(3,2), and (18,2)(18,2).

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.