Maths Olympiad Prep

Library / /7 of 18

Number theory Difficulty 6.8 National Olympiad Prove it Vietnam

Prove that there exists infinitely many positive integer tt such that tt both 2012t+12012t+1 and 2013t+12013t+1 are perfect square.

2. Let m,nm, n be positive integers such that both mn+1mn+1 and (m+1)n+1(m+1)n+1 are perfect square. Prove that nn is divisible by 8(2m+1)8(2m+1).

Solution

1. Let d=(2012t+1,2013t+1)d = (2012t+1, 2013t+1) then it is easy to see that d=1d=1. Thus, both 2012t+12012t+1 and 2013t+12013t+1 are perfect square if and only if (2012t+1)(2013t+1)=y2(2012t+1)(2013t+1) = y^2 for some positive integer yy. We have
(2012t+1)(2013t+1)=y242012220132t2+4201220134025t+420122013=420122013y2(220122013t+4025)21=420122013y2 \begin{aligned} (2012t+1)(2013t+1) &= y^2 \\ &\Leftrightarrow 4 \cdot 2012^2 \cdot 2013^2 t^2 + 4 \cdot 2012 \cdot 2013 \cdot 4025t + 4 \cdot 2012 \cdot 2013 = 4 \cdot 2012 \cdot 2013 \cdot y^2 \\ &\Leftrightarrow (2 \cdot 2012 \cdot 2013t + 4025)^2 - 1 = 4 \cdot 2012 \cdot 2013 \cdot y^2 \end{aligned}
Putting x=220122013t+4025x = 2 \cdot 2012 \cdot 2013t + 4025 we have the equation x2420122013y2=1x^2 - 4 \cdot 2012 \cdot 2013y^2 = 1.
It is clear that 4201220134 \cdot 2012 \cdot 2013 is not perfect square, so the Pell equation of 1st type has infinitely many solutions. The fundamental solution of this equation is (x,y)=(4025,1)(x, y) = (4025, 1), thus all its solutions are given by formula
{x0=1,x1=4025,xn+2=8050xn+1xn,n0.y0=1,y1=1,yn+2=8050yn+1yn \begin{cases} x_0 = 1, x_1 = 4025, x_{n+2} = 8050x_{n+1} - x_n, & n \ge 0. \\ y_0 = 1, y_1 = 1, y_{n+2} = 8050y_{n+1} - y_n & \end{cases}
By induction, we can prove that x2i+1x_{2i+1} is congruent to 4025(mod220122013)4025 \pmod{2 \cdot 2012 \cdot 2013} for all ii and each value x2i+14025220122013\frac{x_{2i+1} - 4025}{2 \cdot 2012 \cdot 2013} gives us a positive integer tt satisfying the required condition.
So there exists infinitely many positive integers tt such that tt both 2012t+12012t+1 and 2013t+12013t+1 are perfect squares. (Q.E.D)

2. Let d=(mn+1,mn+n+1)d = (mn+1, mn+n+1) then
d(mn+n+1mn1) or dn, therefore d(mn+1mn) or d1. d|(mn+n+1-mn-1) \text{ or } d|n, \text{ therefore } d|(mn+1-mn) \text{ or } d|1.
Thus d=1d=1 or in other words the numbers mn+1,(m+1)n+1mn+1, (m+1)n+1 are relatively prime.
So, both mn+1mn+1 and (m+1)n+1(m+1)n+1 are perfect square if and only if
(mn+1)((m+1)n+1) is perfect square. (mn+1)((m+1)n+1) \text{ is perfect square.}
Assume that (mn+1)((m+1)n+1)=y2(mn+1)((m+1)n+1) = y^2 for yZ+y \in \mathbb{Z}^+. We have
m(m+1)n2+(2m+1)n+1=y24m2(m+1)2n2+4m(m+1)(2m+1)n+4m(m+1)=4m(m+1)y2(2m(m+1)n+(2m+1))21=4m(m+1)y2 \begin{aligned} & m(m+1)n^2 + (2m+1)n + 1 = y^2 \\ & \Leftrightarrow 4m^2(m+1)^2 n^2 + 4m(m+1)(2m+1)n + 4m(m+1) = 4m(m+1)y^2 \\ & \Leftrightarrow (2m(m+1)n + (2m+1))^2 - 1 = 4m(m+1)y^2 \end{aligned}
Putting x=2m(m+1)n+(2m+1)x = 2m(m+1)n + (2m+1) then we have following equation
x24m(m+1)y2=1() x^2 - 4m(m+1)y^2 = 1 (*)
This is the Pell equation of 1st type. Since 4m(m+1)4m(m+1) is not perfect square then (*) has infinitely many solutions.
The fundamental solution of equation (*) is (x,y)=(2m+1,1)(x, y) = (2m+1, 1), so all its solutions (xi,yi)(x_i, y_i) can be written in the form
{x0=1,x1=2m+1,xi+2=2(2m+1)xi+1xi,i0y0=0,y1=1,yi+2=2(2m+1)yi+1yi \begin{cases} x_0 = 1, x_1 = 2m+1, x_{i+2} = 2(2m+1)x_{i+1} - x_i, & i \ge 0 \\ y_0 = 0, y_1 = 1, y_{i+2} = 2(2m+1)y_{i+1} - y_i \end{cases}
By induction, we will prove that x2ix_{2i} is congruent to 1 modulo 2m(m+1)2m(m+1) and x2i+1x_{2i+1} is congruent 2m+12m+1 modulo 2m(m+1)2m(m+1) for all i=0,1,2,...i = 0,1,2,... (***)
Indeed,
- For i=0i=0, by the recurrent formula of (xi)(x_i) we see that (*) is true.
- Assume that (
*) is true for ii, i.e x2ix_{2i} is congruent to 1 and x2i+1x_{2i+1} is congruent 2m+12m+1 modulo 2m(m+1)2m(m+1). We have
x2i+2=2(2m+1)x2i+1x2i2(2m+1)(2m+1)1=8m(m+1)+11(mod2m(m+1)),x2i+3=2(2m+1)x2i+2x2i+12(2m+1)(2m+1)2m+1(mod2m(m+1)). \begin{aligned} x_{2i+2} &= 2(2m+1)x_{2i+1} - x_{2i} \equiv 2(2m+1)(2m+1) - 1 = 8m(m+1) + 1 \equiv 1 \pmod{2m(m+1)}, \\ x_{2i+3} &= 2(2m+1)x_{2i+2} - x_{2i+1} \equiv 2(2m+1) - (2m+1) \equiv 2m+1 \pmod{2m(m+1)}. \end{aligned}
Thus, (***) is true for i+1i+1.
By induction principle, (***) is true for all ii.

Next, we will establish the recurrent formula for ri=x2i+1r_i = x_{2i+1} where i=0,1,2,...i = 0,1,2,....
We have
ri+2=x2i+5=2(2m+1)x2i+4x2i+3=2(2m+1)(2(2m+1)x2i+3x2i+2)x2i+3=(4(2m+1)21)x2i+32(2m+1)x2i+2=(4(2m+1)21)x2i+3(x2i+3+x2i+1)=(4(2m+1)22)x2i+3x2i+1=(4(2m+1)22)ri+1ri \begin{aligned} r_{i+2} &= x_{2i+5} = 2(2m+1)x_{2i+4} - x_{2i+3} = 2(2m+1)(2(2m+1)x_{2i+3} - x_{2i+2}) - x_{2i+3} \\ &= (4(2m+1)^2 - 1)x_{2i+3} - 2(2m+1)x_{2i+2} = (4(2m+1)^2 - 1)x_{2i+3} - (x_{2i+3} + x_{2i+1}) \\ &= (4(2m+1)^2 - 2)x_{2i+3} - x_{2i+1} = (4(2m+1)^2 - 2)r_{i+1} - r_i \end{aligned}
Putting ri=2m(m+1)si+(2m+1)r_i = 2m(m+1)s_i + (2m+1) then the sequence (si),i>0(s_i), i > 0 is well-defined and consists of positive integers.
Putting in recurrent formula of (ri)(r_i), we get
2m(m+1)si+2+(2m+1)=(4(2m+1)22)(2m(m+1)si+1+(2m+1))(2m(m+1)si+(2m+1))2m(m+1)si+2=2m(m+1)(4(2m+1)22)si+12m(m+1)si+4(2m+1)(2m+1)21si+2=(4(2m+1)22)si+1si+8(2m+1) \begin{aligned} 2m(m+1)s_{i+2} + (2m+1) &= (4(2m+1)^2 - 2)(2m(m+1)s_{i+1} + (2m+1)) - (2m(m+1)s_i + (2m+1)) \\ \Leftrightarrow 2m(m+1)s_{i+2} &= 2m(m+1)(4(2m+1)^2 - 2)s_{i+1} - 2m(m+1)s_i + 4(2m+1)(2m+1)^2 - 1 \\ \Leftrightarrow s_{i+2} &= (4(2m+1)^2 - 2)s_{i+1} - s_i + 8(2m+1) \end{aligned}
We can compute r0=x1=2m+1r_0 = x_1 = 2m+1 so s0=0s_0 = 0 and
r1=x3=2(2m+1)(2(2m+1)21)(2m+1)=16m(m+1)(2m+1)+2m+1, r_1 = x_3 = 2(2m+1)(2(2m+1)^2 - 1) - (2m+1) = 16m(m+1)(2m+1) + 2m+1,
so we have s1=8(2m+1)s_1 = 8(2m+1).
We have the recurrent formula for (sis_i) are
{s0=0,s1=8(2m+1),si+2=(4(2m+1)22)si+1si+8(2m+1),i0 \begin{cases} s_0 = 0, s_1 = 8(2m+1), \\ s_{i+2} = (4(2m+1)^2 - 2)s_{i+1} - s_i + 8(2m+1), i \ge 0 \end{cases}
From which we can see that all terms of (sis_i) are divisible by 8(2m+1)8(2m+1).
Moreover, by putting x=2m(m+1)n+(2m+1)x = 2m(m+1)n + (2m+1) we can easily see that nn satisfies the required condition if and only if n=si,i=1,2,3,...n = s_i, i = 1, 2, 3, ... (note that s0=0s_0 = 0 is not a positive integer).
Thus, all value of nn is divisible by 8(2m+1)8(2m+1). (Q.E.D).

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.