Maths Olympiad Prep

Library / /11 of 13

Algebra Difficulty 6.6 National olympiad Prove it Bulgaria

Given a rational number q>3q > 3 such that q24q^2 - 4 is the square of a rational number. The row {ai}i=0\{a_i\}_{i=0}^{\infty} is defined as follows:
a0=2, a1=q, ai+1=qaiai1, for each i=1,2, a_0 = 2, \ a_1 = q, \ a_{i+1} = q a_i - a_{i-1}, \text{ for each } i = 1, 2, \dots

Do there exist a natural number nn and nonzero integers b0,b1,,bnb_0, b_1, \dots, b_n such that i=0nbi=0\sum_{i=0}^n b_i = 0 and if we write the number b0a0+b1a1++bnanb_0 a_0 + b_1 a_1 + \dots + b_n a_n in the form AB\frac{A}{B}, where AA and BB are co-prime integers, then is the number AA free of squares?

Solution

We will prove that such numbers do not exist.

The quadratic equation x2qx+1=0x^2 - qx + 1 = 0 has two rational roots tt and 1t\frac{1}{t} for which t+1t=qt + \frac{1}{t} = q. It easily follows by induction that am=tm+1tma_m = t^m + \frac{1}{t^m}. Let's assume that there exist numbers b0,b1,,bnb_0, b_1, \dots, b_n satisfying the condition of the problem.

Lemma. Let f(x)=cnxn+cn1xn1++c1x+c0f(x) = c_n x^n + c_{n-1} x^{n-1} + \dots + c_1 x + c_0 be a polynomial with nonzero integer coefficients for which cnk=ckc_{n-k} = c_k for each k=0,1,,nk = 0, 1, \dots, n and i=0nci=0\sum_{i=0}^n c_i = 0. Then f(x)=(x1)2g(x)f(x) = (x-1)^2 g(x), where g(x)g(x) is a polynomial with integer coefficients.

Proof: From the condition we have that f(1)=0f(1) = 0. As
f(x)=ncnxn1+(n1)cn1xn2++c1, f'(x) = n c_n x^{n-1} + (n-1) c_{n-1} x^{n-2} + \dots + c_1,
it follows that
2f(1)=(ncn+(n1)cn1++c1)+(nc0+(n1)c1++cn1)=n(cn+cn1++c1+c0)=0 2 f'(1) = (n c_n + (n-1) c_{n-1} + \dots + c_1) + (n c_0 + (n-1) c_1 + \dots + c_{n-1}) = n(c_n + c_{n-1} + \dots + c_1 + c_0) = 0
and therefore x=1x = 1 is a double root. The lemma is proved.

The polynomial f(x)=bnx2n+bn1x2n1++b1xn+1+2b0xn+b1xn1+b2xn2++bn1x+bnf(x) = b_n x^{2n} + b_{n-1} x^{2n-1} + \dots + b_1 x^{n+1} + 2b_0 x^n + b_1 x^{n-1} + b_2 x^{n-2} + \dots + b_{n-1} x + b_n satisfies the conditions of the lemma. It's not hard to see that
tn(bn(tn+1tn)+bn1(tn1+1tn1)++2b0)=f(t)=(t1)2g(t). t^n \left( b_n \left( t^n + \frac{1}{t^n} \right) + b_{n-1} \left( t^{n-1} + \frac{1}{t^{n-1}} \right) + \dots + 2b_0 \right) = f(t) = (t-1)^2 g(t).
Moreover, if t=rst = \frac{r}{s}, (r,s)=1(r, s) = 1, then from rs+sr=q>3\frac{r}{s} + \frac{s}{r} = q > 3 it easily follows that rs+2r \ge s + 2, i.e. rs2r - s \ge 2. Then g(rs)g\left(\frac{r}{s}\right) is a number of the form ls2n2\frac{l}{s^{2n-2}}.

Finally b0a0+b1a1++bnanb_0 a_0 + b_1 a_1 + \dots + b_n a_n is presented in the form (rs)2lrnsn\frac{(r-s)^2 l}{r^n s^n} and because the number rs2r-s \ge 2 and (rs,r)=(rs,s)=1(r-s, r) = (r-s, s) = 1, then the numerator will always square a prime number. \square

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 and solution reproduced as published; topic and difficulty added by this site.